{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T04:42:59Z","timestamp":1781930579995,"version":"3.54.5"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T00:00:00Z","timestamp":1246492800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s10107-009-0295-4","type":"journal-article","created":{"date-parts":[[2009,7,1]],"date-time":"2009-07-01T08:58:44Z","timestamp":1246438724000},"page":"49-72","source":"Crossref","is-referenced-by-count":245,"title":["Modeling disjunctive constraints with a logarithmic number of binary variables and constraints"],"prefix":"10.1007","volume":"128","author":[{"given":"Juan Pablo","family":"Vielma","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George L.","family":"Nemhauser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,7,2]]},"reference":[{"key":"295_CR1","doi-asserted-by":"crossref","unstructured":"Appleget, J.A., Wood, R.K.: Explicit-constraint branching for solving mixed-integer programs. In: Laguna, M., Gonz\u00e1lez, J.L. (eds.) Computing Tools for Modeling, Optimization, and Simulation: Interfaces in Computer Science and Operations Research, Operations Research Computer Science Interfaces Series, vol. 12, pp. 245\u2013261. Kluwer, Dordrecht (2000)","DOI":"10.1007\/978-1-4615-4567-5_14"},{"key":"295_CR2","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1002\/net.3230190202","volume":"19","author":"A. Balakrishnan","year":"1989","unstructured":"Balakrishnan A., Graves S.C.: A composite algorithm for a concave-cost network flow problem. Networks 19, 175\u2013202 (1989)","journal-title":"Networks"},{"key":"295_CR3","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.: Disjunctive programming. Ann. Discrete Math. 5, 3\u201351 (1979)","journal-title":"Ann. Discrete Math."},{"key":"295_CR4","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1137\/0606047","volume":"6","author":"E. Balas","year":"1985","unstructured":"Balas E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discrete Methods 6, 466\u2013486 (1985)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"295_CR5","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0167-6377(88)90058-2","volume":"7","author":"E. Balas","year":"1988","unstructured":"Balas E.: On the convex-hull of the union of certain polyhedra. Oper. Res. Lett. 7, 279\u2013283 (1988)","journal-title":"Oper. Res. Lett."},{"key":"295_CR6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0166-218X(98)00136-X","volume":"89","author":"E. Balas","year":"1998","unstructured":"Balas E.: Disjunctive programming: properties of the convex hull of feasible points. Discrete Appl. Math. 89, 3\u201344 (1998)","journal-title":"Discrete Appl. Math."},{"key":"295_CR7","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s10479-005-3969-1","volume":"140","author":"E. Balas","year":"2005","unstructured":"Balas E.: Projection, lifting and extended formulation in integer and combinatorial optimization. Ann. Oper. Res. 140, 125\u2013161 (2005)","journal-title":"Ann. Oper. Res."},{"key":"295_CR8","first-page":"447","volume-title":"OR 69: Proceedings of the Fifth International Conference on Operational Research","author":"E.M.L. Beale","year":"1970","unstructured":"Beale E.M.L., Tomlin J.A.: Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. In: Lawrence, J. (eds) OR 69: Proceedings of the Fifth International Conference on Operational Research, pp. 447\u2013454. Tavistock Publications, London (1970)"},{"key":"295_CR9","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1137\/0131054","volume":"31","author":"C. Blair","year":"1976","unstructured":"Blair C.: 2 Rules for deducing valid inequalities for 0\u20131 problems. SIAM J. Appl. Math. 31, 614\u2013617 (1976)","journal-title":"SIAM J. Appl. Math."},{"key":"295_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01588775","volume":"49","author":"C. Blair","year":"1990","unstructured":"Blair C.: Representation for multiple right-hand sides. Math. Program. 49, 1\u20135 (1990)","journal-title":"Math. Program."},{"key":"295_CR11","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF02207700","volume":"13","author":"J.M. Carnicer","year":"1996","unstructured":"Carnicer J.M., Floater M.S.: Piecewise linear interpolants to lagrange and hermite convex scattered data. Numer. Algorithms 13, 345\u2013364 (1996)","journal-title":"Numer. Algorithms"},{"key":"295_CR12","unstructured":"Christof, T., Loebel, A.: PORTA\u2014POlyhedron Representation Transformation Algorithm, version 1.3. Available at http:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/PORTA\/"},{"key":"295_CR13","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1016\/j.disopt.2005.06.001","volume":"2","author":"D. Coppersmith","year":"2005","unstructured":"Coppersmith D., Lee J.: Parsimonious binary-encoding in integer programming. Discrete Optim. 2, 190\u2013200 (2005)","journal-title":"Discrete Optim."},{"key":"295_CR14","doi-asserted-by":"crossref","first-page":"1268","DOI":"10.1287\/mnsc.49.9.1268.16570","volume":"49","author":"K.L. Croxton","year":"2003","unstructured":"Croxton K.L., Gendron B., Magnanti T.L.: A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems. Manage. Sci. 49, 1268\u20131273 (2003)","journal-title":"Manage. Sci."},{"key":"295_CR15","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/opre.5.2.266","volume":"5","author":"G.B. Dantzig","year":"1957","unstructured":"Dantzig G.B.: Discrete-variable extremum problems. Oper. Res. 5, 266\u2013277 (1957)","journal-title":"Oper. Res."},{"key":"295_CR16","doi-asserted-by":"crossref","first-page":"30","DOI":"10.2307\/1905292","volume":"28","author":"G.B. Dantzig","year":"1960","unstructured":"Dantzig G.B.: On the significance of solving linear-programming problems with some integer variables. Econometrica 28, 30\u201344 (1960)","journal-title":"Econometrica"},{"key":"295_CR17","volume-title":"Linear Programming and Extensions","author":"G.B. Dantzig","year":"1963","unstructured":"Dantzig G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)"},{"key":"295_CR18","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1017\/S0269888901000030","volume":"16","author":"I.R. Farias de Jr","year":"2001","unstructured":"de Farias I.R. Jr., Johnson E.L., Nemhauser G.L.: Branch-and-cut for combinatorial optimization problems without auxiliary binary variables. Knowl. Eng. Rev. 16, 25\u201339 (2001)","journal-title":"Knowl. Eng. Rev."},{"key":"295_CR19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0012-365X(76)90091-1","volume":"16","author":"T. Ibaraki","year":"1976","unstructured":"Ibaraki T.: Integer programming formulation of combinatorial optimization problems. Discrete Math. 16, 39\u201352 (1976)","journal-title":"Discrete Math."},{"key":"295_CR20","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.: Cutting plane theory: disjunctive methods. Ann. Discrete Math. 1, 293\u2013330 (1977)","journal-title":"Ann. Discrete Math."},{"key":"295_CR21","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.: Representability in mixed integer programming 1: characterization results. Discrete Appl. Math. 17, 223\u2013243 (1987)","journal-title":"Discrete Appl. Math."},{"key":"295_CR22","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/0377-2217(88)90013-6","volume":"36","author":"R.G. Jeroslow","year":"1988","unstructured":"Jeroslow R.G.: A simplification for some disjunctive formulations. Eur. J. Oper. Res. 36, 116\u2013121 (1988)","journal-title":"Eur. J. Oper. Res."},{"key":"295_CR23","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0166-218X(89)90023-1","volume":"23","author":"R.G. Jeroslow","year":"1989","unstructured":"Jeroslow R.G.: Representability of functions. Discrete Appl. Math. 23, 125\u2013137 (1989)","journal-title":"Discrete Appl. Math."},{"key":"295_CR24","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BFb0121015","volume":"22","author":"R.G. Jeroslow","year":"1984","unstructured":"Jeroslow R.G., Lowe J.K.: Modeling with integer variables. Math. Program. Study 22, 167\u2013184 (1984)","journal-title":"Math. Program. Study"},{"key":"295_CR25","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1057\/jors.1985.67","volume":"36","author":"R.G. Jeroslow","year":"1985","unstructured":"Jeroslow R.G., Lowe J.K.: Experimental results on the new techniques for integer programming formulations. J. Oper. Res. Soc. 36, 393\u2013403 (1985)","journal-title":"J. Oper. Res. Soc."},{"key":"295_CR26","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/S0167-6377(03)00059-2","volume":"32","author":"A.B. Keha","year":"2004","unstructured":"Keha A.B., de Farias I.R., Nemhauser G.L.: Models for representing piecewise linear cost functions. Oper. Res. Lett. 32, 44\u201348 (2004)","journal-title":"Oper. Res. Lett."},{"key":"295_CR27","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1287\/opre.1060.0277","volume":"54","author":"A.B. Keha","year":"2006","unstructured":"Keha A.B., de Farias I.R., Nemhauser G.L.: A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization. Oper. Res. 54, 847\u2013858 (2006)","journal-title":"Oper. Res."},{"key":"295_CR28","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1023\/A:1014804110661","volume":"6","author":"J. Lee","year":"2002","unstructured":"Lee J.: All-different polytopes. J. Comb. Optim. 6, 335\u2013352 (2002)","journal-title":"J. Comb. Optim."},{"key":"295_CR29","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1287\/ijoc.1060.0178","volume":"19","author":"J. Lee","year":"2007","unstructured":"Lee J., Margot F.: On a binary-encoded ilp coloring formulation. INFORMS J. Comput. 19, 406\u2013415 (2007)","journal-title":"INFORMS J. Comput."},{"key":"295_CR30","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/S0166-218X(00)00216-X","volume":"108","author":"J. Lee","year":"2001","unstructured":"Lee J., Wilson D.: Polyhedral methods for piecewise-linear functions I: the lambda method. Discrete Appl. Math. 108, 269\u2013285 (2001)","journal-title":"Discrete Appl. Math."},{"key":"295_CR31","unstructured":"Lowe, J.K.: Modelling with Integer Variables. Ph.D. Thesis, Georgia Institute of Technology (1984)"},{"key":"295_CR32","first-page":"234","volume-title":"IPCO, Lecture Notes in Computer Science, vol. 3064","author":"T.L. Magnanti","year":"2004","unstructured":"Magnanti T.L., Stratila D.: Separable concave optimization approximately equals piecewise linear optimization. In: Bienstock, D., Nemhauser, G.L. (eds) IPCO, Lecture Notes in Computer Science, vol. 3064, pp. 234\u2013243. Springer, Heidelberg (2004)"},{"key":"295_CR33","doi-asserted-by":"crossref","first-page":"84","DOI":"10.2307\/1907744","volume":"25","author":"H.M. Markowitz","year":"1957","unstructured":"Markowitz H.M., Manne A.S.: On the solution of discrete programming-problems. Econometrica 25, 84\u2013110 (1957)","journal-title":"Econometrica"},{"key":"295_CR34","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/s10107-005-0665-5","volume":"105","author":"A. Martin","year":"2006","unstructured":"Martin A., Moller M., Moritz S.: Mixed integer models for the stationary case of gas network optimization. Math. Program. 105, 563\u2013582 (2006)","journal-title":"Math. Program."},{"key":"295_CR35","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01585518","volume":"7","author":"R.R. Meyer","year":"1974","unstructured":"Meyer R.R.: On the existence of optimal solutions to integer and mixed-integer programming problems. Math. Program. 7, 223\u2013235 (1974)","journal-title":"Math. Program."},{"key":"295_CR36","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01262932","volume":"16","author":"R.R. Meyer","year":"1975","unstructured":"Meyer R.R.: Integer and mixed-integer programming models\u2014general properties. J. Optim. Theory Appl. 16, 191\u2013206 (1975)","journal-title":"J. Optim. Theory Appl."},{"key":"295_CR37","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0012-365X(76)90145-X","volume":"16","author":"R.R. Meyer","year":"1976","unstructured":"Meyer R.R.: Mixed integer minimization models for piecewise-linear functions of a single variable. Discrete Math. 16, 163\u2013171 (1976)","journal-title":"Discrete Math."},{"key":"295_CR38","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1002\/nav.3800280109","volume":"28","author":"R.R. Meyer","year":"1981","unstructured":"Meyer R.R.: A theoretical and computational comparison of equivalent mixed-integer formulations. Nav. Res. Logist. 28, 115\u2013131 (1981)","journal-title":"Nav. Res. Logist."},{"key":"295_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0167-6377(00)00028-6","volume":"27","author":"M. Padberg","year":"2000","unstructured":"Padberg M.: Approximating separable nonlinear functions via mixed zero-one programs. Oper. Res. Lett. 27, 1\u20135 (2000)","journal-title":"Oper. Res. Lett."},{"key":"295_CR40","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0167-6377(01)00063-3","volume":"28","author":"H.D. Sherali","year":"2001","unstructured":"Sherali H.D.: On mixed-integer zero-one representations for separable lower-semicontinuous piecewise-linear functions. Oper. Res. Lett. 28, 155\u2013160 (2001)","journal-title":"Oper. Res. Lett."},{"key":"295_CR41","doi-asserted-by":"crossref","unstructured":"Sherali, H.D., Shetty, C.M.: Optimization with Disjunctive Constraints. Lecture Notes in Economics and Mathematical Systems, vol. 181. Springer, Heidelberg (1980)","DOI":"10.1007\/978-3-642-48794-1"},{"key":"295_CR42","unstructured":"Shields, R.: Personal communication (2007)"},{"key":"295_CR43","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/B978-0-12-398050-2.50021-9","volume-title":"Fixed Points: Algorithms and Applications","author":"M.J. Todd","year":"1977","unstructured":"Todd M.J.: Union jack triangulations. In: Karamardian, S. (eds) Fixed Points: Algorithms and Applications, pp. 315\u2013336. Academic Press, New York (1977)"},{"key":"295_CR44","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/S0304-0208(08)73476-5","volume-title":"Studies on Graphs and Discrete Programming, Annals of Discrete Mathematics, vol. 11","author":"J.A. Tomlin","year":"1981","unstructured":"Tomlin J.A.: A suggested extension of special ordered sets to non-separable non-convex programming problems. In: Hansen, P. (eds) Studies on Graphs and Discrete Programming, Annals of Discrete Mathematics, vol. 11, pp. 359\u2013370. North Holland, Amsterdam (1981)"},{"key":"295_CR45","doi-asserted-by":"crossref","unstructured":"Vielma, J.P., Ahmed, S., Nemhauser, G.L.: Mixed-integer models for nonseparable piecewise linear optimization: unifying framework and extensions. Oper. Res. (to appear) (2009)","DOI":"10.1287\/opre.1090.0721"},{"key":"295_CR46","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/j.disopt.2007.07.001","volume":"5","author":"J.P. Vielma","year":"2008","unstructured":"Vielma J.P., Keha A.B., Nemhauser G.L.: Nonconvex, lower semicontinuous piecewise linear optimization. Discrete Optim. 5, 467\u2013488 (2008)","journal-title":"Discrete Optim."},{"key":"295_CR47","first-page":"199","volume-title":"IPCO, Lecture Notes in Computer Science, vol. 5035","author":"J.P. Vielma","year":"2008","unstructured":"Vielma J.P., Nemhauser G.L.: Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds) IPCO, Lecture Notes in Computer Science, vol. 5035, pp. 199\u2013213. Springer, Hiedelberg (2008)"},{"key":"295_CR48","doi-asserted-by":"crossref","first-page":"1171","DOI":"10.1287\/opre.15.6.1171","volume":"15","author":"L.J. Watters","year":"1967","unstructured":"Watters L.J.: Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper. Res. 15, 1171\u20131174 (1967)","journal-title":"Oper. Res."},{"key":"295_CR49","unstructured":"Wilf., H.S.: Combinatorial algorithms\u2014an update, CBMS-NSF regional conference series in applied mathematics, vol. 55. Society for Industrial and Applied Mathematics (1989)"},{"key":"295_CR50","unstructured":"Wilson, D.: Polyhedral methods for piecewise-linear functions. Ph.D. Thesis, University of Kentucky (1998)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-009-0295-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-009-0295-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-009-0295-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T05:50:06Z","timestamp":1559109006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-009-0295-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,2]]},"references-count":50,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["295"],"URL":"https:\/\/doi.org\/10.1007\/s10107-009-0295-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,2]]}}}