Optimization Online


Another pedagogy for pure-integer Gomory

Qi He (qihe***at***umich.edu)
Jon Lee (jonxlee***at***umich.edu)

Abstract: We present pure-integer Gomory cuts in a way so that they are derived with respect to a ``dual form'' pure-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. The input integer problem is not in standard form, and so the cuts are derived a bit differently. In this manner, we obtain a finitely-terminating version of pure-integer Gomory cuts that employs the primal rather than the dual simplex algorithm.

Keywords: Gomory cut, Chvatal-Gomory cut, cutting plane, integer program, integer linear program, integer optimization, simplex algorithm, lexicographic

Category 1: Integer Programming

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 07/19/2015
Entry Accepted: 07/19/2015
Entry Last Modified: 12/17/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