Facets of Special Knapsack Equality Polytopes
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.
Citable link to this pagehttps://hdl.handle.net/1911/101809
MetadataShow full item record
- CAAM Technical Reports