Premium
A pseudopolynomial network flow formulation for exact knapsack separation
Author(s) -
Andrew Boyd E.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220507
Subject(s) - knapsack problem , polyhedron , subspace topology , flow (mathematics) , yield (engineering) , mathematics , combinatorics , mathematical optimization , dual (grammatical number) , computer science , separation (statistics) , dual polyhedron , physics , geometry , mathematical analysis , art , statistics , literature , thermodynamics
The NP‐complete separation problem for the knapsack polyhedron 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 and that the dual polyhedron can be projected onto an appropriate subspace to yield the polar of . Practical consequences of the formulation are discussed.