{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T12:37:45Z","timestamp":1762173465832},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319661575"},{"type":"electronic","value":"9783319661582"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-66158-2_41","type":"book-chapter","created":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T07:24:38Z","timestamp":1503386678000},"page":"641-651","source":"Crossref","is-referenced-by-count":6,"title":["Reduced Cost Fixing in MaxSAT"],"prefix":"10.1007","author":[{"given":"Fahiem","family":"Bacchus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antti","family":"Hyttinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matti","family":"J\u00e4rvisalo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Saikko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,23]]},"reference":[{"key":"41_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-40627-0_12","volume-title":"Principles and Practice of Constraint Programming","author":"C Ans\u00f3tegui","year":"2013","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Gab\u00e0s, J., Levy, J.: Improving WPM2 for (weighted) partial MaxSAT. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 117\u2013132. Springer, Heidelberg (2013). doi:\n10.1007\/978-3-642-40627-0_12"},{"key":"41_CR2","unstructured":"Argelich, J., Li, C.M., Many\u00e0, F., Planes, J.: MaxSAT evaluation (2016). \nhttp:\/\/maxsat.ia.udl.cat\/introduction\/\n\n. Accessed 27 Apr 2017"},{"key":"41_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-319-59776-8_18","volume-title":"Integration of AI and OR Techniques in Constraint Programming","author":"OS Bajgiran","year":"2017","unstructured":"Bajgiran, O.S., Cire, A.A., Rousseau, L.-M.: A first look at picking dual variables for maximizing reduced cost fixing. In: Salvagnin, D., Lombardi, M. (eds.) CPAIOR 2017. LNCS, vol. 10335, pp. 221\u2013228. Springer, Cham (2017). doi:\n10.1007\/978-3-319-59776-8_18"},{"key":"41_CR4","series-title":"Frontiers in Artificial Intelligence and Applications","volume-title":"Handbook of Satisfiability","year":"2009","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, Amsterdam (2009)"},{"key":"41_CR5","volume-title":"Linear Programming","author":"V Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear Programming. Freeman, New York (1983)"},{"issue":"5","key":"41_CR6","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1287\/opre.31.5.803","volume":"31","author":"H Crowder","year":"1983","unstructured":"Crowder, H., Johnson, E.L., Padberg, M.: Solving large-scale zero-one linear programming problems. Oper. Res. 31(5), 803\u2013834 (1983)","journal-title":"Oper. Res."},{"key":"41_CR7","first-page":"393","volume":"2","author":"G Danzig","year":"1954","unstructured":"Danzig, G., Fulkerson, D., Johnson, S.: Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393\u2013410 (1954)","journal-title":"Oper. Res."},{"key":"41_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-23786-7_19","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"J Davies","year":"2011","unstructured":"Davies, J., Bacchus, F.: Solving MAXSAT by solving a sequence of simpler SAT instances. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 225\u2013239. Springer, Heidelberg (2011). doi:\n10.1007\/978-3-642-23786-7_19"},{"key":"41_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-3-642-39071-5_13","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2013","author":"J Davies","year":"2013","unstructured":"Davies, J., Bacchus, F.: Exploiting the power of mip solvers in maxsat. In: J\u00e4rvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 166\u2013181. Springer, Heidelberg (2013). doi:\n10.1007\/978-3-642-39071-5_13"},{"key":"41_CR10","unstructured":"Davies, J.: Solving MAXSAT by decoupling optimization and satisfaction. Ph.D. thesis, University of Toronto (2013). \nhttp:\/\/www.cs.toronto.edu\/~jdavies\/Davies_Jessica_E_201311_PhD_thesis.pdf"},{"key":"41_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-40627-0_21","volume-title":"Principles and Practice of Constraint Programming","author":"J Davies","year":"2013","unstructured":"Davies, J., Bacchus, F.: Postponing optimization to speed up MAXSAT solving. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 247\u2013262. Springer, Heidelberg (2013). doi:\n10.1007\/978-3-642-40627-0_21"},{"key":"41_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-540-48085-3_14","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 1999","author":"F Focacci","year":"1999","unstructured":"Focacci, F., Lodi, A., Milano, M.: Cost-based domain filtering. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 189\u2013203. Springer, Heidelberg (1999). doi:\n10.1007\/978-3-540-48085-3_14"},{"key":"41_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/978-3-642-34413-8_35","volume-title":"Learning and Intelligent Optimization","author":"F Heras","year":"2012","unstructured":"Heras, F., Morgado, A., Marques-Silva, J.: Lower bounds and upper bounds for MaxSAT. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 402\u2013407. Springer, Heidelberg (2012). doi:\n10.1007\/978-3-642-34413-8_35"},{"key":"41_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-13509-5_14","volume-title":"Combinatorial Pattern Matching","author":"RM Karp","year":"2010","unstructured":"Karp, R.M.: Implicit hitting set problems and multi-genome alignment. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, p. 151. Springer, Heidelberg (2010). doi:\n10.1007\/978-3-642-13509-5_14"},{"key":"41_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1007\/978-3-540-85958-1_46","volume-title":"Principles and Practice of Constraint Programming","author":"CM Li","year":"2008","unstructured":"Li, C.M., Many\u00e0, F., Mohamedou, N.O., Planes, J.: Transforming inconsistent subformulas in MaxSAT lower bound computation. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 582\u2013587. Springer, Heidelberg (2008). doi:\n10.1007\/978-3-540-85958-1_46"},{"key":"41_CR16","unstructured":"Li, C.M., Many\u00e0, F., Planes, J.: Detecting disjoint inconsistent subformulas for computing lower bounds for Max-SAT. In: Proceedings of AAAI, pp. 86\u201391. AAAI Press (2006)"},{"key":"41_CR17","unstructured":"Li, C., Many\u00e0, F.: MaxSAT, hard and soft constraints. In: Handbook of Satisfiability, pp. 613\u2013631. IOS Press, Amsterdam (2009)"},{"key":"41_CR18","unstructured":"Lin, H., Su, K.: Exploiting inference rules to compute lower bounds for MAX-SAT solving. In: Proceedings of IJCAI, pp. 2334\u20132339 (2007)"},{"key":"41_CR19","unstructured":"Lin, H., Su, K., Li, C.M.: Within-problem learning for efficient lower bound computation in Max-SAT solving. In: Proceedings of AAAI, pp. 351\u2013356. AAAI Press (2008)"},{"issue":"2","key":"41_CR20","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1287\/opre.1120.1139","volume":"61","author":"E Moreno-Centeno","year":"2013","unstructured":"Moreno-Centeno, E., Karp, R.M.: The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment. Oper. Res. 61(2), 453\u2013468 (2013)","journal-title":"Oper. Res."},{"key":"41_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-642-31612-8_22","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2012","author":"A Morgado","year":"2012","unstructured":"Morgado, A., Heras, F., Marques-Silva, J.: Improvements to core-guided binary search for MaxSAT. In: Cimatti, A., Sebastiani, R. (eds.) SAT 2012. LNCS, vol. 7317, pp. 284\u2013297. Springer, Heidelberg (2012). doi:\n10.1007\/978-3-642-31612-8_22"},{"key":"41_CR22","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1999","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, Hoboken (1999)"},{"key":"41_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/978-3-319-40970-2_34","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2016","author":"P Saikko","year":"2016","unstructured":"Saikko, P., Berg, J., J\u00e4rvisalo, M.: LMHS: a SAT-IP hybrid MaxSAT solver. In: Creignou, N., Le Berre, D. (eds.) SAT 2016. LNCS, vol. 9710, pp. 539\u2013546. Springer, Cham (2016). doi:\n10.1007\/978-3-319-40970-2_34"},{"key":"41_CR24","unstructured":"Saikko, P.: Re-implementing and extending a hybrid SAT-IP approach to maximum satisfiability. Master\u2019s thesis, University of Helsinki (2015). \nhttp:\/\/hdl.handle.net\/10138\/159186"},{"key":"41_CR25","unstructured":"Saikko, P., Wallner, J.P., J\u00e4rvisalo, M.: Implicit hitting set algorithms for reasoning beyond NP. In: Proceedings of KR, pp. 104\u2013113. AAAI Press (2016)"},{"issue":"1\u20134","key":"41_CR26","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1023\/A:1021136801775","volume":"115","author":"ES Thorsteinsson","year":"2002","unstructured":"Thorsteinsson, E.S., Ottosson, G.: Linear relaxations and reduced-cost based propagation of continuous variable subscripts. Ann. Oper. Res. 115(1\u20134), 15\u201329 (2002)","journal-title":"Ann. Oper. Res."},{"key":"41_CR27","volume-title":"Integer Programming","author":"LA Wolsey","year":"1998","unstructured":"Wolsey, L.A.: Integer Programming. Wiley, Hoboken (1998)"},{"issue":"2","key":"41_CR28","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1287\/opre.1090.0733","volume":"58","author":"TH Yunes","year":"2010","unstructured":"Yunes, T.H., Aron, I.D., Hooker, J.N.: An integrated solver for optimization problems. Oper. Res. 58(2), 342\u2013356 (2010)","journal-title":"Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66158-2_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T07:47:27Z","timestamp":1503388047000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66158-2_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319661575","9783319661582"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66158-2_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}