Mixed-integer linear programs (MILPs) are fundamental to power system operations but are challenging to solve due to their NP-hard nature. Quantum annealing, which seeks to find the ground state of an Ising model–a minimization of a quadratic binary function–offers potential speedups for solving combinatorial optimization problems. However, converting MILPs into quadratic unconstrained binary optimization (QUBO) problems often requires lots of slack variables, leading to significant qubit overhead and limiting the capability of quantum annealers. In this work, we propose an efficient formulation approach that generates a QUBO representation of a targeted MILP without introducing auxiliary binary variables. Geometrically, our method approximates the value function of the MILP with a quadratic binary function leveraging a simple convex optimization subroutine. We prove the existence of the QUBO representation, which preserves the MILP’s optimal solution and objective value with the same number of binary variables. The proposed approach is validated on several instances of the security-constrained unit commitment (SCUC) problem, with test cases featuring up to 288 binary variables, demonstrating its efficacy in reducing qubit overhead for quantum-classical hybrid Benders decomposition frameworks.
Let
(QP) be an integer quadratic program that consists in minimizing a quadratic function subject to linear constraints. A such problem belongs to the class of
NP-Hard problems. Standard solvers that use a Branch and Bound algorithm can efficiently solve
(QP) in the specific case where its objective function is convex. Thus, to solve
(QP), we choose to reformulate it into an equivalent problem with a convex objective function. Two reformulations are possible: either we reformulate
(QP) into a linear program, or we reformulate it into a convex quadratic program. \par In the first part of this dissertation, we present several linearizations of
(QP), i.e. reformulations into an equivalent program with a linear objective function. Many linearization methods for the quadratic binary programs are known. A natural approach when considering
(QP) is therefore to reformulate it into a quadratic binary program. This can be done by the binary decomposition of each integer variable and then the linearization of each new product of two binary variables. However, this method, that we denote by \texttt{BBL (Binary Binary Linearization)}, leads to a linear program with a large number of variables and constraints. We then present a new approach, \texttt{BIL (Binary Integer Linearization)}, that consists in reformulating
(QP) into a particular quadratic integer program where each quadratic term is the product of an integer variable by a binary variable. As in the \texttt{BBL} approach, the binary variables come from the binary decomposition of the initial integer variables. Then, we linearize the obtained program by replacing each quadratic term by a new real variable and a set of inequalities. As the number of quadratic terms is lower than in the \texttt{BBL} approach, the number of additional variables is reduced. Hence, the obtained integer linear program is significantly smaller in the \texttt{BIL} approach. Moreover, contrary to what one might think, the \texttt{BIL} approach provides a better bound obtained by continuous relaxation than the \texttt{BBL} approach. Each reformulation leads to an integer linear program that is equivalent to
(QP) and that we improve by adding valid inequalities. \par In a second part, we present several quadratic convex reformulations of
(QP), i.e. we reformulate
(QP) into an equivalent program, with a quadratic convex objective function. We first introduce a simple approach to convexify
(QP) that consists in expressing linearly the squares of integer variables using their unary decompositions, and then to convexify with the smallest eigenvalue of the Hessian matrix of
(QP). We call this approach \texttt{NC (Naive Convexification)}. Then, we introduce a new convex reformulation scheme that perturbs the objective function of
(QP) with the linear expression of the products of integer variables, and the equality constraints of
(QP). Then, we show that we can compute, within this scheme, an optimal reformulation of
(QP) in terms of bound obtained by continuous relaxation : the \texttt{IQCR (Integer Quadratic Convex Reformulation)} approach. This reformulation is based on the optimal dual solution of a semi-definite relaxation of
(QP). Moreover, we show that the method \texttt{IQCR} is easily adaptable to mixed-integer programming. This adaptation, that we call \texttt{IQCRs}, also allows us to integrate the inequality constraints of
(QP) into the perturbation of the objective function of our convex reformulation scheme. Then, we present an interesting restriction of the method \texttt{IQCR}, called \texttt{CQCR (Compact Quadratic Convex Reformulation)}. The difference between this last approach and \texttt{IQCR} is that \texttt{CQCR} only uses the linear expression of the integer variable squares to perturb the objective function, while \texttt{IQCR} uses all the products. The interest is that \texttt{CQCR} produces a reformulated problem with a reduced size in comparison with the \texttt{IQCR} approach, what could be profitable experimentally. Finally, we apply these
3 methods \texttt{NC}, \texttt{CQCR} and \texttt{IQCR} to binary quadratic programming. We show that \texttt{NC} and \texttt{CQCR} are equivalent to existing binary convex reformulations. An interesting result is that \texttt{IQCR} is an improvement of existing convexifications for binary quadratic programming.\par In a third part, we design a specific Branch and Bound algorithm based on a projection property of the \texttt{IQCR} approach.\par Finally, we compare the four obtained linearizations and the three obtained quadratic convex reformulations from the computational point of view. For integer programming, computational experiences are carried out with two classes of instances of
(QP), the first having one equality constraint, and the other having one inequality constraint. The results show that most of the considered instances with up to
40 variables can be solved in one hour of CPU time by the \texttt{IQCR} and \texttt{CQCR} approaches. We then test \texttt{IQCR} on binary quadratic programming. The results corroborate that our approach \texttt{IQCR} improves existing convexifications.
We consider in this paper quadratic programming problems with cardinality and minimum threshold constraints that arise naturally in various real-world applications such as portfolio selection and subset selection in regression. This class of problems can be formulated as mixed-integer 0-1 quadratic programs. We propose a new semidefinite program (SDP) approach for computing the “best” diagonal decomposition that gives the tightest continuous relaxation of the perspective reformulation of the problem. We also give an alternative way of deriving the perspective reformulation by applying a special Lagrangian decomposition scheme to the diagonal decomposition of the problem. This derivation can be viewed as a “dual” method to the convexification method employing the perspective function on semicontinuous variables. Computational results show that the proposed SDP approach can be advantageous for improving the performance of mixed-integer quadratic programming solvers when applied to the perspective reformulations of the problem.