On relaxations of the max k-cut problem formulations |
| |
Affiliation: | 1. Industrial and Systems Engineering, Lehigh University, PA, United States of America;2. Industrial, Manufacturing & Systems Engineering, Texas Tech University, TX, United States of America;3. Computational Applied Mathematics & Operations Research, Rice University, TX, United States of America |
| |
Abstract: | A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub. |
| |
Keywords: | Mixed integer optimization Semidefinite optimization Continuous relaxation |
本文献已被 ScienceDirect 等数据库收录! |
|