caa a22 4500 465751415 CHVBK 20180323111834.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF02241270 doi (NATIONALLICENCE)springer-10.1007/BF02241270 Algorithms for the maximum satisfiability problem [Elektronische Daten] [Pierre Hansen, Brigitte Jaumard] Algorithmen für das maximale Erfüllbarkeitsproblem Old and new algorithms for the Maximum Satisfiability problem are studied. We first summarize the different heuristics previously proposed, i.e., the approximation algorithms of Johnson and of Lieberherr for the general Maximum Satisfiability problem, and the heuristics of Lieberherr and Specker, Poljak and Turzik for the Maximum 2-Satisfiability problem. We then consider two recent local search algorithmic schemes, the Simulated Annealing method of Kirkpatrick, Gelatt and Vecchi and the Steepest Ascent Mildest Descent method, and adapt them to the Maximum Satisfiability problem. The resulting algorithms, which avoid being blocked as soon as a local optimum has been found, are shown empirically to be more efficient than the heuristics previously proposed in the literature. Springer-Verlag, 1990 Satisfiability nationallicence heuristic nationallicence computation nationallicence Hansen Pierre Rutcor, Hill Center for Mathematical Sciences, Rutgers University, 08903, New Brunswick, NY, U.S.A. aut Jaumard Brigitte Département de Mathématiques Appliquées, Gérad and École Polytechnique, Succ. A., C.P. 6079, H3C 3A7, Montréal, Québec, Canada aut Computing Springer-Verlag 44/4(1990-12-01), 279-303 0010-485X 44:4<279 1990 44 607 https://doi.org/10.1007/BF02241270 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02241270 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hansen Pierre Rutcor, Hill Center for Mathematical Sciences, Rutgers University, 08903, New Brunswick, NY, U.S.A aut NATIONALLICENCE 700 1- Jaumard Brigitte Département de Mathématiques Appliquées, Gérad and École Polytechnique, Succ. A., C.P. 6079, H3C 3A7, Montréal, Québec, Canada aut NATIONALLICENCE 773 0- Computing Springer-Verlag 44/4(1990-12-01), 279-303 0010-485X 44:4<279 1990 44 607 Metadata rights reserved Springer special CC-BY-NC licence nationallicence SWISSBIB 465751415 BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer