A Pseudopolynomial Network Flow Formulation for Exact Knapsack Separation
Boyd, E. Andrew
The NP-complete separation problem for the knapsack polyhedron P is formulated as a side-constrained network flow problem with a pseudopolynomial number of vertices and edges. It is demonstrated that the primal polyhedron associated with this formulation can be projected onto an appropriate subspace to yield P and that the dual polyhedron can be projected onto an appropriate subspace to yield the polar of P. Practical consequences of the formulation are discussed.
Citable link to this pagehttps://hdl.handle.net/1911/101708
MetadataShow full item record
- CAAM Technical Reports