Intersection Cuts from Bilinear Disjunctions Matteo Fischetti, University of Padova (joint work with Michele Monaci, University of Bologna) Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 1 Non-convex MIQP Goal: implement a Mixed-Integer (non-convex) Quadratic solver Two approaches: 1. start with a continuous QP solver and add enumeration on top of

it implement B&B to handle integer var.s 2. start with a MILP solvers (B&C) and customize it to handle the non-convex quadratic terms add McCormick & spatial branching PROS: CONS: This talk goes for 2. Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 2 MIQP as a MILP with bilinear eq.s The fully-general MIQP of interest reads

and can be restated as Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 3 McCormick inequalities To simplify notation, rewrite the generic bilevel eq. as: Obviously

(just replace xy by z in the products on the left) Note: mc1) and mc2) can be improved in case x=y gradients cuts Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 4 Spatial branching McCormick inequalities are not perfect they are tight only when x and/or y are at their lower/upper bound

at some B&C nodes, it may happen that the current (fractional or integer) solution satisfies all MC inequalities but some bilinear eq.s z = xy are still violated (we call this #bilinear_infeasibility) we need a bilinear-specific branching (the usual MILP branching on integrality does not work if all var.s are integer already) Standard Spatial Branching: if z* = x* y* is violated, branch on (x x*) OR (x x*) to make the upper (resp. lower) bound on x tight at the left (resp. right) child node thus improving the corresponding MC inequality Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 5

A new branching rule Shifted Spatial Branching: let * := z* - x* y* ; if * > 0, branch on (x x* - ) OR (x x* - ) where is defined so as to balance the violation of the two child nodes (case * < 0 is similar) Left branch (ux = x* - ) violation of of the upper bound ux Right branch (lx = x* - ) violation of for the MC ineq.

by choosing New Branching Rule: among all violated z* = x* y*, select the one maximizing the balanced violation Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 6 The branching procedure Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 7

Intersection Cuts (ICs) Intersection cuts (Balas, 1971): a powerful tool to separate a point x* from a set X by a liner cut All you need is (love, but also) a cone pointed at x* containing all x X a convex set S with x* (but no x X) in its interior If x* vertex of an LP relaxation, a suitable cone comes for the LP basis Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 8 Bilinear-free sets

Observation: given an infeasible point x*, any branching disjunction violated by x* implicitly defines a convex set S with x* (but no feasible x) in its interior Thus, in principle, one could always generate an IC instead of branching not always advisable because of numerical issues, slow convergence, tailing off, cut saturation, etc. #LikeGomoryCuts Candidate branching disjunctions (supplemented by MC cuts) are

the 1- and 2-level (possibly shifted) spatial branching conditions: Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 9 IC separation issues IC separation can be probematic, as we need to read the cone rays from the LP tableau numerical accuracy can be a big issue here! For MILPs, ICs like Gomory cuts are not mandatory (so we can skip their generation in case of numerical problems), but for MIBLPs they are more instrumental #SeparateOrPerish Notation: consider w.l.o.g. an LP in standard form and no var. ubs

be the LP relaxation at a given node be the bilevel-free set be the disjunction to be satisfied by all feas. sol.s Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 10 Numerically safe ICs A single valid inequality can be obtained by taking, for each variable, the worst LHS Coefficient (and RHS) in each disjunction To be applied to a reduced form of each disjunction where the coefficient of all basic

variables is zero (kind of LP reduced costs) Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 11 B&C implementation Implementation using IBM ILOG Cplex 12.8 using callbacks: Lazy constraint callback: separation of MC inequalities for integer sol.s Usercut callback: not needed (and sometimes detrimental) Branch callback: our new spatial branching Incumbent callback: very-last resort to kill a bilinear-infeasible integer solution (when everything else fails e.g. because of tolerances)

MILP heuristics (kindly provided by the MILP solver): active at their default level MIQP-specific heuristics: not implemented yet12 - 19, 2019 Bellairs Workshop on Discrete Optimization, April 12 Computational analysis

Three algorithms under comparison SCIP: the general-purpose solver SCIP (vers. 5.0.1 using CPLEX 12.8 as LP solver + IPOPT 3.12.9 as nonlinear solver) basic: our branch-and-cut algorithm without intersection cuts with-IC: intersection cuts separated at each node where the LP solution is integral Single-thread runs (parallel runs not allowed in SCIP) with a time limit of 1 hour on a standard PC Intel @ 3.10 GHz with 16 GB ram Testbed: all quadratic instances in MINLPlib (700+ instances) but some instances removed as root LP was unbounded 620 instances left, 248 of which solved by all methods in 1 hour Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019

13 Results Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 14 More statistics Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 15

ICs can make a difference Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 16 Thanks for your attention! Paper available at http://www.dei.unipd.it/~fisch/papers/

Slides available at http://www.dei.unipd.it/~fisch/papers/slides/ . Bellairs Workshop on Discrete Optimization, April 12 - 19, 2019 17