{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T01:44:56Z","timestamp":1764812696748},"reference-count":26,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5184,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The NP\u2010complete separation problem for the knapsack polyhedron \ud835\udcc5 is formulated as a side\u2010constrained 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 \ud835\udcc5 and that the dual polyhedron can be projected onto an appropriate subspace to yield the polar of \ud835\udcc5. Practical consequences of the formulation are discussed.<\/jats:p>","DOI":"10.1002\/net.3230220507","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:48:42Z","timestamp":1178974122000},"page":"503-514","source":"Crossref","is-referenced-by-count":7,"title":["A pseudopolynomial network flow formulation for exact knapsack separation"],"prefix":"10.1002","volume":"22","author":[{"given":"E.","family":"Andrew Boyd","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"529","volume-title":"Handbooks in Operations Research and Management Science","author":"Ahuja R. K.","year":"1989"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130405"},{"key":"e_1_2_1_4_2","unstructured":"E.BalasandW. R.Pulleyblank The perfectly matchable subgraph polytope of an arbitrary graph. Research Report 87470\u2010OR. Institute for Operations Research Bonn University (1987)."},{"key":"e_1_2_1_5_2","first-page":"13","volume-title":"Mathematical Programming","author":"Balas E.","year":"1984"},{"key":"e_1_2_1_6_2","unstructured":"M. O.Ball W. G.Liu andW. R.Pulleyblank Two terminal Steiner tree polyhedra. Research Report CORR 87\u201033. Department of Combinatorics and Optimization University of Waterloo (1987)."},{"key":"e_1_2_1_7_2","unstructured":"F.Barahona On cuts and matchings in planar graphs. Research Report 88503\u2010OR. Institute for Operations Research Bonn University (1988)."},{"key":"e_1_2_1_8_2","unstructured":"F.Barahona Reducing matching to polynomial size linear programming. Research Report CORR 88\u201051. Department of Combinatorics and Optimization University of Waterloo (1988)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.30.10.1255"},{"key":"e_1_2_1_10_2","unstructured":"E. A.Boyd Fenchel cutting planes for integer programs. Technical Report TR90\u20103. Department of Mathematical Sciences Rice University (1990)."},{"key":"e_1_2_1_11_2","unstructured":"E. A.Boyd Generating Fenchel cutting planes for knapsack polyhedra. Technical Report TR90\u201020. Department of Mathematical Sciences Rice University (1990)."},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.31.5.803"},{"key":"e_1_2_1_13_2","volume-title":"Solving multi\u2010item capacitated lot\u2010sizing problems using variable redefinition","author":"Eppen G. D.","year":"1985"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121015"},{"key":"e_1_2_1_16_2","unstructured":"W. G.Liu Extended formulations and polyhedral projection. PhD Thesis Department of Combinatorics and Optimization University of Waterloo (1988)."},{"key":"e_1_2_1_17_2","first-page":"185","article-title":"The Steiner in graphs","volume":"33","author":"Maculan N.","year":"1987","journal-title":"Ann. Discrete Math."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90028-N"},{"key":"e_1_2_1_19_2","unstructured":"R. K.Martin R. L.Rardin andB. A.Campbell Polyhedral characterization of discrete dynamic programming. Research Report CC\u201087\u201024. Institute for Interdisciplinary Engineering Studies Purdue University (1987)."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580738"},{"key":"e_1_2_1_22_2","first-page":"529","volume-title":"Handbooks in Operations Research and Management Science","author":"Pulleyblank W. R.","year":"1989"},{"key":"e_1_2_1_23_2","unstructured":"R. L.RardinandL. A.Wolsey Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems.Research Report CC\u201090\u20102.Institute for Interdisciplinary Engineering Studies Purdue University (1990)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589102"},{"key":"e_1_2_1_25_2","doi-asserted-by":"crossref","unstructured":"M.Yannakakis Expressing combinatorial optimization problems by linear programs. Research report AT&T Bell Laboratories (1988).","DOI":"10.1145\/62212.62232"},{"key":"e_1_2_1_26_2","volume-title":"Easily computable facets of the knapsack polytope","author":"Zemel E.","year":"1987"},{"key":"e_1_2_1_27_2","unstructured":"E.ZemelandD.Hartvigsen On the complexity of lifted inequalities for the knapsack problem.Working Paper 740.Department of Managerial Economics and Decision Sciences Northwestern University (1987)."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220507","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T01:34:15Z","timestamp":1698111255000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,8]]},"references-count":26,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1992,8]]}},"alternative-id":["10.1002\/net.3230220507"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220507","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,8]]}}}