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

Jean Bertrand Gauthier (), Jacques Desrosiers () and Marco E. Lübbecke ()
Additional contact information
Jean Bertrand Gauthier: HEC Montréal and GERAD
Jacques Desrosiers: HEC Montréal and GERAD
Marco E. Lübbecke: RWTH Aachen University

EURO Journal on Transportation and Logistics, 2016, vol. 5, issue 2, No 3, 204 pages

Abstract: 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 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.

Keywords: Primal simplex; Degeneracy; Combination of entering variables; Positive edge rule; Nondegenerate pivot algorithm; Dynamic Dantzig–Wolfe decomposition; Vector subspace (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s13676-015-0077-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjtl:v:5:y:2016:i:2:d:10.1007_s13676-015-0077-5

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13676

DOI: 10.1007/s13676-015-0077-5

Access Statistics for this article

EURO Journal on Transportation and Logistics is currently edited by Michel Bierlaire

More articles in EURO Journal on Transportation and Logistics from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().