Browse Prior Art Database

SOME CONTINUOUS FUNCTIONS RELATED TO CORNER POLYHEDRA

IP.com Disclosure Number: IPCOM000148455D
Original Publication Date: 1971-Feb-23
Included in the Prior Art Database: 2007-Mar-30
Document File: 108 page(s) / 3M

Publishing Venue

Software Patent Institute

Related People

Gomory, Ralph E.: AUTHOR [+3]

Abstract

Ralph E. Gomory Ellis L. Johnson IBM Thomas J. Watson Research Center Yorktown Heights, New York RC 3311 #14921) February 23, 1971 SOME CONTINUOUS FUNCTIONS RELATED TO CORNER POLYHEDRA Ralph E. Gomory E l l i s L. Johnson INTRODUCÎON A. Inequalities based on the integer nature of some or a l l of the variables are useful in almost any algorithm for integer programming. They can furnish cut of f s for branch and bound or truncated enumeration methods, or cutting planes for cutting plane methods. In this paper we describe methods for producing such inequalities and develop some underlying theory. We will attempt to outline our general approach, taking the pure integer case first. Consider a pure integer problem (1) Ax b, x 2 0in which A is an mx(m+n) matrix, x is an integer m+n vector, and b an m-vector. If we consider a basis B (in most applications this w i l l be an optimal basis) we can write (1) as Bx N x N b x B O , x N O B where x is the m-vector of basic variables and the non-basic n-vector.

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 6% of the total text.

Page 1 of 108

SOME CONTINUOUS FUNCTIONS RELATED TO CORNER POLYHEDRA

Ralph E. Gomory
Ellis L. Johnson

IBM Thomas J. Watson Research Center Yorktown Heights, New York

RC 3311 ( #14921)
February 23, 1971

[This page contains 1 picture or other non-text object]

Page 2 of 108

SOME CONTINUOUS FUNCTIONS RELATED TO CORNER POLYHEDRA

Ralph E. Gomory

E l l i s L. Johnson

INTRODUCÎON

A.

- Inequalities based on the integer nature of some or a l l of the variables are useful in almost any algorithm for integer programming. They can furnish cut of f s for branch and bound or truncated enumeration methods, or cutting planes for cutting plane methods. In this paper we describe methods for producing such inequalities and develop some underlying theory.

        We will attempt to outline our general approach, taking the pure integer case first.

Consider a pure integer problem
(1) Ax = b, x 2 0
in which A is an mx(m+n) matrix, x is an integer m+n vector, and b an m-vector. If we consider a basis B (in most applications this w i l l be an optimal basis) we can write (1) as

Bx + N x N = b x B > O , x N > O

B

where x is the m-vector of basic variables and % the non-basic n-vector.

B


The usual transformed matrix [ l , pages 75-80] corresponds to the equations

Taking the ith row we have

[This page contains 1 picture or other non-text object]

Page 3 of 108

        We can form a new but related equation by reducing a l l co- efficients modulo 1 and replacing the equality by eiuivalence modulo 1. This yields

(mod 1).

Now any integer vector (y,z) satisfying (2) automatically satisfies (3), so that any inequality

which is satisfied by all solutions z to (3) is also satisfied by all solutions to (2) , i.


e.

holds for any integer vector (y ,z) satisfying (2).

        The approach of this paper is to develop inequalities valid for all solutions to (2) by obtaining those valid for all solutions to the simpler equations like (3).

        More generally, we can proceed as follows, let IJJ be a linear mapping sending the points of m-space into some other topological group S with addition. If we have an equati.on (like (2))

in which the C. and C are m vectors, we can obtain a new equation by

3 0

using the mapping Q to obtain, by linearity,

[This page contains 1 picture or other non-text object]

Page 4 of 108

which is an equation involving a set of group elements in S,the elements $(C.x.). For integer x $(C.x.) = dJ(C.)x so equivalent

          J J j' J J J j
group equations are

In the discussion leading up to equation (3) the C. were the columns

J

of the matrix (1,N') and I) was the mapping that sends an m vector into the fractional part of its ith coordinate. The group S was the unit interval with addition modulo 1. Equation (3) was the equation (6).

Again, if IT-x 2 .rr holds for all integer x satisfying (5) or

0

(6) it holds for integer x satisfying (4).

In this paper we study equations such as (6) and...