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 < 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.
Published April 1991 , 9 pages
This cahier was revised in April 1992