...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>EURO journal of transportation and logistics >Tools for primal degenerate linear programs: IPS, DCA, and PE
【24h】

Tools for primal degenerate linear programs: IPS, DCA, and PE

机译：用于原始简并线性程序的工具：IPS，DCA和PE

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the improved primal simplex (IPS) algorithm which turns degeneracy into a possible advantage. The constraints of the original problem are dynamically partitioned based on the numerical values of the current basic variables. The idea is to work only with those constraints that correspond to nondegenerate basic variables. This leads to a row-reduced problem which decreases the size of the current working basis. The main feature of IPS is that it provides a nondegenerate pivot at every iteration of the solution process until op-timality is reached. To achieve such a result, a negative reduced cost convex combination of the variables at their bounds is selected, if any. This pricing step provides a necessary and sufficient optimality condition for linear programming. The second tool is the dynamic constraint aggregation (DCA), a constructive strategy specifically designed for set partitioning constraints. It heuristically aims to achieve the properties provided by the IPS methodology. We bridge the similarities and differences of IPS and DCA on set partitioning models. The final tool is the positive edge (PE) rule. It capitalizes on the compatibility definition to determine the status of a column vector and the associated variable during the reduced cost computation. Within IPS, the selection of a compatible variable to enter the basis ensures a nondegenerate pivot, hence PE permits a trade-off between strict improvement and high, reduced cost degenerate pivots. This added value is obtained without explicitly computing the updated column components in the simplex tableau. Ultimately, we establish tight bonds between these three tools by going back to the linear algebra framework from which emanates the so-called concept of subspace basis.
机译：本文介绍了用于处理线性规划中原始退化的三种最新工具。第一个是改进的原始单纯形（IPS）算法，它将简并性转化为可能的优势。原始问题的约束条件基于当前基本变量的数值进行动态分区。想法是仅使用与非退化基本变量相对应的那些约束。这导致行减少的问题，从而减小了当前工作基础的大小。 IPS的主要特点是，它在解决方案过程的每次迭代中都提供了一个不退化的枢轴，直到达到最佳状态为止。为了获得这样的结果，选择变量在其边界处的负的降低成本的凸组合（如果有）。该定价步骤为线性规划提供了必要和充分的最优条件。第二个工具是动态约束聚合（DCA），这是一种专门为设置分区约束而设计的构造策略。它启发式地旨在实现IPS方法提供的属性。我们在设置分区模型上架起了IPS和DCA的异同点。最终工具是上升沿（PE）规则。它利用兼容性定义在减少成本的计算过程中确定列向量和关联变量的状态。在IPS中，选择兼容变量以输入基数可确保不退化的支点，因此PE允许在严格改进与成本降低的退化支点之间进行权衡。在不显式计算单纯形表中更新的列组件的情况下获得此附加值。最终，我们回到线性代数框架来建立这三个工具之间的紧密联系，线性代数框架由此产生了所谓的子空间基础概念。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号