Browse Prior Art Database

Subadditive Algorithm for the Group Problem of Integer Programming

IP.com Disclosure Number: IPCOM000078961D
Original Publication Date: 1973-Apr-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 3 page(s) / 36K

Publishing Venue

IBM

Related People

Burdet, CA: AUTHOR [+2]

Abstract

The pure integer programming (IP) problem is: x(j)>/-0 and integer, j = 1,...,n (IP) Ax = b cx = z(min). Most solution methods for IP begin by solving the associated linear program (LP) x(j)>/-0 (LP) A(x) = b cx = z(min) obtained by deleting the integer requirements on x(j). The algorithm given here begins with a solution to LP and generates a cutting plane to adjoin to LP, or alternatively a lower bound on z subject to IP. This latter bound is useful in branch-and-bound methods, which involve successive solutions of problems of the form LP. The algorithm employs construction of a subadditive function S, an enumeration set E, and a constraint set F.

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

Page 1 of 3

Subadditive Algorithm for the Group Problem of Integer Programming

The pure integer programming (IP) problem is: x(j)>/-0 and integer, j = 1,...,n (IP) Ax = b cx = z(min). Most solution methods for IP begin by solving the associated linear program (LP) x(j)>/-0 (LP) A(x) = b cx = z(min) obtained by deleting the integer requirements on x(j). The algorithm given here begins with a solution to LP and generates a cutting plane to adjoin to LP, or alternatively a lower bound on z subject to IP. This latter bound is useful in branch-and-bound methods, which involve successive solutions of problems of the form LP. The algorithm employs construction of a subadditive function S, an enumeration set E, and a constraint set F.

The algorithm requires for input the solution of LP in the following, updated form: x(J) + Nx(K) = b' c'(K)x(K) = z-z(o), where x(J) are the optimal, basic variables and x(K) are the nonbasic variables. Let F be the set of columns of N, reduced modulo one. Denote the j/th/ element of F by f/j/. Let c(j) be the costs coefficient c'(k) corresponding to the column of N giving f/j/. Let f/o/ denote b', reduced modulo one. Let E be the set of columns initially consisting of the single column e'=0 consisting of m zero's. Let d(1)=0.

Each element f/j/ of F or e/k/ of E is a column vector, whose i/th/ component is denoted f/k/ or e/k/(i). The cost coefficients c(j) or d(k) correspond to f/j/ or e/ki/, respectively.

The steps of the algorithm are shown in the flow chart. A function S(f) for 0</-f(i)</-1, i = 1,...,m is used. S is defined in terms of E and d by

(Image Omitted)

where U(x) denotes the fractional part of x and p(i),q(i) are parameters. Here, U(x) is defined to be 1-U(x). The p(i) and q(i) are adjusted in CHANGES to increase S(f/o/) subject to S(f/j/)</-c.. In this problem, pi and q(i) enter in a nonconvex way.

However, gradient methods can be used to obtain a local optima. Initially, the best values of p(i) and q(i) are ones which...