Efficient branch-and-bound algorithms for weighted MAX-2-SAT
DOI10.1007/S10107-009-0285-6zbMATH Open1216.90073OpenAlexW2049935674MaRDI QIDQ535012FDOQ535012
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
Recommendations
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Cites Work
- Theory and Applications of Satisfiability Testing
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- BerkMin: A fast and robust SAT-solver
- Title not available (Why is that?)
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Title not available (Why is that?)
- Introduction to algorithms
- A Linear Programming Approach to the Cutting-Stock Problem
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Pseudo-Boolean optimization
- Some simplified NP-complete graph problems
- A new approach to the maximum-flow problem
- Title not available (Why is that?)
- On the Complexity of Timetable and Multicommodity Flow Problems
- A Computing Procedure for Quantification Theory
- Title not available (Why is that?)
- On implementing the push-relabel method for the maximum flow problem
- A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- Title not available (Why is that?)
- Adaptive memory tabu search for binary quadratic programs
- New inference rules for Max-SAT
- A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Algorithms for the maximum satisfiability problem
- On the Approximation of Maximum Satisfiability
- A bidirectional shortest-path algorithm with good average-case behavior
- One-pass heuristics for large-scale unconstrained binary quadratic problems
- A polynomial-time algorithm to find an equitable home--away assignment
- Greedy and local search heuristics for unconstrained binary quadratic programming
- Using the unconstrained quadratic program to model and solve Max 2-SAT problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- New Upper Bounds for Maximum Satisfiability
- Title not available (Why is that?)
- Exact algorithms for MAX-SAT
- Improving exact algorithms for MAX-2-SAT
- Title not available (Why is that?)
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
- Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation
- Exact MAX-2SAT solution via lift-and-project closure
- Semidefinite programming based approaches to the break minimization problem
- An Empirical Study of MAX-2-SAT Phase Transitions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solving Max-SAT as weighted CSP
- Upper-bounds for quadratic 0-1 maximization
Cited In (3)
Uses Software
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)
