{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:36:18Z","timestamp":1759847778135},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T00:00:00Z","timestamp":1403568000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["4OR-Q J Oper Res"],"published-print":{"date-parts":[[2014,9]]},"DOI":"10.1007\/s10288-014-0262-7","type":"journal-article","created":{"date-parts":[[2014,6,23]],"date-time":"2014-06-23T09:51:22Z","timestamp":1403517082000},"page":"201-234","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Deriving compact extended formulations via LP-based separation techniques"],"prefix":"10.1007","volume":"12","author":[{"given":"Giuseppe","family":"Lancia","sequence":"first","affiliation":[]},{"given":"Paolo","family":"Serafini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,6,24]]},"reference":[{"key":"262_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1287\/trsc.3.1.53","volume":"3","author":"L Appelgren","year":"1969","unstructured":"Appelgren L (1969) A column generation algorithm for a ship scheduling problem. Transportation Science 3:53\u201368","journal-title":"Transportation Science"},{"key":"262_CR2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01580600","volume":"60","author":"F Barahona","year":"1993","unstructured":"Barahona F (1993) On cuts and matchings in planar graphs. Math Program 60:53\u201368","journal-title":"Math Program"},{"key":"262_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01587084","volume":"44","author":"F Barahona","year":"1989","unstructured":"Barahona F, J\u00fcnger M, Reinelt G (1989) Experiments in quadratic 0\u20131 programming. Math Program 44:127\u2013137","journal-title":"Math Program"},{"issue":"3","key":"262_CR4","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper Res 46(3):316\u2013329","journal-title":"Oper Res"},{"key":"262_CR5","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program 98:49\u201371","journal-title":"Math Program"},{"key":"262_CR6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1287\/opre.1030.0065","volume":"52","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52:35\u201353","journal-title":"Oper Res"},{"key":"262_CR7","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A Caprara","year":"1999","unstructured":"Caprara A (1999) Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J Discret Math 12:91\u2013110","journal-title":"SIAM J Discret Math"},{"key":"262_CR8","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1287\/ijoc.13.3.224.12631","volume":"13","author":"A Caprara","year":"2001","unstructured":"Caprara A, Lancia G, Ng SK (2001) Sorting permutations by reversal through branch-and-price. Inf J Comput 13:224\u2013244","journal-title":"Inf J Comput"},{"key":"262_CR9","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0196-6774(03)00052-X","volume":"48","author":"A Caprara","year":"2003","unstructured":"Caprara A, Panconesi A, Rizzi R (2003) Packing cycles in undirected graphs. J Algorithms 48:239\u2013256","journal-title":"J Algorithms"},{"key":"262_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1089\/106652704773416876","volume":"11","author":"A Caprara","year":"2004","unstructured":"Caprara A, Carr RD, Lancia G, Walenz B, Istrail S (2004) 1001 optimal PDB structure alignments: integer programming methods for finding the maximum contact map overlap. J Comput Biol 11:27\u201352","journal-title":"J Comput Biol"},{"key":"262_CR11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0167-6377(01)00106-7","volume":"30","author":"RD Carr","year":"2002","unstructured":"Carr RD, Lancia G (2002) Compact vs exponential-size LP relaxations. Oper Res Lett 30:57\u201365","journal-title":"Oper Res Lett"},{"key":"262_CR12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10288-004-0036-8","volume":"2","author":"RD Carr","year":"2004","unstructured":"Carr RD, Lancia G (2004) Compact optimization can outperform separation: a case study in structural proteomics. 4OR 2:221\u2013233","journal-title":"4OR"},{"key":"262_CR13","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0095-8956(75)90041-6","volume":"18","author":"V Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal V (1975) On certain polytopes associated with graphs. J Comb Theory Ser B 18:138\u2013154","journal-title":"J Comb Theory Ser B"},{"key":"262_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10288-010-0122-z","volume":"8","author":"M Conforti","year":"2010","unstructured":"Conforti M, Cornu\u00e9jols G, Zambelli G (2010) Extended formulations in combinatorial optimization. 4OR 8:1\u201348","journal-title":"4OR"},{"key":"262_CR15","volume-title":"Combinatorial optimization","author":"WJ Cook","year":"1998","unstructured":"Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1998) Combinatorial optimization. Wiley, New York"},{"key":"262_CR16","first-page":"393","volume":"2","author":"GB Dantzig","year":"1954","unstructured":"Dantzig GB, Fulkerson R, Johnson SM (1954) Solution of a large-scale traveling salesman problem. Oper Res 2:393\u2013410","journal-title":"Oper Res"},{"key":"262_CR17","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1023\/A:1018952112615","volume":"86","author":"JMV Carvalho de","year":"1999","unstructured":"de Carvalho JMV (1999) Exact solutions of Bin-Packing problems using column generation and branch-and-bound. Ann Oper Res 86:629\u2013665","journal-title":"Ann Oper Res"},{"key":"262_CR18","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0377-2217(02)00124-8","volume":"141","author":"JMV Carvalho de","year":"2002","unstructured":"de Carvalho JMV (2002) LP models for bin packing and cutting stock problems. Eur J Oper Res 141:253\u2013273","journal-title":"Eur J Oper Res"},{"key":"262_CR19","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1080\/10556789408805564","volume":"3","author":"C Simone De","year":"1994","unstructured":"De Simone C, Rinaldi G (1994) A cutting plane algorithm for the max-cut problem. Optim Methods Softw 3:195\u2013214","journal-title":"Optim Methods Softw"},{"key":"262_CR20","doi-asserted-by":"crossref","unstructured":"Fiorini S, Massar S, Pokutta S, Raj Tiwary H, de Wolf R (2012) Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: 44th ACM symposium on theory of computing (STOC 2012), New-York, NY, USA","DOI":"10.1145\/2213977.2213988"},{"key":"262_CR21","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s12532-012-0039-y","volume":"4","author":"M Fischetti","year":"2012","unstructured":"Fischetti M, Monaci M (2012) Cutting plane versus compact formulations for uncertain (integer) linear programs. Math Program Comput 4:239\u2013273","journal-title":"Math Program Comput"},{"key":"262_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/net.10022","volume":"39","author":"M Fischetti","year":"2002","unstructured":"Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees. Networks 39:1\u201313","journal-title":"Networks"},{"key":"262_CR23","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02579262","volume":"6","author":"AMH Gerards","year":"1986","unstructured":"Gerards AMH, Schrijver A (1986) Matrices with the Edmonds\u2013Johnson property. Combinatorica 6:365\u2013379","journal-title":"Combinatorica"},{"key":"262_CR24","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/opre.9.6.849","volume":"9","author":"PC Gilmore","year":"1961","unstructured":"Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting stock problem. Oper Res 9:849\u2013859","journal-title":"Oper Res"},{"key":"262_CR25","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1287\/opre.11.6.863","volume":"11","author":"PC Gilmore","year":"1963","unstructured":"Gilmore PC, Gomory RE (1963) A linear programming approach to the cutting stock problem-II. Oper Res 11:863\u2013888","journal-title":"Oper Res"},{"key":"262_CR26","doi-asserted-by":"crossref","unstructured":"Goldman D, Istrail S, Papadimitriou C (1999) Algorithmic aspects of protein structure similarity. In: Proceedings of the 40th annual IEEE symposium on foundations of computer science, pp 512\u2013522","DOI":"10.1109\/SFFCS.1999.814624"},{"issue":"2","key":"262_CR27","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01586932","volume":"51","author":"M Gr\u00f6tschel","year":"1991","unstructured":"Gr\u00f6tschel M, Holland O (1991) Solution of large-scale travelling salesman problems. Math Program 51(2):141\u2013202","journal-title":"Math Program"},{"key":"262_CR28","volume-title":"Calculating exact ground states of spin glasses: a polyhedral approach Heidelberg Colloquium on Glassy Dynamics","author":"M Gr\u00f6tschel","year":"1987","unstructured":"Gr\u00f6tschel M, J\u00fcnger M, Reinelt G (1987) Calculating exact ground states of spin glasses: a polyhedral approach Heidelberg Colloquium on Glassy Dynamics. Springer, Berlin"},{"key":"262_CR29","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1137\/0203015","volume":"3","author":"TC Hu","year":"1974","unstructured":"Hu TC (1974) Optimum communication spanning trees. SIAM J Comp 3:188\u2013195","journal-title":"SIAM J Comp"},{"key":"262_CR30","unstructured":"Kaibel V (2011) Extended formulations in combinatorial optimization arXiv, preprint arXiv:1104.1023"},{"key":"262_CR31","unstructured":"Kaibel V, Pashkovich K (2011) Constructing extended formulations from reflection relations integer programming and combinatorial optimization XV. In: G\u00fcnl\u00fck O, Woeginger G (eds) Lecture Notes in Computer Science 6655. Springer, Berlin, pp 287\u2013300"},{"key":"262_CR32","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.endm.2011.05.020","volume":"37","author":"G Lancia","year":"2011","unstructured":"Lancia G, Serafini P (2011) An effective compact formulation of the Max Cut problem on sparse graphs. Electron Notes Discret Math 37:111\u2013116","journal-title":"Electron Notes Discret Math"},{"key":"262_CR33","doi-asserted-by":"crossref","unstructured":"Lancia G, Carr RD, Walenz B, Istrail S (2001) 101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. In: Proceedings of 5th ACM international conference on computational molecular biology (RECOMB), pp 193\u2013202","DOI":"10.1145\/369133.369199"},{"key":"262_CR34","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/s10479-010-0832-9","volume":"86","author":"G Lancia","year":"2011","unstructured":"Lancia G, Rinaldi F, Serafini P (2011) A time-indexed LP-based approach for min-sum job-shop problems. Ann Oper Res 86:175\u2013198","journal-title":"Ann Oper Res"},{"key":"262_CR35","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1089\/cmb.1998.5.517","volume":"5","author":"HP Lenhof","year":"1998","unstructured":"Lenhof HP, Reinert K, Vingron M (1998) A polyhedral approach to RNA sequence structure alignment. J Comput Biol 5:517\u2013530","journal-title":"J Comput Biol"},{"key":"262_CR36","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"K Martin","year":"1991","unstructured":"Martin K (1991) Using separation algorithms to generate mixed integer model reformulations. Oper Res Lett 10:119\u2013128","journal-title":"Oper Res Lett"},{"key":"262_CR37","doi-asserted-by":"crossref","first-page":"1956","DOI":"10.1137\/120880355","volume":"23","author":"M Monaci","year":"2011","unstructured":"Monaci M, Pferschy U (2011) On the robust knapsack problem. SIAM J Optim 23:1956\u20131982","journal-title":"SIAM J Optim"},{"key":"262_CR38","doi-asserted-by":"crossref","first-page":"2625","DOI":"10.1016\/j.cor.2013.05.005","volume":"40","author":"M Monaci","year":"2013","unstructured":"Monaci M, Pferschy U, Serafini P (2013) Exact solution of the Robust Knapsack problem. Comput Oper Res 40:2625\u20132631","journal-title":"Comput Oper Res"},{"key":"262_CR39","first-page":"1","volume-title":"Encyclopedia of algorithms","author":"A Newman","year":"2008","unstructured":"Newman A (2008) Max Cut. In: Kao Ming-Yang (ed) Encyclopedia of algorithms. Springer, USA, pp 1\u201399"},{"issue":"1","key":"262_CR40","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev 33(1):60\u2013100","journal-title":"SIAM Rev"},{"key":"262_CR41","doi-asserted-by":"crossref","unstructured":"Stoer M, Wagner F (1994) A simple mincut algorithm. In: Proceedings of ESA 94, lecture notes in computer science, vol 855. Springer, Berlin, pp 141\u2013147","DOI":"10.1007\/BFb0049404"},{"key":"262_CR42","first-page":"761","volume":"29","author":"BY Wu","year":"1999","unstructured":"Wu BY, Lancia G, Bafna V, Chao KM, Ravi R, Tang CY (1999) A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J Comp 29:761\u2013778","journal-title":"SIAM J Comp"}],"container-title":["4OR"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-014-0262-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10288-014-0262-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10288-014-0262-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T20:32:36Z","timestamp":1565555556000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10288-014-0262-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,24]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["262"],"URL":"https:\/\/doi.org\/10.1007\/s10288-014-0262-7","relation":{},"ISSN":["1619-4500","1614-2411"],"issn-type":[{"value":"1619-4500","type":"print"},{"value":"1614-2411","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,24]]}}}