Groupe d’études et de recherche en analyse des décisions


Number of Fractions in LP Solutions for GAP Like Problems


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

Ce cahier a été révisé en avril 1992