{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T19:47:33Z","timestamp":1776109653991,"version":"3.50.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1990,12,1]],"date-time":"1990-12-01T00:00:00Z","timestamp":660009600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1990,12]]},"DOI":"10.1007\/bf02241270","type":"journal-article","created":{"date-parts":[[2005,11,15]],"date-time":"2005-11-15T01:18:15Z","timestamp":1132017495000},"page":"279-303","source":"Crossref","is-referenced-by-count":235,"title":["Algorithms for the maximum satisfiability problem","Algorithmen f\u00fcr das maximale Erf\u00fcllbarkeitsproblem"],"prefix":"10.1007","volume":"44","author":[{"given":"Pierre","family":"Hansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brigitte","family":"Jaumard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02241270_CR1","doi-asserted-by":"crossref","first-page":"657","DOI":"10.2307\/3214097","volume":"24","author":"Anily","year":"1987","unstructured":"Anily and Federgruen, Simulated Annealing methods with general acceptance probabilities, Journal of Applied Probability24 (1987) 657\u2013667.","journal-title":"Journal of Applied Probability"},{"key":"BF02241270_CR2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(87)90200-6","volume":"24","author":"V. Arvind","year":"1987","unstructured":"Arvind, V., and S. Biswas, AnO(n 2) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences, Information Processing Letters24 (1987) 67\u201369.","journal-title":"Information Processing Letters"},{"key":"BF02241270_CR3","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0743-1066(85)90020-2","volume":"3","author":"P. Asirelli","year":"1985","unstructured":"Asirelli, P., M. de Santis, and A. Martelli, Integrity constraints in logic data bases, Journal of Logic Programming3 (1985) 221\u2013232.","journal-title":"Journal of Logic Programming"},{"key":"BF02241270_CR4","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., M. F. Plass, and R. E. Tarjan, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Information Processing Letters8 (1979) 121\u2013123.","journal-title":"Information Processing Letters"},{"issue":"5","key":"BF02241270_CR5","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1016\/0305-0548(86)90056-0","volume":"13","author":"C. E. Blair","year":"1986","unstructured":"Blair, C. E., R. G. Jeroslow, and J. K. Lowe, Some results and experiments in programming for propositional logic, Computers and Operations Research13 (5) (1986) 633\u2013645.","journal-title":"Computers and Operations Research"},{"key":"BF02241270_CR6","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0377-2217(84)90231-5","volume":"17","author":"R. E. Burkard","year":"1984","unstructured":"Burkard, R. E., and F. Rendl, Thermodynamically motivated simulation procedure, European Journal of Operational Research17 (1984) 169\u2013174.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"BF02241270_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00940812","volume":"45","author":"V. Cerny","year":"1985","unstructured":"Cerny, V., A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications45 (1) (1985) 41\u201351.","journal-title":"Journal of Optimization Theory and Applications"},{"key":"BF02241270_CR8","doi-asserted-by":"crossref","unstructured":"Cook, S., The complexity of theorem proving procedures, Proceedings of the Third Symposium of the Association of Computing Machinery on the Theory of Computing (1971) 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"BF02241270_CR9","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M., and H. Putnam, A computing procedure for quantification theory, Journal of ACM7 (1960) 202\u2013215.","journal-title":"Journal of ACM"},{"key":"BF02241270_CR10","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"3","author":"W. F. Dowling","year":"1984","unstructured":"Dowling, W. F., and J. H. Gallier, Linear-time algorithms for testing the satisfiability of propositional Horn formulae, Journal of Logic Programming3 (1984) 267\u2013284.","journal-title":"Journal of Logic Programming"},{"issue":"15","key":"BF02241270_CR11","first-page":"765","volume":"303","author":"O. Dubois","year":"1986","unstructured":"Dubois, O., Etude de classes de donn\u00e9es du probl\u00e8me de satisfiabilit\u00e9, r\u00e9futation de la conjecture de Tovey, Comptes Rendus de l'Acad\u00e9mie des Sciences de Paris 303, s\u00e9rie I (15) (1986) 765\u2013768.","journal-title":"Comptes Rendus de l'Acad\u00e9mie des Sciences de Paris"},{"key":"BF02241270_CR12","doi-asserted-by":"crossref","first-page":"475","DOI":"10.4153\/CJM-1973-048-x","volume":"25","author":"C. S. Edwards","year":"1973","unstructured":"Edwards, C. S., Some extremal properties of bipartite subgraphs, Canadian Journal of Mathematics25 (1973) 475\u2013485.","journal-title":"Canadian Journal of Mathematics"},{"key":"BF02241270_CR13","first-page":"167","volume-title":"Recent advances in graph theory","author":"C. S. Edwards","year":"1975","unstructured":"Edwards, C. S., An improved lower bound for the number of edges in a largest bipartite subgraph, in: Recent advances in graph theory (Academia, Prague, 1975), 167\u2013181."},{"key":"BF02241270_CR14","volume-title":"Analyse de deux m\u00e9thodes heuristiques: m\u00e9thode de \u201crecuit\u201d et m\u00e9thode de \u201cplus grande descente\u2014plus petite remont\u00e9e\u201d","author":"A. Baamrani El","year":"1985","unstructured":"El Baamrani, A., Analyse de deux m\u00e9thodes heuristiques: m\u00e9thode de \u201crecuit\u201d et m\u00e9thode de \u201cplus grande descente\u2014plus petite remont\u00e9e\u201d, B. Sc. Essay, Facult\u00e9 Universitaire Catholique de Mons, Belgium (1985)."},{"key":"BF02241270_CR15","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"Even, S., Itai, A., and Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM Journal of Computing5 (1976) 691\u2013703.","journal-title":"SIAM Journal of Computing"},{"issue":"2","key":"BF02241270_CR16","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/356924.356929","volume":"16","author":"H. Gallaire","year":"1984","unstructured":"Gallaire, H., Minker, J., and J. M. Nicolas, Logic and databases: A deductive approach, Computing Surveys 16 (2) (June 1984) 153\u2013185.","journal-title":"Computing Surveys"},{"key":"BF02241270_CR17","unstructured":"Garey, R. M., and D. S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, W. H. Freeman and Co. 1979."},{"key":"BF02241270_CR18","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"R. M. Garey","year":"1976","unstructured":"Garey, R. M., Johnson, D. S., and L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science1 (1976) 237\u2013267.","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"BF02241270_CR19","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F. Glover","year":"1986","unstructured":"Glover, F., Future paths for integer programming and links to artificial intelligence, Computers and Operations Research13 (5) (1986) 533\u2013549.","journal-title":"Computers and Operations Research"},{"key":"BF02241270_CR20","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F. Glover","year":"1989","unstructured":"Glover, F., Tabu Search\u2014Part 1, ORSA Journal on Computing1 (1989) 190\u2013206.","journal-title":"ORSA Journal on Computing"},{"key":"BF02241270_CR21","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF02612354","volume":"28","author":"P. L. Hammer","year":"1984","unstructured":"Hammer, P. L., Hansen, P., and B. Simeone, Roof duality, complementation and persistency in quadratic 0\u20131 optimization, Mathematical Programming28 (1984) 121\u2013155.","journal-title":"Mathematical Programming"},{"key":"BF02241270_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-85823-9","volume-title":"Boolean methods in Operations Research and Related Areas","author":"P. L. Hammer","year":"1968","unstructured":"Hammer, P. L., and S. Rudeanu, Boolean methods in Operations Research and Related Areas, Springer-Verlag, Heidelberg, 1968."},{"key":"BF02241270_CR23","first-page":"19","volume-title":"Combinatorial Programming","author":"P. Hansen","year":"1975","unstructured":"Hansen, P., Les proc\u00e9dures d'optimisation et d'exploration par s\u00e9paration et \u00e9valuation, in Combinatorial Programming, B. Roy (ed.), Reidel, Dordrecht, 1975, 19\u201325."},{"issue":"2","key":"BF02241270_CR24","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0020-0190(76)90079-X","volume":"5","author":"P. Hansen","year":"1976","unstructured":"Hansen, P., A cascade algorithm for the logical closure of a set of binary relations, Information Processing Letters5 (2) (1976) 50\u201353.","journal-title":"Information Processing Letters"},{"key":"BF02241270_CR25","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0167-5060(08)70343-1","volume":"5","author":"P. Hansen","year":"1979","unstructured":"Hansen, P., Methods of nonlinear 0\u20131 programming, Annals of Discrete Mathematics5 (1979) 53\u201369.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF02241270_CR26","unstructured":"Hansen, P., The Steepest Ascent Mildest Descent heuristic for combinatorial programming, presented at the congress on Numerical Methods in Combinatorial Optimization, Capri, March 1986."},{"key":"BF02241270_CR27","unstructured":"Hansen, P., and B. Jaumard, Algorithms for the Maximum Satisfiability Problem, Rutcor Research Report, RRR#43-87, November 1987."},{"key":"BF02241270_CR28","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01580586","volume":"34","author":"P. Hansen","year":"1986","unstructured":"Hansen, P., Jaumard, B., and M. Minoux, A linear expected time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, Mathematical Programming34 (1986) 223\u2013231.","journal-title":"Mathematical Programming"},{"key":"BF02241270_CR29","unstructured":"Hansen, P., S. H. Lu, B. Jaumard and D. Stephany, A computational comparison of the Simulated Annealing and Steepest Descent Mildest Ascent heuristics, (in preparation)."},{"key":"BF02241270_CR30","volume-title":"Building expert systems","author":"F. Hayes","year":"1983","unstructured":"Hayes, F., D. A. Waterman and D. B. Lenat, Building expert systems, Reading, Ma., Addisson-Wesley, 1983."},{"key":"BF02241270_CR31","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1145\/321850.321857","volume":"21","author":"L. Henschen","year":"1974","unstructured":"Henschen, L., and L. Wos, Unit refutation and Horn sets, Journal of ACM21 (1974) 590\u2013605.","journal-title":"Journal of ACM"},{"key":"BF02241270_CR32","doi-asserted-by":"crossref","unstructured":"Hertz, A., and D. de Werra, The Tabu Search Metaheuristic: How we used it, Annals of Mathematics and Artificial Intelligence (to appear).","DOI":"10.1007\/BF01531073"},{"key":"BF02241270_CR33","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1287\/ijoc.1.3.137","volume":"1","author":"J. N. Hooker","year":"1989","unstructured":"Hooker, J. N., Input proofs and rank one cutting-planes, ORSA Journal on Computing1 (1989) 137\u2013145.","journal-title":"ORSA Journal on Computing"},{"key":"BF02241270_CR34","unstructured":"Jaumard, B., Extraction et utilisation de relations bool\u00e9ennes pour la r\u00e9solution des programmes lin\u00e9aires en variables 0\u20131, Th\u00e8se de Doctorat, (Paris, 1986)."},{"key":"BF02241270_CR35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(87)90028-7","volume":"26","author":"B. Jaumard","year":"1987\/88","unstructured":"Jaumard, B., and B. Simeone, On the complexity of the maximum satisfiability problem for Horn formulas, Information Processing Letters26 (1987\/88) 1\u20134.","journal-title":"Information Processing Letters"},{"key":"BF02241270_CR36","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"Johnson, D. S., Approximation algorithms for combinatorial problems, Journal of Computer and System Sciences9 (1974) 256\u2013278.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02241270_CR37","first-page":"107","volume":"3","author":"N. D. Jones","year":"1977","unstructured":"Jones, N. D., and W. T. Laaser, Complete problems for deterministic polynomial time, Theoretical Computer Science3 (1977) 107\u2013117.","journal-title":"Theoretical Computer Science"},{"key":"BF02241270_CR38","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"Karp, R. M., Reducibility among combinatorial problems, in Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, New York, 1972, 85\u2013104."},{"issue":"4598","key":"BF02241270_CR39","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirpatrick","year":"1983","unstructured":"Kirpatrick, S., C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science 220 (4598) (1983) 671\u2013674.","journal-title":"Science"},{"key":"BF02241270_CR40","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0196-6774(82)90022-0","volume":"3","author":"K. J. Lieberherr","year":"1982","unstructured":"Lieberherr, K. J., Algorithmic extremal problems in combinatorial optimization, Journal of Algorithms3 (1982) 225\u2013244.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"BF02241270_CR41","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1145\/322248.322260","volume":"28","author":"K. J. Lieberherr","year":"1981","unstructured":"Lieberherr, K. J., and E. Specker, Complexity of partial satisfaction, Journal of ACM28 (2) (1981) 411\u2013421.","journal-title":"Journal of ACM"},{"key":"BF02241270_CR42","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N. Metropolis","year":"1953","unstructured":"Metropolis, N., A. Rosenbluth, M. Rosenbluth, A. Teller, and E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys.21 (1953) 1087\u20131092.","journal-title":"J. Chem. Phys."},{"key":"BF02241270_CR43","unstructured":"Nguyen, T. A., W. A. Perkins, T. J. Laffey and D. Pecora, Checking an expert systems knowledge base for consistency and completeness, IJCAI 85, Arvind Joshi (ed.), Los Altos, California, 375\u2013378."},{"issue":"3","key":"BF02241270_CR44","doi-asserted-by":"crossref","first-page":"519","DOI":"10.4153\/CJM-1982-036-8","volume":"XXXIV","author":"S. Poljak","year":"1982","unstructured":"Poljak, S., and D. Turzik, A polynomial algorithm for constructing a large bipartite subgraph, with an application to a satisfiability problem, Canadian Journal of MathematicsXXXIV (3) (1982) 519\u2013524.","journal-title":"Canadian Journal of Mathematics"},{"key":"BF02241270_CR45","volume-title":"Quadratic 0\u20131 programming, boolean functions and graphs","author":"B. Simeone","year":"1979","unstructured":"Simeone, B., Quadratic 0\u20131 programming, boolean functions and graphs, Doctoral Dissertation, University of Waterloo, (Waterloo, Ontario, 1979)."},{"key":"BF02241270_CR46","doi-asserted-by":"crossref","unstructured":"Schaefer, T., The complexity of satisfiability problems, Proc. 10th Annual ACM Symposium on Theory of Computing (1978) 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"BF02241270_CR47","volume-title":"Localisation de postes en fonction du traffic interpostes","author":"D. Stephany","year":"1986","unstructured":"Stephany, D., Localisation de postes en fonction du traffic interpostes, B. Sc. Essay, Facult\u00e9 Universitaire Catholique de Mons. Belgium (1986)."},{"key":"BF02241270_CR48","volume-title":"Programmation non lin\u00e9aire en variables 0\u20131 et application \u00e0 des probl\u00e8mes de placement de t\u00e2ches dans des syst\u00e8mes distribu\u00e9s","author":"A. Sutter","year":"1989","unstructured":"Sutter, A., Programmation non lin\u00e9aire en variables 0\u20131 et application \u00e0 des probl\u00e8mes de placement de t\u00e2ches dans des syst\u00e8mes distribu\u00e9s, Th\u00e8se de Doctorat, Conservatoire National des Arts et M\u00e9tiers, Paris, France, Juin 1989."},{"key":"BF02241270_CR49","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C. A. Tovey","year":"1984","unstructured":"Tovey, C. A., A simplified NP-complete satisfiability problem, Discrete Applied Mathematics8 (1984) 85\u201389.","journal-title":"Discrete Applied Mathematics"},{"key":"BF02241270_CR50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(83)80027-8","volume":"59","author":"S. Yamasaki","year":"1983","unstructured":"Yamasaki, S., and S. Doshita, The satisfiability problem for a class of Horn sentences and some non-Horn sentences in propositional logic, Information and Control59 (1983) 1\u201312.","journal-title":"Information and Control"}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02241270.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02241270\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02241270","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T23:15:41Z","timestamp":1557875741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02241270"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,12]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1990,12]]}},"alternative-id":["BF02241270"],"URL":"https:\/\/doi.org\/10.1007\/bf02241270","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,12]]}}}