Efficient branch-and-bound algorithms for weighted MAX-2-SAT
From MaRDI portal
Publication:535012
DOI10.1007/s10107-009-0285-6zbMath1216.90073OpenAlexW2049935674MaRDI QIDQ535012
Yuichi Koga, Hiroshi Nagamochi, Toshihide Ibaraki, Koji Nonobe, Takashi Imamichi, 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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudo-Boolean optimization
- Algorithms for the maximum satisfiability problem
- Improving exact algorithms for MAX-2-SAT
- Upper-bounds for quadratic 0-1 maximization
- A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
- Some simplified NP-complete graph problems
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems
- Analyses on the 2 and 3-flip neighborhoods for the MAX SAT
- On implementing the push-relabel method for the maximum flow problem
- One-pass heuristics for large-scale unconstrained binary quadratic problems
- A polynomial-time algorithm to find an equitable home--away assignment
- A bidirectional shortest-path algorithm with good average-case behavior
- Efficient 2 and 3-flip neighborhood search algorithms for the MAX SAT: experimental Evaluation
- Greedy and local search heuristics for unconstrained binary quadratic programming
- MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability
- Exact MAX-2SAT solution via lift-and-project closure
- Using the unconstrained quadratic program to model and solve Max 2-SAT problems
- Semidefinite programming based approaches to the break minimization problem
- BerkMin: A fast and robust SAT-solver
- Adaptive Memory Tabu Search for Binary Quadratic Programs
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- A Linear Programming Approach to the Cutting-Stock Problem
- An Empirical Study of MAX-2-SAT Phase Transitions
- Roof duality, complementation and persistency in quadratic 0–1 optimization
- A new approach to the maximum-flow problem
- Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the Approximation of Maximum Satisfiability
- New Upper Bounds for Maximum Satisfiability
- Exact Algorithms for MAX-SAT
- Theory and Applications of Satisfiability Testing
- A Computing Procedure for Quantification Theory
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Principles and Practice of Constraint Programming – CP 2003
