Browse Prior Art Database

Generation of Valid Inequalities from Gomory Polyhedra

IP.com Disclosure Number: IPCOM000073578D
Original Publication Date: 1971-Jan-01
Included in the Prior Art Database: 2005-Feb-22
Document File: 3 page(s) / 31K

Publishing Venue

IBM

Related People

Gomory, RE: AUTHOR [+2]

Abstract

The integer programming problem is to minimize a linear objective function subject to linear inequality constraints and subject to some variables taking on integer values. In several procedures (e.g. cutting plane methods, branch and bound, enumeration), additional valid linear inequalities are useful in solving an integer problem.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 55% of the total text.

Page 1 of 3

Generation of Valid Inequalities from Gomory Polyhedra

The integer programming problem is to minimize a linear objective function subject to linear inequality constraints and subject to some variables taking on integer values. In several procedures (e.g. cutting plane methods, branch and bound, enumeration), additional valid linear inequalities are useful in solving an integer problem.

The faces of Gomory's corner polyhedron can be used to find inequalities satisfied by every integer solution to a given integer program. However, in order to do so, the corresponding linear program must have an optimal basis with a small determinant, and exact integer arithmetic must be used in solving the linear program. The present work is intended to given practical methods of generating inequalities for mixed integer programming problems.

Consider the mixed integer program

(1) x >/- 0,

(2) x(j) integer for j epsilon I

(3) Ax = b

(4) cx = z(min), where I is a subset of {1,...,m+n} and A is an mx(m+n) matrix of real numbers. For any real numbers l(i), i = 1,...,m, every x satisfying (3) will also satisfy

(Image Omitted)

where (z) denotes the fractional part of z. The problem is now to find linear inequalities satisfied by every x for which (1), (2), and (5) hold. In order to do so, a special case is first examined in detail.

Let P(C(D),+1,-1,b) denote the convex hull in R/D+1/ of all (x(1),... x(D- 1),x(+),x(-)) satisfying (6) x(1) >/- 0,...,x(D-1) >/- 0, x(+) >/- 0, x(-) >/- 0, (7) x ,...,x integer valued,

(Image Omitted)

R. Gomory, "Some Polyhedra Related to Combinatorial Problems," J. of Linear Algebra and Its Applications, Vol. 2, No. 4 (Oct 1969) 451-558....