This paper is concerned with binary quadratic programs (BQPs), which are among the most well-studied classes of nonlinear integer optimization problems because of their wide variety of applications. While a number of different solution approaches have been proposed for tackling BQPs, practitioners need techniques that are both efficient and easy to implement. We revisit two of the most widely used linearization strategies for BQPs and examine the effectiveness of enhancements to these formulations that have been suggested in the literature. We perform a detailed large-scale computational study over five different classes of BQPs to compare these two linearizations with a more recent linear reformulation and direct submission of the nonlinear integer program to an optimization solver. The goal is to provide practitioners with guidance on how to best approach solving BQPs in an effective and easily implemented manner.
This paper is concerned with binary quadratic programs (BQPs), which are among the most well-studied classes of nonlinear integer optimization problems because of their wide variety of applications. While a number of different solution approaches have been proposed for tackling BQPs, practitioners need techniques that are both efficient and easy to implement. We revisit two of the most widely used linearization strategies for BQPs and examine the effectiveness of enhancements to these formulations that have been suggested in the literature. We perform a detailed large-scale computational study over five different classes of BQPs to compare these two linearizations with a more recent linear reformulation and direct submission of the nonlinear integer program to an optimization solver. The goal is to provide practitioners with guidance on how to best approach solving BQPs in an effective and easily implemented manner.
This paper addresses the solution of a nonlinear boolean quadratic programming problem using three different approaches. The first uses a classic linearization technique to transform the original problem into a Mixed Integer Linear Programming (MILP) problem for which multiple formulations are studied. The second uses the capabilities of current MILP solvers to deal with Mixed Integer Quadratic Programming (MIQP) problems, and the third relies on the utilization of optimization solvers available that can deal with nonlinear combinatorial problems. Two additional strategies relying on the MILP formulations are evaluated. Special emphasis is placed on the definition of computationally efficient MILP reformulations and their comparison with other approaches. The results indicate that the most efficient approach relies on solving the problem as a MIQP problem using a specific MILP solver from the set of solvers tested, while the most efficient MILP formulations are still a better option than solving the problem as a MIQP using the remaining MILP solvers tested, and their performance is considerably superior to the application of general purpose solvers.
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.
Quadratic programming problems have received an increasing amount of attention in the recent years, both from the theoretical and practical point of views. For this class of problems, we studied two different useful computational tricks.The first one is the exploitation of Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers. We included the SDP relaxation in a state-of-the-art MINLP solver as an additional bounding technique and demonstrated that this idea could be computationally useful. The Quadratic Stable Set Problem is adopted as the case study. The tests indicate that the Hybrid SDP Bounding Procedure allows an average 50% cut of the overall computing time and a cut of more than one order of magnitude for the branching nodes.The second one is a new linearisation technique. We computationally prove that the new formulation, called Extended Linear Formulation, can be effective for different classes of problems in practice. Our tests are based on two sets of classical BQPs from the literature, i.e., the Unconstrained BQP and the Maximum Cut of edge-weighted graphs. Finally we discuss the relations between the Linear Programming relaxations of the different linearisation techniques presented and we discuss the elimination of constraint redundancy which is effective at speeding up the computational convergence.
The main objective of this work is to show the application of linear and nonlinear programming methods to deal with problems whose natural 0−1 formulation has a quadratic objective function. To this end, we develop an extension of the t-linearization technique and show how to apply it to quadratic problems such as Maximum Cut, Maximum Diversity and Maximum Edge-Weighted Clique. In addition, we review the hyperbolic smoothing technique and show how to apply it to the maximum cut problem. We carry out a theoretical study of each problem, where we particularly present the development of new valid inequalities for each of them. We perform computational experiments to evaluate the performance of each technique separately, as well as combined with the proposed new constraints. The experiments attest the quality of the bounds obtained as well as the strength of the new inequalities. We develop an exact method for each problem, based on the presented techniques. For the maximum cut and maximum edge-weighted clique, we compare our method with linearized formulations. For maximum diversity, we compare our method with linearized formulations and with our implementation of the best exact method, which does not use mathematical solvers, known in the literature. Computational experiments with instances of the literature show superior performance of our method.
Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.
In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.