We consider binary quadratically constrained quadratic problems and propose a new approach based on decomposition to generate strong bounds. This new relaxation is based on the Boolean Quadric Polytope and is solved via a Dantzig-Wolfe Reformulation in matrix space. For block-decomposable problems, we extend the relaxation and analyze the theoretical properties of this new decomposition.
If overlapping size of blocks is at most two, we establish equivalence to the one based on the Boolean Quadric Polytope. We prove that this equivalence does not hold if the sparsity graph is not chordal and we conjecture that equivalence holds for any block structure with a chordal sparsity graph. Numerical results show that the proposed approach yields very good bounds in reasonable time.

This paper provides exact and approximate solution methods for convex binary quadratic programs with linear constraints (CBQP). We reformulate the problem using spectral decomposition and apply principal component analysis (PCA) to derive approximate solutions. The quality of the resulting solutions is assessed by determining worst-case optimality gaps. Furthermore, we show how to extend this approximate method to an exact strategy by reformulating it into a mixed-integer quadratic program and developing a Benders-type decomposition method to derive optimal solutions for the original CBQP. We apply this methodology to routing optimization with stochastic and correlated travel times, demonstrating its effectiveness across problem instances with different structures.

We introduce a new polyhedral framework for characterizing instances of binary quadratic programs that are linearizable, which means that the quadratic objective can be equivalently rewritten as a linear function in such a manner that preserves the objective function value at all feasible binary solutions. Of particular interest to our study are problems that are challenging when the objective function is quadratic but are readily solvable in the linear case, such as the quadratic assignment problem (QAP) and the quadratic minimum spanning tree problem (QMSTP). Our main result is that an instance of such a problem is linearizable if and only if the quadratic cost coefficients can be used to create a linear equation in a lifted variable space that is valid for the affine hull of a specially constructed discrete set. In this talk, we will discuss how viewing the concept of linearizability through this new polyhedral lens has interesting implications for both the QAP and QMSTP, leading to the resolution of open questions in each case. Furthermore, we will show how our framework for studying the linearizable property can provide insights into the identification and characterization of other families of problem instances that, while not linearizable, can still be solved in polynomial time.

Given binary products in the objective function or constraints, the inductive linearization technique may serve as a computationally attractive compromise between the (often weak) "standard" linearization and the (often large) result of applying the reformulation linearization technique (RLT). In the best case, inductive linearizations may be more constraint-side compact than the standard linearization, and still provide a continuous relaxation that is at least as tight or even close to the one of a complete first-level RLT. Prominent combinatorial optimization problems where this applies are for instance the Quadratic Assignment, the Quadratic Matching, and the Quadratic Traveling Salesman Problem. We shed light on some properties of a program that appear particularly suited to experience computational advantage when applying the inductive linearization technique in combination with a MIP solver. doi: 10.1007/s10288-023-00537-5