10h30 - 10h55
Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems
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.
10h55 - 11h20
Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs
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%.
11h20 - 11h45
Predicting SDP bounds of binary quadratic programs in a branch-and-bound 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 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.
11h45 - 12h10
Reformulation of SAT and weighted MAXSAT (or MINSAT) into Polynomial Box-Constrainted 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.