Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation
From MaRDI portal
Publication:2045008
DOI10.1007/S10898-020-00972-2zbMATH Open1473.90110arXiv1901.07904OpenAlexW3119616506MaRDI QIDQ2045008FDOQ2045008
Authors: Sourour Elloumi, Amélie Lambert, Arnaud Lazare 
Publication date: 11 August 2021
Published in: Journal of Global Optimization (Search for Journal in Brave)
Abstract: We propose a solution approach for the problem (P) of minimizing an unconstrained binary polynomial optimization problem. We call this method PQCR (Polynomial Quadratic Convex Reformulation). The resolution is based on a 3-phase method. The first phase consists in reformulating (P) into a quadratic program (QP). For this, we recursively reduce the degree of (P) to two, by use of the standard substitution of the product of two variables by a new one. We then obtain a linearly constrained binary program. In the second phase, we rewrite the quadratic objective function into an equivalent and parametrized quadratic function using the equality x 2 i = x i and new valid quadratic equalities. Then, we focus on finding the best parameters to get a quadratic convex program which continuous relaxation's optimal value is maximized. For this, we build a semidefinite relaxation (SDP) of (QP). Then, we prove that the standard linearization inequalities, used for the quadratization step, are redundant in (SDP) in presence of the new quadratic equalities. Next, we deduce our optimal parameters from the dual optimal solution of (SDP). The third phase consists in solving (QP *), the optimal reformulated problem, with a standard solver. In particular, at each node of the branch-and-bound, the solver computes the optimal value of a continuous quadratic convex program. We present computational results on instances of the image restoration problem and of the low autocorrelation binary sequence problem. We compare PQCR with other convexification methods, and with the general solver Baron 17.4.1 [39]. We observe that most of the considered instances can be solved with our approach combined with the use of Cplex [24].
Full work available at URL: https://arxiv.org/abs/1901.07904
Recommendations
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Quadratic convex reformulations for quadratic 0-1 programming
- A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs
- An efficient compact quadratic convex reformulation for general integer quadratic programs
- Polynomial unconstrained binary optimisation -- part 2
global optimizationsemi-definite programmingquadratic convex reformulationunconstrained binary polynomial programming
Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22) Boolean programming (90C09) Polynomial optimization (90C23)
Cites Work
- BARON: A general purpose global optimization software package
- SCIP: solving constraint integer programs
- BBCPOP
- Algorithm 996
- Using a conic bundle method to accelerate both phases of a quadratic convex reformulation
- The maximum clique problem
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- GloptiPoly
- A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique
- A dynamic inequality generation scheme for polynomial programming
- Quadratic reformulations of nonlinear binary optimization problems
- Title not available (Why is that?)
- Quadratic Binary Programming with Application to Capital-Budgeting Problems
- ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
- Cluster Analysis and Mathematical Programming
- Exact quadratic convex reformulations of mixed-integer quadratically constrained problems
- Branching and bounds tighteningtechniques for non-convex MINLP
- Extending the QCR method to general mixed-integer programs
- An introduction to polynomial and semi-algebraic optimization
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- SDP relaxations in combinatorial optimization from a Lagrangian viewpoint.
- A Selection Problem of Shared Fixed Costs and Network Flows
- Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
- Convex underestimators of polynomials
- Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization
- A class of valid inequalities for multilinear 0-1 optimization problems
- Global solution of non-convex quadratically constrained quadratic programs
- Alternative SDP and SOCP approximations for polynomial optimization
Cited In (9)
- Solving unconstrained binary polynomial programs with limited reach: application to low autocorrelation binary sequences
- Efficient linear reformulations for binary polynomial optimization problems
- Generating convex polynomial inequalities for mixed 0-1 programs
- Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization
- A polyhedral study of lifted multicuts
- Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
- Short paper -- The binary linearization complexity of pseudo-Boolean functions
- Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
Uses Software
This page was built for publication: Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045008)
