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.
In this paper, we propose a general modeling framework for a large class of binary quadratic programs subject to variable partitioning constraints.This problem has a wide range of applications as many of the binary quadratic programs with linear constraints can be represented in this form.By exploiting the problems' structure, we propose mixed-integer nonlinear program (MINLP) and mixed-integer linear program (MILP) reformulations and show the relationship between the two models in terms of the relaxation strength.Our methodology relies on a convex reformulation of the proposed MINLP and a branch-and-cut algorithm based on outer approximation cuts where the cuts are generated on the fly by efficiently solving separation subproblems.Our experimental results on various quadratic combinatorial optimization problems show that our approach outperforms the state-of-the-art solver applied to different MILP reformulations of the corresponding problems.
Quadratic programming (QP) is a well-studied fundamental NP-hard optimization problem which optimizes a quadratic objective over a set of linear constraints. In this paper, we reformulate QPs as a mixed-integer linear problem (MILP). This is done via the reformulation of QP as a linear complementary problem, and the use of binary variables and big-M constraints, to model the complementary constraints. To obtain such reformulation, we show how to impose bounds on the dual variables without eliminating all the (globally) optimal primal solutions; using some fundamental results on the solution of perturbed linear systems. Reformulating non-convex QPs as MILPs provides an advantageous way to obtain global solutions as it allows the use of current state-of-the-art MILP solvers. To illustrate this, we compare the performance of our solution approach, labeled quadprogIP, with the current benchmark global QP solver quadprogBB, as well as with BARON, one of the leading non-linear programming (NLP) solvers, and CPLEX's non-convex QP solver, on a large variety of QP test instances. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. For general QPs, quadprogIP outperforms quadprogBB, outperforms BARON in most instances, while CPLEX performs the best on these instances. For box-constrained QPs, quadprogIP has a comparable performance to quadprogBB and BARON in small- to medium-scale instances, but is outperformed by these solvers on large-scale instances; while CPLEX performs the best on box-constrained QP instances. Also, unlike quadprogBB, the solution approach proposed here is able to solve QP instances whose dual feasible set is unbounded. The MATLAB code, called quadprogIP, and the instances used to perform these numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP.
Binary Quadratic Program with Variable Partitioning Constraints The binary quadratic program with variable partitioning constraints is a very general class of optimization problems that is very difficult to solve because of the nonconvexity and integrality of the variables and is ubiquitous, among others, in network design, computer vision, and transportation and logistics. In their article, “A convex reformulation and an outer approximation for a large class of binary quadratic programs,” Rostami et al. show how to transform such a nonconvex challenging problem into a convex bilinear program with decomposable structure. The authors develop a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. The results of their computational experiments on different problems confirm the efficacy of the solution methods in solving large-scale problem instances.
The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.
We propose new cutting planes for strengthening the linear relaxations that appear in the solution of nonconvex quadratic problems with linear constraints. By a famous result of Motzkin and Straus, these problems are connected to the clique number of a graph. Our cuts are derived in the context of a spatial branch-and-bound algorithm where linearization variables are introduced to represent products. Their validity is based on the result of Motzkin and Straus, in that it depends on the clique number of certain graphs. For convenience, we derive our cuts for the special case of the so-called standard quadratic programs, where the only (linear) constraint imposes that variables must belong to a simplex. We specifically consider cuts that correspond to carefully constructed complete bipartite graphs. We study the relation between these cuts and the classical ones obtained at the first level of the reformulation-linearization technique. By studying this relation, we derive a new type of valid inequalities that generalizes both types of cuts, and thus leading to a large family of cutting planes to strengthen the linear relaxation. We present extensive computational results using the different cutting planes we propose within the spatial branch and bound implemented by the commercial solver CPLEX. We show that our cuts allow us to obtain a significantly better bound than reformulation-linearization cuts and reduce computing times for global optimality. Finally, we formally establish the scaling necessary for using the proposed cuts to solve nonconvex quadratic problems with linear constraints, e.g., quadratic knapsack problems.