Efficient branch-and-bound algorithms for weighted MAX-2-SAT

DOI10.1007/S10107-009-0285-6MaRDI QIDQ535012zbMATH OpenOpenAlexFDO

Authors Toshihide Ibaraki, Takashi Imamichi, Yuichi Koga, Hiroshi Nagamochi, Koji Nonobe, Mutsunori Yagiura

Publication date 11 May 2011

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-009-0285-6

zbMATH Keywords

lower boundsdirected graphNP-hardbranch-and-boundMAX-2-SAT

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Recommendations

• Exact algorithms for MAX-SAT
• New Upper Bounds for Maximum Satisfiability
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Improving exact algorithms for MAX-2-SAT
• A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem

Cites work

• scientific article; zbMATH DE number 1629855 (Why is no real title available?)
• scientific article; zbMATH DE number 1728542 (Why is no real title available?)
• scientific article; zbMATH DE number 5139161 (Why is no real title available?)
• scientific article; zbMATH DE number 3668328 (Why is no real title available?)
• scientific article; zbMATH DE number 23663 (Why is no real title available?)
• scientific article; zbMATH DE number 177832 (Why is no real title available?)
• scientific article; zbMATH DE number 1114001 (Why is no real title available?)
• scientific article; zbMATH DE number 1114003 (Why is no real title available?)
• scientific article; zbMATH DE number 2050711 (Why is no real title available?)
• scientific article; zbMATH DE number 1488074 (Why is no real title available?)
• scientific article; zbMATH DE number 1500507 (Why is no real title available?)
• scientific article; zbMATH DE number 1522934 (Why is no real title available?)
• scientific article; zbMATH DE number 1795723 (Why is no real title available?)
• scientific article; zbMATH DE number 956866 (Why is no real title available?)
• A Computing Procedure for Quantification Theory
• A Linear Programming Approach to the Cutting-Stock Problem
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• A bidirectional shortest-path algorithm with good average-case behavior
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new approach to the maximum-flow problem
• A polynomial-time algorithm to find an equitable home--away assignment
• A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
• Adaptive memory tabu search for binary quadratic programs
• Algorithms for the maximum satisfiability problem
• An Empirical Study of MAX-2-SAT Phase Transitions
• Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
• BerkMin: A fast and robust SAT-solver
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation
• Exact MAX-2SAT solution via lift-and-project closure
• Exact algorithms for MAX-SAT
• Greedy and local search heuristics for unconstrained binary quadratic programming
• Improving exact algorithms for MAX-2-SAT
• Introduction to algorithms
• MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
• New Upper Bounds for Maximum Satisfiability
• New inference rules for Max-SAT
• On implementing the push-relabel method for the maximum flow problem
• On the Approximation of Maximum Satisfiability
• On the Complexity of Timetable and Multicommodity Flow Problems
• One-pass heuristics for large-scale unconstrained binary quadratic problems
• Pseudo-Boolean optimization
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Semidefinite programming based approaches to the break minimization problem
• Solving Max-SAT as weighted CSP
• Some simplified NP-complete graph problems
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Upper-bounds for quadratic 0-1 maximization
• Using the unconstrained quadratic program to model and solve Max 2-SAT problems

Cited in

(3)

• Improving exact algorithms for MAX-2-SAT
• A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
• Algorithms for Variable-Weighted 2-SAT and Dual Problems

Describes a project that uses

Uses Software

• MiniSat
• Zchaff2004
• MaxSolver
• UBCSAT
• MAX-2-SAT
• SATO
• Chaff
• BerkMin
• MiniMaxSat

This page was built for publication: Efficient branch-and-bound algorithms for weighted MAX-2-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q535012)