Back

G-91-17

Number of Fractions in LP Solutions for GAP Like Problems

and

BibTeX reference

It is an old observation that for the Generalized Assignment Problem (GAP) a Linear Programming (LP) relaxation introduces only few fractions in the solution. More precisely, in the GAP with n variables and m constraints, provided n &lt 2p, a basic solution has at most 2p fractional values; we call it the limited fractions property. It is then natural to ask whether this property characterizes the GAP, and, if not, what class of ILP problems it characterizes. We resolve this issue by showing that the limited fractions property of LP relaxations does indeed characterize a class of ILP, called here k-binary systems, which includes the GAP as a proper subset.

, 9 pages

This cahier was revised in April 1992