  


Another pedagogy for mixedinteger Gomory
Jon Lee(jonxleeumich.edu) Abstract: We present a version of GMI (Gomory mixedinteger) cuts in a way so that they are derived with respect to a ``dual form'' mixedinteger optimization problem and applied on the standardform primal side as columns, using the primal simplex algorithm. This follows the general scheme of He and Lee, who did the case of Gomory pureinteger cuts. Our input mixedinteger 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 (mixedinteger rounding) cuts, which are developed from 2dimensional 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'' mixedinteger optimization problem) has no nonnegativity. So we work out a different 2dimensional 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 primalsimplex columngeneration algorithm for mixedinteger optimization problems. Keywords: mixedinteger programming, Gomory mixedinteger cut, mixedinteger rounding cut, basic mixedinteger 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  