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. doi:10.1007/978-3-030-19212-9_43.
[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.

Full Text

Your browser does not support viewing the PDF file inline. Please click the link below to download the file.