dc.identifier.citation | Operations Research, XVII,4, (July-Aug 1969), 680-684. Supplement Operations Research, XVIII,3, (May-June 1970), 564-565 | en |
dc.description.abstract | Consider the zero-one integer programming problem Pi:minimize Z=c'x
subject to Axrb, O<xj<1, xi=O or 1, j=l, 2, **., n, where A is an mXn
matrix, c'= (ci, * * *, ca), x'= (xi, *-* *, x), and b is an mXl vector with b'=
(bi, **, bin). Assume the elements of A, b, c are all rational. This paper
characterizes the feasible solutions of P1, shows that P1 is equivalent to
a problem of minimizing a concave quadratic objective function over a
convex set, and applies a method developed by TuT to solve such a problem
to yield a procedure for the zero-one integer programming problem. | |