Algorithms for the maximum satisfiability problem

DOI10.1007/BF02241270zbMath0716.68077MaRDI QIDQ753502

Brigitte Jaumard, Pierre Hansen

Publication date: 1990

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

heuristicsmaximum satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Complexity of computation (including implicit computational complexity) (03D15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical propositional logic (03B05)

Related Items

Probabilistic estimates for the generalized maximum satisfiability problem, A tabu search algorithm for computing an operational timetable, Improved exact algorithms for MAX-SAT, A user's guide to tabu search, Hashing vectors for tabu search, A tabu search procedure for multicommodity location/allocation with balancing requirements, Solving the maximum clique problem using a tabu search approach, Minimization of a quadratic pseudo-Boolean function, Genetic algorithms and tabu search: Hybrids for optimization, New local search approximation techniques for maximum generalized satisfiability problems, Resolution and the integrality of satisfiability problems, Boolean query optimization and the 0-1 hyperbolic sum problem, The tabu search metaheuristic: How we used it, Boolean regression, Strategies with memories: Local search in an application oriented environment. Applied local search -- a prologue, New approaches for heuristic search: A bilateral linkage with artificial intelligence, Discrete dynamical system approaches for Boolean polynomial optimization, A theoretical analysis of the cross-nested logit model, Variable neighborhood search, A comparison of neighborhood search techniques for multi-objective combinatorial problems, Analysis and solving SAT and MAX-SAT problems using an \(L\)-partition approach, Heuristic reliability optimization by tabu search, Metaheuristics: A bibliography, Formal methods for reasoning and uncertainty reduction in evidential grid maps, The unconstrained binary quadratic programming problem: a survey, On optimization problems in acyclic hypergraphs, Boolean lexicographic optimization: algorithms \& applications, An artificial neural network satisfiability tester, Worst-case study of local search for MAX-\(k\)-SAT., Probabilistic satisfiability: algorithms with the presence and absence of a phase transition, A finite state intersection approach to propositional satisfiability, Probably partially true: satisfiability for Łukasiewicz infinitely-valued probabilistic logic and related topics, Probabilistic bounds and algorithms for the maximum satisfiability problem, Reactive local search techniques for the maximum \(k\)-conjunctive constraint satisfaction problem \((MAX-k-CCSP)\), Best second order bounds for two-terminal network reliability with dependent edge failures, Revisiting simulated annealing: a component-based analysis, Scatter search and genetic algorithms for MAX-SAT problems, Modelling the dynamics of stochastic local search on \(k\)-SAT, An efficient solver for weighted Max-SAT, MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability, Finding a feasible course schedule using Tabu search, Location and sizing of offshore platforms for oil exploration, Exact Algorithms for MAX-SAT, A fixed point operator for the generalised maximum satisfiability problem, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, Variable neighborhood search: Principles and applications, Deconstructing Nowicki and Smutnicki's \(i\)-TSAB tabu search algorithm for the job-shop scheduling problem, Variable neighborhood search for the maximum clique, Maximum satisfiability: how good are tabu search and plateau moves in the worst-case?, Solving thep-Center problem with Tabu Search and Variable Neighborhood Search, Variable and Clause Ordering in an FSA Approach to Propositional Satisfiability, An inventory-routing problem with the objective of travel time minimization, Solving weighted MAX-SAT via global equilibrium search, EPCOT: An efficient procedure for coloring optimally with Tabu Search, TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph, A Theoretical Analysis of Search in GSAT, An analysis of parameter adaptation in reactive tabu search, A tabu search Hooke and Jeeves algorithm for unconstrained optimization, Using heuristics to find minimal unsatisfiable subformulas in satisfiability problems, Algorithmic approach to the satisfactory graph partitioning problem, Unnamed Item, Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem, Tight bound on Johnson's algorithm for maximum satisfiability, ahmaxsat: Description and Evaluation of a Branch and Bound Max-SAT Solver, An Empirical Study of MAX-2-SAT Phase Transitions, Improving exact algorithms for MAX-2-SAT, Rank-constrained fundamental matrix estimation by polynomial global optimization versus the eight-point algorithm, Compiling propositional weighted bases, Global optimization for artificial neural networks: A tabu search application

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• A simplified NP-complete satisfiability problem
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• A thermodynamically motivated simulation procedure for combinatorial optimization problems
• An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences
• On the complexity of the maximum satisfiability problem for Horn formulas
• Some results and experiments in programming techniques for propositional logic
• Approximation algorithms for combinatorial problems
• A cascade algorithm for the logical closure of a set of binary relations
• Some simplified NP-complete graph problems
• Complete problems for deterministic polynomial time
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The tabu search metaheuristic: How we used it
• Future paths for integer programming and links to artificial intelligence
• The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Integrity constraints in logic databases
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
• Simulated annealing methods with general acceptance probabilities
• Methods of Nonlinear 0-1 Programming
• Complexity of Partial Satisfaction
• Algorithmic extremal problems in combinatorial optimization
• Input Proofs and Rank One Cutting Planes
• Unit Refutations and Horn Sets
• On the Complexity of Timetable and Multicommodity Flow Problems
• The complexity of satisfiability problems
• A Computing Procedure for Quantification Theory
• The complexity of theorem-proving procedures
• Some Extremal Properties of Bipartite Subgraphs