Program > By author > Desrosiers Jacques

This presentation describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the Improved Primal Simplex algorithm (IPS) 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 non-degenerate 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 non-degenerate pivot at every iteration of the solution process until optimality is reached. To achieve such a result, a negative reduced cost convex combination of variables is selected such that it is compatible with the current row-reduced problem, 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 rule (PE). It capitalizes on the compatibility definition to determine the variable status 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 non-degenerate pivot, PE permits a trade-of 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 Vector Space Decomposition.