{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T16:19:07Z","timestamp":1773332347447,"version":"3.50.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s12532-017-0122-5","type":"journal-article","created":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T11:05:55Z","timestamp":1497351955000},"page":"33-68","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Branch-and-cut for linear programs with overlapping SOS1 constraints"],"prefix":"10.1007","volume":"10","author":[{"given":"Tobias","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc E.","family":"Pfetsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"122_CR1","unstructured":"Achterberg, T.: Constraint Integer Programming. Ph.D. Thesis, Technical University Berlin (2007)"},{"issue":"1","key":"122_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","volume":"1","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1\u201341 (2009)","journal-title":"Math. Program. Comput."},{"key":"122_CR3","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T Achterberg","year":"2004","unstructured":"Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33, 42\u201354 (2004)","journal-title":"Oper. Res. Lett."},{"key":"122_CR4","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1016\/j.disopt.2016.05.005","volume":"21","author":"A Agra","year":"2016","unstructured":"Agra, A., Doostmohammadi, M., de Souza, C.C.: Valid inequalities for a single constrained 0\u20131 MIP set intersected with a conflict graph. Discrete Optim. 21, 42\u201370 (2016)","journal-title":"Discrete Optim."},{"issue":"1","key":"122_CR5","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0377-2217(99)00015-6","volume":"121","author":"A Atamt\u00fcrk","year":"2000","unstructured":"Atamt\u00fcrk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1), 40\u201355 (2000)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"122_CR6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s101070000154.","volume":"89","author":"A Atamt\u00fcrk","year":"2000","unstructured":"Atamt\u00fcrk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: The mixed vertex packing problem. Math. Program. 89(1), 35\u201353 (2000)","journal-title":"Math. Program."},{"issue":"2","key":"122_CR7","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/s10957-007-9263-4","volume":"134","author":"C Audet","year":"2007","unstructured":"Audet, C., Savard, G., Zghal, W.: New branch-and-cut algorithm for bilevel linear programming. J. Optim. Theory Appl. 134(2), 353\u2013370 (2007)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"122_CR8","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0304-3975(96)00031-X","volume":"162","author":"BS Baker","year":"1996","unstructured":"Baker, B.S., Coffman Jr., E.G.: Mutual exclusion scheduling. Theor. Comput. Sci. 162(2), 225\u2013243 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"122_CR9","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10107-002-0317-y","volume":"94","author":"E Balas","year":"2003","unstructured":"Balas, E., Perregaard, M.: A precise correspondence between lift-and-project cuts, simple disjunctive cuts and mixed integer gomory cuts for 0\u20131 programming. Math. Program. 94(2), 221\u2013245 (2003)","journal-title":"Math. Program."},{"key":"122_CR10","unstructured":"Beale, E.M.L., Tomlin, J.A.: Special facilities in general mathematical programming system for non-convex problems using ordered sets of variables. In: Lawrence, J. (ed.) Proceedings of the 5th International Conference on Operations Research, pp. 447\u2013454. Travistock Publications, London (1970)"},{"issue":"1","key":"122_CR11","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/BF01584344","volume":"13","author":"M Benichou","year":"1977","unstructured":"Benichou, M., Gauthier, J.M., Hentges, G., Ribiere, G.: The efficient solution of large-scale linear programming problems-some algorithmic techniques and computational results. Math. Program. 13(1), 280\u2013322 (1977)","journal-title":"Math. Program."},{"issue":"6","key":"122_CR12","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1016\/j.orl.2013.08.007","volume":"41","author":"T Berthold","year":"2013","unstructured":"Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611\u2013614 (2013)","journal-title":"Oper. Res. Lett."},{"key":"122_CR13","unstructured":"Berthold, T.: Heuristic Algorithms in Global MINLP Solvers. Ph.D. Thesis, TU Berlin (2014)"},{"issue":"2","key":"122_CR14","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s10589-010-9350-6","volume":"51","author":"P Bonami","year":"2012","unstructured":"Bonami, P., Gon\u00e7alves, J.P.: Heuristics for convex mixed integer nonlinear programs. Comput. Optim. Appl. 51(2), 729\u2013747 (2012)","journal-title":"Comput. Optim. Appl."},{"key":"122_CR15","unstructured":"Bornd\u00f6rfer, R., Kormos, Z.: An algorithm for maximum cliques. Zuse Institute Berlin, 1997 (Unpublished Manuskript)"},{"issue":"9","key":"122_CR16","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973)","journal-title":"Commun. ACM"},{"issue":"2","key":"122_CR17","first-page":"185","volume":"36","author":"B Cao","year":"1992","unstructured":"Cao, B.: Transportation problem with nonlinear side constraints a branch and bound approach. Z. Oper. Res. 36(2), 185\u2013197 (1992)","journal-title":"Z. Oper. Res."},{"key":"122_CR18","doi-asserted-by":"crossref","unstructured":"Dowsland, K.A.: Nurse scheduling with tabu search and strategic oscillation. Eur. J. Oper. Res. 106(2\u20133), 393\u2013407 (1998)","DOI":"10.1016\/S0377-2217(97)00281-6"},{"issue":"1","key":"122_CR19","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1017\/S0269888901000030","volume":"16","author":"IR Farias de","year":"2001","unstructured":"de Farias, I.R., Johnson, E.L., Nemhauser, G.L.: Branch-and-cut for combinatorial optimization problems without auxiliary binary variables. Knowl. Eng. Rev. 16(1), 25\u201339 (2001)","journal-title":"Knowl. Eng. Rev."},{"issue":"1","key":"122_CR20","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1287\/moor.27.1.210.335","volume":"27","author":"IR Farias de","year":"2002","unstructured":"de Farias, I.R., Johnson, E.L., Nemhauser, G.L.: Facets of the complementarity knapsack polytope. Math. Oper. Res. 27(1), 210\u2013226 (2002)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"122_CR21","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s12532-014-0070-2","volume":"6","author":"IR Farias de","year":"2014","unstructured":"de Farias, I.R., Kozyreff, E., Zhao, M.: Branch-and-cut for complementarity-constrained optimization. Math. Program. Comput. 6(4), 365\u2013403 (2014)","journal-title":"Math. Program. Comput."},{"issue":"3","key":"122_CR22","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1007\/s10107-003-0420-8","volume":"96","author":"IR Farias de","year":"2003","unstructured":"de Farias, I.R., Nemhauser, G.L.: A polyhedral study of the cardinality constrained knapsack problem. Math. Program. 96(3), 439\u2013467 (2003)","journal-title":"Math. Program."},{"key":"122_CR23","unstructured":"Fischer, T., Pfetsch, M.E.: On the structure of linear programs with overlapping cardinality constraints. Technical report, Available on Optimization Online (2017)"},{"issue":"5","key":"122_CR24","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1287\/mnsc.20.5.736","volume":"20","author":"JJH Forrest","year":"1974","unstructured":"Forrest, J.J.H., Hirst, J.P.H., Tomlin, J.A.: Practical solution of large mixed integer programming problems with UMPIRE. Manag. Sci. 20(5), 736\u2013773 (1974)","journal-title":"Manag. Sci."},{"key":"122_CR25","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"122_CR26","unstructured":"Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533\u2013549 (1986). Applications of Integer Programming"},{"issue":"2","key":"122_CR27","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1109\/18.825799","volume":"46","author":"P Gupta","year":"2000","unstructured":"Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Trans. Inf. Theory 46(2), 388\u2013404 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"122_CR28","unstructured":"Hamdi, K., Labadi, N., Yalaoui, A.: An iterated local search algorithm for the vehicle routing problem with conflicts. In: 8th International Conference of Modeling and Simulation\u2014MOSIM10, pp. 1203\u20131211 (2010)"},{"issue":"9","key":"122_CR29","doi-asserted-by":"crossref","first-page":"2657","DOI":"10.1016\/j.cor.2005.10.004","volume":"34","author":"M Hifi","year":"2007","unstructured":"Hifi, M., Michrafy, M.: Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comput. Oper. Res. 34(9), 2657\u20132673 (2007)","journal-title":"Comput. Oper. Res."},{"key":"122_CR30","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s10107-011-0488-5","volume":"137","author":"T Hoheisel","year":"2013","unstructured":"Hoheisel, T., Kanzow, C., Schwartz, A.: Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints. Math. Program. 137, 257\u2013288 (2013)","journal-title":"Math. Program."},{"issue":"1","key":"122_CR31","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1137\/07068463x","volume":"19","author":"J Hu","year":"2008","unstructured":"Hu, J., Mitchell, J.E., Pang, J.S., Bennett, K.P., Kunapuli, G.: On the global solution of linear programs with linear complementarity constraints. SIAM J. Optim. 19(1), 445\u2013471 (2008)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"122_CR32","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10898-010-9644-3","volume":"53","author":"J Hu","year":"2012","unstructured":"Hu, J., Mitchell, J.E., Pang, J.S., Yu, B.: On linear programs with linear complementarity constraints. J. Glob. Optim. 53(1), 29\u201351 (2012)","journal-title":"J. Glob. Optim."},{"issue":"1","key":"122_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0377-2217(84)90002-X","volume":"17","author":"W Hummeltenberg","year":"1984","unstructured":"Hummeltenberg, W.: Implementations of special ordered sets in MP software. Eur. J. Oper. Res. 17(1), 1\u201315 (1984)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"122_CR34","doi-asserted-by":"crossref","first-page":"28","DOI":"10.15807\/jorsj.23.28","volume":"23","author":"T Ibaraki","year":"1980","unstructured":"Ibaraki, T.: Approximate algorithms for the multiple-choice continuous knapsack problem. J. Oper. Res. Soc. Jpn. 23(1), 28\u201362 (1980)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"1","key":"122_CR35","doi-asserted-by":"crossref","first-page":"59","DOI":"10.15807\/jorsj.21.59","volume":"21","author":"T Ibaraki","year":"1978","unstructured":"Ibaraki, T., Hasegawa, T., Teranaka, K., Iwase, J.: The multiple-choice knapsack problem. J. Oper. Res. Soc. Jpn. 21(1), 59\u201395 (1978)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"4","key":"122_CR36","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/s11276-005-1769-9","volume":"11","author":"K Jain","year":"2005","unstructured":"Jain, K., Padhye, J., Padmanabhan, V.N., Qiu, L.: Impact of interference on multi-hop wireless network performance. Wirel. Netw. 11(4), 471\u2013487 (2005)","journal-title":"Wirel. Netw."},{"key":"122_CR37","first-page":"35","volume-title":"Algorithm Theory\u2014SWAT\u201998. Lecture Notes in Computer Science","author":"K Jansen","year":"1998","unstructured":"Jansen, K.: An approximation scheme for bin packing with conflicts. In: Arnborg, S., Ivansson, L. (eds.) Algorithm Theory\u2014SWAT\u201998. Lecture Notes in Computer Science, vol. 1432, pp. 35\u201346. Springer, Berlin, Heidelberg (1998)"},{"issue":"3","key":"122_CR38","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0166-218X(87)90026-6","volume":"17","author":"RG Jeroslow","year":"1987","unstructured":"Jeroslow, R.G.: Representability in mixed integer programming, I: characterization results. Discrete Appl. Math. 17(3), 223\u2013243 (1987)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"122_CR39","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/s10898-006-9001-8","volume":"36","author":"JJ J\u00fadice","year":"2006","unstructured":"J\u00fadice, J.J., Sherali, H.D., Ribeiro, I.M., Faustino, A.M.: A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints. J. Glob. Optim. 36(1), 89\u2013114 (2006)","journal-title":"J. Glob. Optim."},{"key":"122_CR40","first-page":"406","volume":"2","author":"EYH Lin","year":"1998","unstructured":"Lin, E.Y.H.: Multiple choice knapsack problems and its extensions on capital investment. Oper. Res. Appl. 2, 406\u2013417 (1998)","journal-title":"Oper. Res. Appl."},{"key":"122_CR41","volume-title":"Linear Complementarity, Linear and Non Linear Programming. Sigma Series in Applied Mathematics","author":"KG Murty","year":"1988","unstructured":"Murty, K.G.: Linear Complementarity, Linear and Non Linear Programming. Sigma Series in Applied Mathematics. Heldermann Verlag, Berlin (1988)"},{"key":"122_CR42","volume-title":"Integer and Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization. Wiley, London (1999)"},{"issue":"1","key":"122_CR43","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF00934290","volume":"11","author":"G Owen","year":"1973","unstructured":"Owen, G.: Cutting planes for programs with disjunctive constraints. J. Optim. Theory Appl. 11(1), 49\u201355 (1973)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"122_CR44","doi-asserted-by":"crossref","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy, U., Schauer, J.: The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13(2), 233\u2013249 (2009)","journal-title":"J. Graph Algorithms Appl."},{"issue":"2\u20133","key":"122_CR45","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0166-218X(02)00205-6","volume":"126","author":"S Sakai","year":"2003","unstructured":"Sakai, S., Togasaki, M., Yamazaki, K.: A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math. 126(2\u20133), 313\u2013322 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"122_CR46","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","volume":"6","author":"MWP Savelsbergh","year":"1994","unstructured":"Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6(4), 445\u2013454 (1994)","journal-title":"ORSA J. Comput."},{"key":"122_CR47","unstructured":"SCIP: Solving Constraint Integer Programs. http:\/\/scip.zib.de"},{"key":"122_CR48","doi-asserted-by":"crossref","unstructured":"Shi, Y., Hou, Y.T., Liu, J., Kompella, S.: How to correctly use the protocol interference model for multi-hop wireless networks. In: MobiHoc \u201909: Proceedings of the Tenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 239\u2013248. ACM, New York, USA (2009)","DOI":"10.1145\/1530748.1530782"},{"issue":"4","key":"122_CR49","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1023\/A:1009630528341","volume":"3","author":"M Sun","year":"1998","unstructured":"Sun, M.: A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints. J. Heuristics 3(4), 305\u2013326 (1998)","journal-title":"J. Heuristics"},{"issue":"3\u20134","key":"122_CR50","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1023\/A:1024610128238","volume":"14","author":"A Syarif","year":"2003","unstructured":"Syarif, A., Gen, M.: Solving exclusionary side constrained transportation problem by using a hybrid spanning tree-based genetic algorithm. J. Intell. Manuf. 14(3\u20134), 389\u2013399 (2003)","journal-title":"J. Intell. Manuf."},{"issue":"1\u20133","key":"122_CR51","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF01589393","volume":"42","author":"JA Tomlin","year":"1988","unstructured":"Tomlin, J.A.: Special ordered sets and an application to gas supply operations planning. Math. Program. 42(1\u20133), 69\u201384 (1988)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-017-0122-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-017-0122-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-017-0122-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T00:27:13Z","timestamp":1569457633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-017-0122-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["122"],"URL":"https:\/\/doi.org\/10.1007\/s12532-017-0122-5","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,13]]}}}