Eva K. Lee
May, 1993
The 0/1 knapsack equality polytope is, by definition, the convex hull of 0/1 solutions of a single linear equation. A special form of this polytope --- where the defining linear equation has nonnegative integer coefficients and the number of variables having coefficient one is greater than the right-hand-side --- is considered. Equality constraints of this form arose in a real-world application of integer programming to a truck dispatching scheduling problem. Families of facet defining inequalities for this polytope are identified, and in two cases a complete linear inequality representation is obtained.
Keywords: knapsack polytope, integer programming, polyhedral theory, branch-and-cut
Abbreviated title: Knapsack equality polytopes