Another pedagogy for mixed-integer Gomory

Jon Lee () and Angelika Wiegele ()
Additional contact information
Jon Lee: University of Michigan
Angelika Wiegele: Alpen-Adria-Universität Klagenfurt

EURO Journal on Computational Optimization, 2017, vol. 5, issue 4, No 1, 455-466

Abstract: Abstract We present a version of GMI (Gomory mixed-integer) cuts in a way so that they are derived with respect to a “dual form” mixed-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. This follows the general scheme of He and Lee, who did the case of Gomory pure-integer cuts. Our input mixed-integer problem is not in standard form, and so our cuts are derived rather differently from how they are normally derived. A convenient way to develop GMI cuts is from MIR (mixed-integer rounding) cuts, which are developed from 2-dimensional BMI (basic mixed-integer) cuts, which involve a nonnegative continuous variable and an integer variable. The non-negativity of the continuous variable is not the right tool for us, as our starting point (the “dual form” mixed-integer optimization problem) has no non-negativity. So we work out a different 2-dimensional starting point, a pair of somewhat arbitrary inequalities in one continuous and one integer variable. In the end, we follow the approach of He and Lee, getting now a finitely converging primal simplex column-generation algorithm for mixed-integer optimization problems.

Keywords: Mixed-integer programming; Gomory mixed-integer cut; Mixed-integer rounding cut; Basic mixed-integer cut; Column generation; Primal simplex algorithm; 90C10 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-017-0085-3 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:eurjco:v:5:y:2017:i:4:d:10.1007_s13675-017-0085-3

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

DOI: 10.1007/s13675-017-0085-3

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

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