{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T21:26:39Z","timestamp":1783113999463,"version":"3.54.6"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540202028","type":"print"},{"value":"9783540451938","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45193-8_25","type":"book-chapter","created":{"date-parts":[[2010,9,8]],"date-time":"2010-09-08T19:35:03Z","timestamp":1283974503000},"page":"363-376","source":"Crossref","is-referenced-by-count":35,"title":["Solving Max-SAT as Weighted CSP"],"prefix":"10.1007","author":[{"given":"Simon","family":"de Givry","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javier","family":"Larrosa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pedro","family":"Meseguer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Schiex","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"25_CR1","unstructured":"Aloul, F., Ramani, A., Markov, I., Sakallah, K.: Pbs: A backtracksearch pseudo-boolean solver and optimizer. In: Symposium on the Theory and Applications of Satisfiability Testing (SAT), Cincinnati (OH), pp. 346\u2013353 (2002)"},{"key":"25_CR2","unstructured":"Barth, P.: A davis-putnam based enumeration algorithm for linear pseudo-boolean optimization. Tech. Rep. MPI-I-95-2-003, Max-Planck Institut F\u00fcr Informatik (1995)"},{"key":"25_CR3","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"519","volume-title":"Satisfiability Problem: Theory and Applications","author":"B. Borchers","year":"1997","unstructured":"Borchers, B., Mitchell, J., Joy, S.: A branch-and-cut algorithm for MAXSAT and weighted MAX-SAT. In: Du, D., Gu, J., Pardalos, P. (eds.) Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a035, pp. 519\u2013536. AMS, Providence (1997)"},{"key":"25_CR4","unstructured":"Borning, A., Mahert, M., Martindale, A., Wilson, M.: Constraint hierarchies and logic programming. In: Int. conf. on logic programming, pp. 149\u2013164 (1989)"},{"key":"25_CR5","unstructured":"Dixon, H., Ginsberg, M.: Inference methods for a pseudo-boolean satisfiability solver. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI 2002), pp. 635\u2013640 (2002)"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","volume":"58","author":"E. Freuder","year":"1992","unstructured":"Freuder, E., Wallace, R.: Partial constraint satisfaction. Artificial Intelligence\u00a058, 21\u201370 (1992)","journal-title":"Artificial Intelligence"},{"key":"25_CR7","unstructured":"Freuder, E.C.: Partial constraint satisfaction. In: Proc. of the 11th IJCAI, Detroit, MI, pp. 278\u2013283 (1989)"},{"key":"25_CR8","unstructured":"Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: New worstcase upper bounds for MAX-2-SAT with application to MAX-CUT. Tech. Rep. TR00-037, Electronic Colloquium on Computational Complexity (2000)"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-46521-9_15","volume-title":"Algorithms and Complexity","author":"J. Gramm","year":"2000","unstructured":"Gramm, J., Niedermeier, R.: Faster exact solutions for max2Sat. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 174\u2013186. Springer, Heidelberg (2000)"},{"key":"25_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF02241270","volume":"44","author":"P. Hansen","year":"1990","unstructured":"Hansen, P., Jaumard, B.: Algorithms for the maximum satisfiability problem. Computing\u00a044, 279\u2013303 (1990)","journal-title":"Computing"},{"key":"25_CR11","unstructured":"ILOG. Cplex solver 8.1.0 (2002), \n                    \n                      http:\/\/www.ilog.com\/products\/cplex"},{"key":"25_CR12","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume-title":"Second DIMACS implementation challenge:cliques, coloring and satisfiability","year":"1996","unstructured":"Johnson, D.S., Trick, M.A. (eds.): Second DIMACS implementation challenge:cliques, coloring and satisfiability. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a026. AMS, Providence (1996)"},{"key":"25_CR13","unstructured":"Larrosa, J.: On arc and node consistency in weighted CSP. In: Proc. AAAI 2002, Edmondton, CA (2002)"},{"key":"25_CR14","series-title":"Lecture Notes in Computer Science","first-page":"531","volume-title":"On the dual representation of non-binary semiring-based CSPs","author":"J. Larrosa","year":"2000","unstructured":"Larrosa, J., Dechter, R.: CP 2000. LNCS, vol.\u00a01894, p. 531. Springer, Heidelberg (2000)"},{"key":"25_CR15","unstructured":"Larrosa, J., Schiex, T.: In: the quest of the best form of local consistency for weighted CSP. In: Proc. of the 18th IJCAI, Acapulco, Mexico (August 2003), see \n                    \n                      http:\/\/www.inra.fr\/bia\/T\/schiex\/Export\/ijcai03.pdf"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient sat solver. In: 38th Design Automation Conference (DAC 2001), June 2001, pp. 530\u2013535 (2001)","DOI":"10.1145\/378239.379017"},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1090\/dimacs\/035\/11","volume-title":"Satisfiability problem: Theory and Applications","author":"M. Resende","year":"1997","unstructured":"Resende, M., Pitsoulis, L., Pardalos, P.: Approximate solution of weighted max-SAT problems using GRASP. In: Du, D., Gu, J., Pardalos, P. (eds.) Satisfiability problem: Theory and Applications, pp. 393\u2013405. AMS, Providence (1997)"},{"issue":"6","key":"25_CR18","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1109\/TSMC.1976.4309519","volume":"6","author":"A. Rosenfeld","year":"1976","unstructured":"Rosenfeld, A., Hummel, R., Zucker, S.: Scene labeling by relaxation operations. IEEE Trans. on Systems, Man, and Cybernetics\u00a06(6), 173\u2013184 (1976)","journal-title":"IEEE Trans. on Systems, Man, and Cybernetics"},{"key":"25_CR19","unstructured":"Schiex, T. Arc coh\u00e9rence pour contraintes molles. In: Actes de JNPC 2000, Marseille (June 2000)"},{"key":"25_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/3-540-45349-0_30","volume-title":"Principles and Practice of Constraint Programming - CP 2000","author":"T. Schiex","year":"2000","unstructured":"Schiex, T.: Arc consistency for soft constraints. In: Dechter, R. (ed.) CP 2000. LNCS, vol.\u00a01894, pp. 411\u2013424. Springer, Heidelberg (2000)"},{"key":"25_CR21","unstructured":"Schiex, T., Fargier, H., Verfaillie, G.: Valued constraint satisfaction problems: hard and easy problems. In: Proc. of the 14th IJCAI, Montr\u00e9al, Canada, August 1995, pp. 631\u2013637 (1995)"},{"key":"25_CR22","unstructured":"Selman, B., Kautz, H., Cohen, B.: Noise strategies for improving local search. In: Proc. of AAAI 1994, Seattle, WA, pp. 337\u2013343 (1994)"},{"key":"25_CR23","unstructured":"van Gelder, A.: Cnfgen formula generator (1993), \n                    \n                      ftp:\/\/dimacs.rutgers.edu\/pub\/challenge\/satisfiability\/contributed\/UCSC\/instances"},{"key":"25_CR24","unstructured":"van Hentenryck, P., Deville, Y.: The cardinality operator: A new logical connective for constraint logic programming. In: Proc. of the 8th international conference on logic programming, Paris, France (June 1991)"},{"key":"25_CR25","first-page":"542","volume-title":"Proceedings of the 38th conference on Design automation","author":"J. Whittemore","year":"2001","unstructured":"Whittemore, J., Kim, J., Sakallah, K.: SATIRE: A new incremental satisfiability engine. In: Proceedings of the 38th conference on Design automation, Las Vegas, NV, pp. 542\u2013545. ACM, New York (2001)"},{"key":"25_CR26","doi-asserted-by":"crossref","unstructured":"Xu, H., Rutenbar, R.A., Sakallah, K.: sub-SAT: A formulation for relaxed boolean satisfiability with applications in routing. In: Proc. Int. Symp. on Physical Design, San Diego, CA (April 2002)","DOI":"10.1145\/505388.505432"},{"key":"25_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/3-540-45578-7_11","volume-title":"Principles and Practice of Constraint Programming - CP 2001","author":"W. Zhang","year":"2001","unstructured":"Zhang, W.: Phase transitions and backbones of 3-SAT and maximum 3-SAT. In: Walsh, T. (ed.) CP 2001. LNCS, vol.\u00a02239, pp. 153\u2013167. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45193-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T15:07:04Z","timestamp":1548428824000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45193-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540202028","9783540451938"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45193-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}