Optimization Online


Another pedagogy for mixed-integer Gomory

Jon Lee(jonxlee***at***umich.edu)
Angelika Wiegele(angelika.wiegele***at***aau.at)

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 nonnegativity of the continuous variable is not the right tool for us, as our starting point (the ``dual form'' mixed-integer optimization problem) has no nonnegativity. 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

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: arXiv 1510.06522 http://arxiv.org/abs/1510.06522

Download: [PDF]

Entry Submitted: 10/25/2015
Entry Accepted: 10/25/2015
Entry Last Modified: 10/25/2015

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