{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:34:13Z","timestamp":1774978453662,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2005,11,1]],"date-time":"2005-11-01T00:00:00Z","timestamp":1130803200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2005,11]]},"DOI":"10.1007\/s10479-005-3969-1","type":"journal-article","created":{"date-parts":[[2005,11,26]],"date-time":"2005-11-26T12:12:53Z","timestamp":1133007173000},"page":"125-161","source":"Crossref","is-referenced-by-count":39,"title":["Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization"],"prefix":"10.1007","volume":"140","author":[{"given":"Egon","family":"Balas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3969_CR1","doi-asserted-by":"crossref","unstructured":"Balas, E. (1998). \u201cDisjunctive Programming: Properties of the Convex Hull of Feasible Points.\u201d Invited paper, with a foreword by G. Cornu\u00e9jols and W. Pulleyblank, Discrete Applied Mathematics 89, 3\u201344. (Originally MSRR# 348, Carnegie Mellon University, July 1974).","DOI":"10.1016\/S0166-218X(98)00136-X"},{"key":"3969_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0167-5060(08)70342-X","volume":"5","author":"E. Balas","year":"1979","unstructured":"Balas, E. (1979). \u201cDisjunctive Programming.\u201d Annals of Discrete Mathematics 5, 3\u201351.","journal-title":"Annals of Discrete Mathematics"},{"key":"3969_CR3","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/0606047","volume":"6","author":"E. Balas","year":"1985","unstructured":"Balas, E. (1985). \u201cDisjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems.\u201d SIAM Journal on Algebraic and Discrete Methods 6, 466\u2013485.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"3969_CR4","first-page":"35","volume":"60","author":"E. Balas","year":"1987","unstructured":"Balas, E. (1987). \u201cThe Assignable Subgraph Polytope of a Directed Graph.\u201d Congressus Numerantium 60, 35\u201342.","journal-title":"Congressus Numerantium"},{"key":"3969_CR5","first-page":"19","volume":"79","author":"E. Balas","year":"1997","unstructured":"Balas, E. (1997). \u201cA Modified Lift-and-Project Procedure.\u201d Mathematical Programming 79, 19\u201331.","journal-title":"Mathematical Programming"},{"key":"3969_CR6","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1023\/A:1018368920203","volume":"10","author":"E. Balas","year":"1998","unstructured":"Balas, E. (1998). \u201cProjection with a Minimal System of Inequalities.\u201d Computational Optimization and Applications 10, 189\u2013193.","journal-title":"Computational Optimization and Applications"},{"key":"3969_CR7","doi-asserted-by":"crossref","unstructured":"Balas, E. (2001). \u201cProjection and Lifting in Combinatorial Optimization.\u201d In M. J\u00fcnger and D. Naddef (eds.), Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions, LNCS 2241, Springer, pp. 26\u201356.","DOI":"10.1007\/3-540-45586-8_2"},{"key":"3969_CR8","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01581273","volume":"58","author":"E. Balas","year":"1993","unstructured":"Balas, E., S. Ceria, and G. Cornu\u00e9jols. (1993). \u201cA Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs.\u201d Mathematical Programming 58, 295\u2013324.","journal-title":"Mathematical Programming"},{"key":"3969_CR9","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1287\/mnsc.42.9.1229","volume":"42","author":"E. Balas","year":"1996","unstructured":"Balas, E., S. Ceria, and G. Cornu\u00e9jols. (1996). \u201cMixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework.\u201d Management Science 42, 1229\u20131246.","journal-title":"Management Science"},{"key":"3969_CR10","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1090\/dimacs\/026\/02","volume-title":"Clique, Coloring and Satisfiability: The Second DIMACS Challenge","author":"E. Balas","year":"1996","unstructured":"Balas, E., S. Ceria, G. Cornu\u00e9jols, and G. Pataki. (1996). \u201cPolyhedral Methods for the Maximum Clique Problem.\u201d In D. Johnson and M. Trick (eds.), Clique, Coloring and Satisfiability: The Second DIMACS Challenge. The American Mathematical Society, Providence, RI, pp. 11\u201327."},{"key":"3969_CR11","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/0377-2217(80)90106-X","volume":"4","author":"E. Balas","year":"1980","unstructured":"Balas, E. and R.G. Jeroslow. (1980). \u201cStrengthening Cuts for Mixed Integer Programs.\u201d European Journal of Operational Research 4, 224\u2013234.","journal-title":"European Journal of Operational Research"},{"key":"3969_CR12","unstructured":"Balas, E. and J.B. Mazzola. (1984). \u201cNonlinear 0-1 Programming: I. Linearization Techniques, II. Dominance Relations and Algorithms.\u201d Mathematical Programming 30, 1\u201321 and 22\u201345."},{"key":"3969_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0166-218X(98)00096-1","volume":"87","author":"E. Balas","year":"1998","unstructured":"Balas, E. and M. Oosten. (1998). \u201cOn the Dimension of Projected Polyhedra.\u201d Discrete Applied Mathematics 87, 1\u20139.","journal-title":"Discrete Applied Mathematics"},{"key":"3969_CR14","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1002\/1097-0037(200008)36:1<34::AID-NET4>3.0.CO;2-2","volume":"36","author":"E. Balas","year":"2000","unstructured":"Balas, E. and M. Oosten. (2000). \u201cThe Cycle Polytope of a Directed Graph.\u201d Networks 36, 34\u201346.","journal-title":"Networks"},{"key":"3969_CR15","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10107-002-0317-y","volume":"94","author":"E. Balas","year":"2003","unstructured":"Balas, E. and M. Perregaard. (2003). \u201cA Precise Correspondence Between Lift-and-Project Cuts, Simple Disjunctive Cuts, and Mixed Integer Gomory Cuts for 0-1 Programming.\u201d Mathematical Programming B 94, 221\u2013245.","journal-title":"Mathematical Programming B"},{"key":"3969_CR16","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1002\/net.3230130405","volume":"13","author":"E. Balas","year":"1983","unstructured":"Balas, E. and W.R. Pulleyblank. (1983). \u201cThe Perfectly Matchable Subgraph Polytope of a Bipartite Graph.\u201d Networks 13, 495\u2013518.","journal-title":"Networks"},{"key":"3969_CR17","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02125345","volume":"9","author":"E. Balas","year":"1989","unstructured":"Balas, E. and W.R. Pulleyblank. (1989). \u201cThe Perfectly Matchable Subgraph Polytope of an Arbitrary Graph.\u201d Combinatorica 9, 321\u2013337.","journal-title":"Combinatorica"},{"key":"3969_CR18","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF01587096","volume":"44","author":"E. Balas","year":"1989","unstructured":"Balas, E., J. Tama and J. Tind. (1989). \u201cSequential Convexification in Reverse Convex and Disjunctive Programming.\u201d Mathematical Programming 44, 337\u2013350.","journal-title":"Mathematical Programming"},{"key":"3969_CR19","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0377-2217(90)90419-C","volume":"48","author":"N. Beaumont","year":"1990","unstructured":"Beaumont, N. (1990). \u201cAn Algorithm for Disjunctive Programming.\u201d European Journal of Operational Research 48, 362\u2013371.","journal-title":"European Journal of Operational Research"},{"key":"3969_CR20","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1023\/A:1018960631213","volume":"90","author":"R. Bixby","year":"1999","unstructured":"Bixby, R., W. Cook, A. Cox, and E. Lee. (1999). \u201cComputational Experience with Parallel Mixed Integer Programming in a Distributed Environment.\u201d Annals of Operations Research 90, 19\u201345.","journal-title":"Annals of Operations Research"},{"key":"3969_CR21","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1137\/0131054","volume":"31","author":"C. Blair","year":"1976","unstructured":"Blair, C. (1976). \u201cTwo Rules for Deducing Valid Inequalities for 0-1 Programs.\u201d SIAM Journal of Applied Mathematics 31, 614\u2013617.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"3969_CR22","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/0166-218X(80)90037-2","volume":"2","author":"C. Blair","year":"1980","unstructured":"Blair, C. (1980). \u201cFacial Disjunctive Programs and Sequences of Cutting Planes.\u201d Discrete Applied Mathematics 2, 173\u2013180.","journal-title":"Discrete Applied Mathematics"},{"key":"3969_CR23","doi-asserted-by":"crossref","unstructured":"Ceria, S. and G. Pataki. (1998). \u201cSolving Integer and Disjunctive Programs by Lift-and-Project.\u201d In R.E. Bixby, E.A. Boyd, and R.Z. Rios-Mercado (eds.), IPCO VI, Lecture Notes in Computer Science, 1412. Springer, pp. 271\u2013283.","DOI":"10.1007\/3-540-69346-7_21"},{"key":"3969_CR24","unstructured":"Ceria, S. and J. Soares. (1997). \u201cDisjunctive Cuts for Mixed 0-1 Programming: Duality and Lifting.\u201d GSB, Columbia University."},{"key":"3969_CR25","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/s101070050106","volume":"86","author":"S. Ceria","year":"1999","unstructured":"Ceria, S. and J. Soares. (1999). \u201cConvex Programming for Disjunctive Convex Optimization.\u201d Mathematical Programming 86, 595\u2013614.","journal-title":"Mathematical Programming"},{"key":"3969_CR26","first-page":"393","volume":"2","author":"G.B. Dantzig","year":"1954","unstructured":"Dantzig, G.B., R.D. Fulkerson, and S.M. Johnson. (1954). \u201cSolution of a Large-Scale Traveling Salesman Problem.\u201d Operations Research 2, 393\u2013410.","journal-title":"Operations Research"},{"key":"3969_CR27","first-page":"17","volume":"4","author":"R. Fortet","year":"1960","unstructured":"Fortet, R. (1960). \u201cApplications de l'alg\u00e8bre de Boole en recherche op\u00e9rationnelle.\u201d Revue Francaise de Recherche Op\u00e9rationnelle 4, 17\u201325.","journal-title":"Revue Francaise de Recherche Op\u00e9rationnelle"},{"key":"3969_CR28","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/S0167-5060(08)70741-6","volume":"1","author":"R.G. Jeroslow","year":"1977","unstructured":"Jeroslow, R.G. (1977). \u201cCutting Plane Theory: Disjunctive Methods.\u201d Annals of Discrete Mathematics 1, 293\u2013330.","journal-title":"Annals of Discrete Mathematics"},{"key":"3969_CR29","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(87)90026-6","volume":"17","author":"R.G. Jeroslow","year":"1987","unstructured":"Jeroslow, R.G. (1987). \u201cRepresentability in Mixed Integer Programming I: Characterization Results.\u201d Discrete Applied Mathematics 17, 223\u2013243.","journal-title":"Discrete Applied Mathematics"},{"key":"3969_CR30","unstructured":"Jeroslow, R.G. (1989). \u201cLogic Based Decision Support: Mixed Integer Model Formulation.\u201d Annals of Discrete Mathematics 40."},{"key":"3969_CR31","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BFb0120692","volume":"2","author":"E.L. Johnson","year":"1974","unstructured":"Johnson, E.L. (1974). \u201cThe Group Problem for Mixed-Integer Programming.\u201d Mathematical Programming Study 2, 137\u2013179.","journal-title":"Mathematical Programming Study"},{"key":"3969_CR32","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1023\/A:1011493126498","volume":"5","author":"A. Letchford","year":"2001","unstructured":"Letchford, A. (2001). \u201cOn Disjunctive Cuts for Combinatorial Optimization.\u201d Journal of Combinatorial Optimization 5, 299\u2013317.","journal-title":"Journal of Combinatorial Optimization"},{"key":"3969_CR33","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L. and A. Schrijver. (1991). \u201cCones of Matrices and Set Functions and 0-1 Optimization.\u201d SIAM Journal of Optimization 1, 166\u2013190.","journal-title":"SIAM Journal of Optimization"},{"key":"3969_CR34","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"C.E. Miller","year":"1960","unstructured":"Miller, C.E., A.W. Tucker, and R.A. Zemlin. (1960). \u201cInteger Programming Formulations and Traveling Salesman Problems.\u201d Journal of the ACM 7, 326\u2013329.","journal-title":"Journal of the ACM"},{"key":"3969_CR35","unstructured":"Nemhauser, G. and L. Wolsey. (1986). Integer and Combinatorial Optimization. Wiley."},{"key":"3969_CR36","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01582894","volume":"52","author":"M. Padberg","year":"1991","unstructured":"Padberg, M. and T.-Y. Sung. (1991). \u201cAn Analytical Comparison of Different Formulations of the Traveling Salesman Problem.\u201d Math. Programming 52, 315\u2013357.","journal-title":"Math. Programming"},{"key":"3969_CR37","unstructured":"Pataki, G. (2001). Personal communication, March."},{"key":"3969_CR38","unstructured":"Perregaard, M. (2003). \u201cA Practical Implementation of Lift-and-Project Cuts. A computational exploration of lift-and-project with XPRESS-MP.\u201d Paper presented at the International Symposium on Mathematical Programming, August, Copenhagen."},{"key":"3969_CR39","doi-asserted-by":"crossref","unstructured":"Perregaard, M. and E. Balas. (2001). \u201cGenerating Cuts from Multiple-Term Disjunctions.\u201d In K. Aardal and B. Gerards (eds.), Integer Programming and Combinatorial Optimization (8th IPCO Conference, Utrecht, 2001), LCNS No. 2081, Springer, pp. 318\u2013360.","DOI":"10.1007\/3-540-45535-3_27"},{"key":"3969_CR40","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H. Sherali","year":"1990","unstructured":"Sherali, H. and W. Adams. (1990). \u201cA Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems.\u201d SIAM Journal on Discrete Mathematics 3, 411\u2013430.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"3969_CR41","doi-asserted-by":"crossref","unstructured":"Sherali, H. and C. Shetty. (1980). Optimization with Disjunctive Constraints. Lecture Notes in Economics and Mathematical Systems, 181, Springer.","DOI":"10.1007\/978-3-642-48794-1"},{"key":"3969_CR42","doi-asserted-by":"crossref","unstructured":"Stoer, J. and C. Witzgall. (1970). Convexity and Optimization in Finite Dimensions I. Springer.","DOI":"10.1007\/978-3-642-46216-0"},{"key":"3969_CR43","unstructured":"Stubbs, R.A. and S. Mehrotra. (1996). \u201cA Branch-and-Cut Method for 0-1 Mixed Convex Programming.\u201d Department of Industrial Engineering, Northwestern University."},{"key":"3969_CR44","unstructured":"Thienel, S. (1995). \u201cABACUS: A Branch-and-Cut System.\u201d Doctoral Dissertation, Faculty of Mathematics and The Natural Sciences, University of Cologne."},{"key":"3969_CR45","doi-asserted-by":"crossref","first-page":"2611","DOI":"10.1021\/ie9600856","volume":"35","author":"M. Turkay","year":"1996","unstructured":"Turkay, M. and I.E. Grossmann. (1996). \u201cDisjunctive Programming Techniques for the Optimization of Process Systems with Discontinuous Investment Costs-Multiple Size Regions.\u201d Industrial Engineering Chemical Research 35, 2611\u20132623.","journal-title":"Industrial Engineering Chemical Research"},{"key":"3969_CR46","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/0377-2217(94)90341-7","volume":"72","author":"H.P. Williams","year":"1994","unstructured":"Williams, H.P. (1994). \u201cAn Alternative Explanation of Disjunctive Formulations.\u201d European Journal of Operational Research 72, 200\u2013203.","journal-title":"European Journal of Operational Research"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3969-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-005-3969-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-005-3969-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:59:35Z","timestamp":1559152775000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-005-3969-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,11]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,11]]}},"alternative-id":["3969"],"URL":"https:\/\/doi.org\/10.1007\/s10479-005-3969-1","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,11]]}}}