Join us in Dublin, Ireland for the Annual EURO Conference

Gurobi Optimization will be presenting and exhibiting at the 30th European Conference on Operational Research. This conference will be held on June 23 – June 26 in Dublin, Ireland. Gurobi Optimization will be very active at this conference, with talks and an exhibit booth.

This is a great opportunity for those interested in learning about the significant new features in the upcoming version 9.0 of the Gurobi Optimizer, and more.

Session RLT Cuts for Mixed Integer Linear Programming
Presented by Dr. Tobias Achterberg
Location Room L249, Software for mixed-integer linear optimization (MB-49)
Time Monday, 10:30 - 12:00

Reformulation Linearization Technique (RLT) cuts are an important ingredient to solve non-convex mixed integer quadratically constrained problems (MIQCPs). Many solvers for this problem class work on an LP relaxation of the problem, in which the McCormick relaxation is used to linearize the quadratic constraints. To do so, one introduces auxiliary variables to represent the product terms that appear in the quadratic constraints. The main idea of RLT cuts is to multiply a linear constraint by a problem variable and then substitute the resulting product terms with the existing auxiliary product variables. The resulting constraint is again linear and can be added as a cutting plane to the LP relaxation. In this talk we show how the same technique can be applied to mixed integer linear programs. Variables that model products of two binary variables or a binary and a non-binary variable are discovered in the MILP model and used to substitute the products in the RLT cut scheme. Computational results are presented to illustrate the effect of these cuts in the current development version of Gurobi 9.0.

Session SDP based BQP relaxation strengthening
Presented by Dr. Robert Luce
Location Room L249, Software for mixed-integer linear optimization (MB-49)
Time Monday, 12:30 - 14:00
We consider the solution of binary quadratic programming (BQP) problems in the standard branch-and-bound framework. Unlike for the more general mixed-integer quadratic programming problem, the idempotency of binary variables allows for regularization of the objective function without altering the set of optimal solutions. Such regularization can serve two purposes. First, it can be applied to ensure the convexity of the continuous relaxation, and secondly one can take advantage of this freedom to strengthen the root relaxation of (convex) BQP problems. In both cases choosing the "best" (in a particular sense) regularization results in an auxiliary semi-definite programming problem. We discuss different computational techniques for the exact and approximate solution of this SDP, along with some simplistic heuristics. An overall assessment of this approach, based on the implementation in Gurobi v8.1 on a large set of BQP’s will be given.