Ka Wa Yip, Hong Xu, Sven Koenig, and T. K. Satish Kumar.
Quadratic reformulation of nonlinear pseudo-Boolean functions via the constraint composite graph.
In Proceedings of the 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR). 2019.
[full text] [BibTeX▼]
Nonlinear pseudo-Boolean optimization (nonlinear PBO) is the minimization problem on nonlinear pseudo-Boolean functions (non linear PBFs). One promising approach to nonlinear PBO is to first use a quadratization algorithm to reduce the PBF to a quadratic PBF by introducing intelligently chosen auxiliary variables and then solve it using a quadratic PBO solver. In this paper, we develop a new quadratization algorithm based on the idea of the constraint composite graph (CCG). We demonstrate its theoretical advantages over state-of-the-art quadratization algorithms. We experimentally demonstrate that our CCG-based quadratization algorithm outperforms the state-of-the-art algorithm in terms of both effectiveness and efficiency on randomly generated instances and a novel reformulation of facility location problems.