This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming.First, relaxations for quadratic programming and related problem classes are reviewed.Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables.Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations.This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances.The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36.Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1% in all instances, while Baron achieved relative gaps between 10% and 30% in most of them.
We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.
Optimization is a crucial challenge across various domains, including finance, resource allocation, and mobility. Quantum computing has the potential to redefine the way we handle complex problems by reducing computational complexity and enhancing solution quality. Optimization, particularly of objective functions, stands to benefit significantly from quantum solvers, which leverage principles of quantum mechanics like superposition, entanglement, and tunneling. The Ising and Quadratic Unconstrained Binary Optimization (QUBO) models are the most suitable formulations for these solvers, involving binary variables and constraints treated as penalties within the overall objective function. To harness quantum approaches for optimization, two primary strategies are employed: exploiting quantum annealers—special-purpose optimization devices—and designing algorithms based on quantum circuits. This review provides a comprehensive overview of quantum optimization methods, examining their advantages, challenges, and limitations. It demonstrates their application to real-world scenarios and outlines the steps to convert generic optimization problems into quantum-compliant models. Lastly, it discusses available tools and frameworks that facilitate the exploration of quantum solutions for optimization tasks.
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .
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 binary quadratic programs (QP) having a quadratic objectivefunction, linear constraints, and binary variables. Many classical solution methods ofthese problems are based on exact reformulation of QP into anequivalent mixed integer linear program. Several linearization methods werestudied in the literature. More recent solution methods alsobuild an exact reformulation but into a problem which objective function isquadratic and convex. A common point of the two approaches is that thecontinuous relaxation of the reformulated problem is a convex optimizationproblem that can be solved in polynomial time. This makes it possible to use a general branch-and-bound framework to solve the reformulated problem and even to rely on the strongness of standard solvers. In this paper, we show that several quadratic convex reformulation methods, as well as classical linearization, can be viewed within a unified framework. This shows the non-surprising result that linearization is a particular quadratic convex reformulation on the one hand. On the other hand, it allows to compare these methods from a theoretical point of view.