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 等数据库收录! |
|