Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framework to reformulate a BQP problem with linear constraints to a new BQP with an exponential number of variables defined on a graph. This framework relies on the concept of stars in the graph to split the quadratic costs into adjacent and nonadjacent components indicating in-star and out-of-star interactions. We exploit the star-based structure of the new reformulation to develop a decomposition-based column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures. The quadratic component of the problem is dealt with in the column generation master problem and its subproblem. Results indicate the superiority of the framework over one of the state-of-the-art solvers, GUROBI, when applied to various benchmark reformulations with adjacent-only or sparse quadratic cost matrices. The framework outperforms GUROBI in terms of both dual bound and computational time in almost all instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: The authors thank the Mitacs Accelerate Program for providing funding for this project. In addition, B. Rostami gratefully acknowledges the funding provided by the Canadian Natural Sciences and Engineering Research Council (NSERC) under a Discovery Grant [Grant RGPIN-2020-05395]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2021.0186 .
Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framework to reformulate a BQP problem with linear constraints to a new BQP with an exponential number of variables defined on a graph. This framework relies on the concept of stars in the graph to split the quadratic costs into adjacent and nonadjacent components indicating in-star and out-of-star interactions. We exploit the star-based structure of the new reformulation to develop a decomposition-based column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures. The quadratic component of the problem is dealt with in the column generation master problem and its subproblem. Results indicate the superiority of the framework over one of the state-of-the-art solvers, GUROBI, when applied to various benchmark reformulations with adjacent-only or sparse quadratic cost matrices. The framework outperforms GUROBI in terms of both dual bound and computational time in almost all instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: The authors thank the Mitacs Accelerate Program for providing funding for this project. In addition, B. Rostami gratefully acknowledges the funding provided by the Canadian Natural Sciences and Engineering Research Council (NSERC) under a Discovery Grant [Grant RGPIN-2020-05395]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2021.0186 .
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.
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.
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 multi-linearly constrained separable binary quadratic programming problem (MLSBQP) is a direct extension of the classical singly-linearly constrained separable binary quadratic programming problem (SLSBQP). In the literature, several algorithms have been proposed for SLSBQP which can solve problem instances with millions of variables globally. However, for the case of MLSBQP, the current state-of-the-art solver can only solve problems with up to 40000 binary variables within a reasonable computational time. In this paper, we propose an extremely efficient branch-and-bound algorithm for solving MLSBQP. The main feature of the proposed algorithm is that an efficient dual coordinate ascent algorithm is applied to obtain lower bounds, and the complexity of each inner loop of the dual coordinate ascent algorithm is $ \mathcal{O}(n\log n) $. Our numerical experiments show that the proposed branch-and-bound algorithm can solve MLSBQP with up to millions of variables within only several minutes, and performs much faster than Gurobi when the number of linear constraints is small.
This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.