Another pedagogy for mixed-integer Gomory

DOI10.1007/S13675-017-0085-3MaRDI QIDQ1688937zbMATH OpenOpenAlexFDO

Authors Peng Zhang

Publication date 12 January 2018

Published in EURO Journal on Computational Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1510.06522

zbMATH Keywords

column generationmixed-integer programmingprimal simplex algorithmbasic mixed-integer cutGomory mixed-integer cutmixed-integer rounding cut

Mathematics Subject Classification ID

Integer programming (90C10)

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.

Recommendations

• Another pedagogy for pure-integer Gomory
• Gomory cuts revisited
• Strengthening Gomory Mixed-Integer Cuts
• On the strength of Gomory mixed-integer cuts as group cuts
• A relax-and-cut framework for Gomory's mixed-integer cuts

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• Aggregation and Mixed Integer Rounding to Solve MIPs
• Another pedagogy for pure-integer Gomory
• Integer Programming
• Integer Programming: Methods, Uses, Computations
• The ongoing story of Gomory cuts

Cited in

(2)

• Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective
• Another pedagogy for pure-integer Gomory

Describes a project that uses

Uses Software

• JLee_LinearOptimizationBook
• GitHub

This page was built for publication: Another pedagogy for mixed-integer Gomory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688937)