Diapositiva 1 - Università degli studi di Padova

Diapositiva 1 - Università degli studi di Padova

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

Recently Viewed Presentations

  • Peacekeeping and Stability Operations Institute The Armys only

    Peacekeeping and Stability Operations Institute The Armys only

    *Army MDMP completes actions MCPP covers in Guidance Step . Analyze higher HQs plan or order. Perform IPB. Determine specified/implied/essential tasks. Review available assets. Determine constraints. Identify critical facts and assumptions. Conduct risk assessment. Determine CCIR& EEFI. Determine initial ISR...
  • Operação de terminais e armazéns - WordPress.com

    Operação de terminais e armazéns - WordPress.com

    Armazenagem estratégica Benefícios econômicos: Separação; Cross-docking - a medida que os produtos são recebidos e descarregados no armazém, eles são separados por destino proporcionado redução de custos com frete.
  • Lets go to EUROPE A 10-day tour |

    Lets go to EUROPE A 10-day tour |

    Let's. Watch! Getting out there and experiencing something first hand is the best way to learn.I want to play you a quick video that won't be about our tour specifically, but it will show you what its like when a...
  • The Importance of Biodiversity (biodiversity = the number of ...

    The Importance of Biodiversity (biodiversity = the number of ...

    The Importance of Biodiversity(biodiversity = the number of different species living together in a community or ecosystem). Think of any of the topics we have discussed so far. Come up with as many reasons as you can as to the...
  • Chapter 1 Structure and Bonding - faculty.swosu.edu

    Chapter 1 Structure and Bonding - faculty.swosu.edu

    Physical Properties Main group elements characterized by s/p electrons following the octet rule Metals give up electrons to achieve filled valence shell Nonmetals accept electrons to achieve filled valence shell Conductance Metals have loosely bound e- so they can conduct...
  • Dynamic Neural Network Control (DNNC): A Non-Conventional Neural

    Dynamic Neural Network Control (DNNC): A Non-Conventional Neural

    It has been shown that the DNNC controller strategy is robust enough to perform well over a wide range of operating conditions. Conclusions Q P P y u d d e' ysp y + + + + - - w...
  • Astronomy Club Xmas Quiz 2017

    Astronomy Club Xmas Quiz 2017

    Q44: "Corvus" is the name of the constellation depicting a. Whale. Crow. Dog. Sextant. La Corbière (Jèrriais: La Corbiéthe) is the extreme south-western point of Jersey in St. Brelade. The name means "a place where crows gather", deriving from the...
  • Introduction to Waves

    Introduction to Waves

    Examples include visible light, microwaves, radio waves, x-rays, infrared rays and ultraviolet waves. V = 3.00 x 108 m/s in air or a vacuum Some waves are mechanical waves Mechanical waves require a material medium for their propagation (movement). Sound...