Journées de l'optimisation 2022
HEC Montréal, Québec, Canada, 16 — 18 mai 2022
MA10  Combinatorial optimization
16 mai 2022 10h30 – 12h10
Salle: Banque Scotia (bleu)
Présidée par Stéphane Jacquet
4 présentations

10h30  10h55
Exact and Heuristic Solution Techniques for MixedInteger Quantile Minimization Problems
We consider mixedinteger linear optimization problems whose objective involve the quantile (VaR) of random costs. They constitute largescale problems that are very hard to solve for realworld instances. We motivate the study of this problem class by two important realworld 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.

10h55  11h20
Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs
Current stateoftheart solvers for mixedinteger programming (MIP) problems are designed to perform well on a wide range of problems. However, for many realworld 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 realworld 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%.

11h20  11h45
Predicting SDP bounds of binary quadratic programs in a branchandbound framework
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 branchandbound 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.

11h45  12h10
Reformulation of SAT and weighted MAXSAT (or MINSAT) into Polynomial BoxConstrainted Optimization Problems
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.