4 Presentations

• 
  10:30 AM - 10:55 AM

  Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems

  • Diego Cattaruzza, Centrale Lille
  • Martine Labbé, GOM, Université Libre de Bruxelles and INRIA
  • Matteo Petris, Centre Inria - Lille Nord Europe
  • Marius Roland, presenter, Trier University
  • Martin Schmidt, Friedrich-Alexander-Universität Erlangen-Nürnberg

  We consider mixed-integer linear optimization problems whose objective involve the quantile (VaR) of random costs. They constitute large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world examples: a maintenance planning problem for electricity networks and a variant of the classic portfolio optimization problem. For these problems, we develop valid inequalities and present an overlapping alternating direction method. Moreover, we discuss an adaptive scenario clustering method for which we prove that it terminates after a finite number of iterations with a global optimal solution. We study the computational impact of all presented techniques on both the maintenance planning problem and the portfolio optimization problem.

• 
  10:55 AM - 11:20 AM

  Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs

  • Charly Robinson La Rocca, presenter, Université de Montréal
  • Emma Frejinger, DIRO and CIRRELT
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

  Current state-of-the-art solvers for mixed-integer programming (MIP) problems are designed to perform well on a wide range of problems. However, for many real-world use cases, problem instances come from a narrow distribution. This has motivated the development of methods that can exploit the information in historical datasets to guide the design of heuristics. Recent works have shown that machine learning (ML) can be integrated with the MIP solver to inject domain knowledge and efficiently close the optimality gap. This hybridization is usually done with deep learning (DL), requiring a large dataset and extensive hyperparameter tuning to perform well. This presentation proposes a method that uses the notion of entropy to efficiently build a model with minimal training data and tuning. We test our method on the locomotive assignment problem (LAP); a recurring real-world problem that is challenging to solve at scale. Experimental results show a speed up an order of magnitude faster than CPLEX with a gap of less than 2%.

• 
  11:20 AM - 11:45 AM

  Predicting SDP bounds of binary quadratic programs in a branch-and-bound framework

  • Can Li, presenter, Polytechnique Montreal
  • Andrea Lodi, Polytechnique Montreal

  SDP type of relaxations provides tight bounds for binary quadratic programs but are more expensive to solve than most LP relaxations. We propose a branch and bound framework for solving binary quadratic programs. By default, only the LP relaxation is solved at each node of the branch-and-bound algorithm. SDP relaxations are solved parsimoniously, i.e., we only wish to solve the SDP relaxations if there is a high chance that it can fathom a given node. To predict whether a node can be fathomed by SDP bound, we propose a method that combines machine learning with solving a convex quadratic program. Our proposed approach is shown to save the number of SDP solves and computational time in a number of maxcut instances we tested.

• 
  11:45 AM - 12:10 PM

  Reformulation of SAT and weighted MAXSAT (or MINSAT) into Polynomial Box-Constrainted Optimization Problems

  • Stéphane Jacquet, presenter, Polytechnique Montréal
  • Sylvain Hallé, Université du Québec à Chicoutimi

  We studied two reformulations of SAT that transform a CNF formula into a polynomial function of degree 3 by relaxing the boolean variables. We prove the links between those polynomials and SAT, especially that they share the same optimal solutions. One of the transformations offers the same kind of results for the variations of SAT: Weighted (Partial) MAXSAT/MINSAT.