Sven Mallach State-of-the-art exact methods for the Maximum Cut problem are based on solving linear and semidefinite programming relaxations embedded into a branch-and-bound algorithm. For linear programming formulations, it was shown recently that it is thereby sufficient to enforce the integrality of the variables associated with the edges of a spanning tree. Our first contribution is to … Read more
When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more
We systematically investigate the potentials of improving the lower bound obtained with a linear relaxation of the Quadratic Unconstrained Binary Optimization problem by integrating curvature information from an accompanying quadratic convex underestimator via gradient inequalities. On the one hand, we exemplify to which extent this hybrid approach may provide a lower bound that is strictly … Read more
We report on results concerning the polyhedral structure of, and integer linear programming formulations for, the quadratic linear ordering problem. Specifically, we provide a deeper analysis of the characteristic equation system that takes part in the minimal description of the convex hull of its feasible solutions, and we determine an accessible description of a restricted … Read more
We present a family of integer programming formulations for the maximum cut problem. These formulations encode the incidence vectors of the cuts of a connected graph by employing a subset of the odd-cycle inequalities that relate to a spanning tree, and they require only the corresponding edge variables to be integral explicitly. They so describe … Read more
The computational performance of inductive linearizations for binary quadratic programs in combination with a mixed-integer programming solver is investigated for several combinatorial optimization problems and established benchmark instances. Apparently, a few of these are solved to optimality for the first time. Citationpreprint (no internal series / number): University of Bonn, Germany June 11, 2021ArticleDownload View … Read more