Optimization Online


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

Jean-Bertrand Gauthier(jean-bertrand.gauthier***at***hec.ca)
Jacques Desrosiers(jacques.desrosiers***at***gerad.ca)
Marco Lübbecke(marco.luebbecke***at***rwth-aachen.de)

Abstract: 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 optimality 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 Constraints 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, this added value is obtained without explicitly computing the updated column components in the simplex tableau. Since the selection of a compatible variable to enter the basis ensures a nondegenerate pivot, PE permits a trade-off between strict improvement and high reduced cost degenerate pivots. 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.

Keywords: Primal simplex, degeneracy, combination of entering variables, Positive Edge rule, nondegenerate pivot algorithm, dynamic Dantzig-Wolfe decomposition, vector subspace

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Submitted to EURO Journal of Transportation and Logistics

Download: [PDF]

Entry Submitted: 10/08/2014
Entry Accepted: 10/08/2014
Entry Last Modified: 10/08/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society