Exact MAX-2SAT solution via lift-and-project closure |
| |
| Authors: | P. Bonami |
| |
| Affiliation: | a Carnegie Mellon University, Pittsburgh, USA
b Université Paris 6, 4 Place Jussieu, 75005, Paris, France |
| |
| Abstract: | We present a new approach for exact solution of MAX-2SAT problems based on a strong reformulation deduced from an optimal continuous solution over the elementary closure of lift-and-project cuts. Computational results show that this formulation leads to a reduced number of nodes in the branch-and-bound tree and short computing times. |
| |
| Keywords: | Mixed-integer-programming MAX-2SAT Branch-and-cut Lift-and-project |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
