SCRO / Journées de l'optimisation
HEC Montréal, 2931 mai 2023
CORSJOPT2023
HEC Montréal, 29 — 31 mai 2023
MMI Mathematical Modelling I
31 mai 2023 10h30 – 12h10
Salle: StHubert (vert)
Présidée par Matthieu Gruson
4 présentations

10h30  10h55
Introducing some linearization techniques for the quadratic unconstrained binary optimization problem and their comparison with the classical models.
The Quadratic unconstrained Binary Optimization problem (QUBO) is equivalent (in the optimization sense) to the maximum cut problem, maximum weight stable set problem, maximum weight principal minor problem, among others. QUBO received considerable attention recently from the researchers and practitioners, particularly due to the emerging technology of quantum inspired computers. QUBO seeks a binary vector that minimizes (or maximizes) a quadratic function.
In this study, we revisited some of the classical explicit and compact linearizations from the literature that solve Quadratic binary problem as a mixed integer linear programming problem. We are providing several new linearization techniques for QUBO. Some of the linearization models we introduced have comparatively lesser number of constraints than some classical linearizations but still strong LP relaxation bounds. A comparison of these models with wellknown linearization models from the literature is provided, both theoretically as well as experimentally. As per our experimental results, some of these new techniques can be considered as an alternative for computing lower bounds for QUBO as well as for computing heuristic solutions for the problem. 
10h55  11h20
Learning in Local Branching
Finding highquality solutions to mixedinteger linear programming problems (MILPs) is of great importance for many practical applications. In this respect, the refinement heuristic local branching (LB) has been proposed to produce improving solutions and has been highly influential for the development of local search methods in MILP. The algorithm iteratively explores a sequence of solution neighborhoods defined by the socalled local branching constraint, namely, a linear inequality limiting the distance from a reference solution. For a LB algorithm, the choice of the neighborhood size is critical to performance. In this work, we study the relation between the size of the search neighborhood and the behavior of the underlying LB algorithm, and we devise a leaning based framework for predicting the best size for the specific instance to be solved. Furthermore, we have also investigated the relation between the time limit for exploring the LB neighborhood and the actual performance of LB scheme, and devised a strategy for adapting the time limit. We computationally show that the neighborhood size and time limit can indeed be learned, leading to improved performances and that the overall algorithm generalizes well both with respect to the instance size and, remarkably, across instances.

11h20  11h45
Logical constraints without binary variables: The continuous quadrant penalty formulation
We propose a continuousoptimization formulation of logical
constraints that does not rely on the introduction of binary variables
(contrary to the classical bigM and complementary
formulations). Based on the simple idea of guiding the search of a
continuousoptimization method towards the parts of the domain where
the logical constraint is satisfied, we introduce a smooth
penaltyfunction formulation of logical constraints. The continuous
quadrant penalty (CQP) formulation allows the direct use of
stateoftheart continuous optimization solvers for problems whose
only combinatorial aspect comes from their logical constraints. Its
effectiveness has been demonstrated on a realworld application in air
transportation. 
11h45  12h10
Ranking decomposition for the discrete ordered median problem
Given a set N of size n, a nonnegative, integervalued distance matrix D of dimensions n*n, an integer p and an integervalued weight vector lambda, the discrete ordered median problem (DOMP) consists of selecting a subset C of exactly p points from N (also referred to as the centers) so as to: 1) assign each point in N to its closest center in C; 2) rank the resulting distances (between every point and its center) from smallest to largest in a sorted vector that we denote d; 3) minimize the scalar product . The DOMP generalizes several classical location problems such as the pcenter, the pmedian and the obnoxious median problem. We introduce an exact branchandbound algorithm to solve the DOMP. This branchandbound decouples the ranking attribute of the problem to form a series of simpler subproblems which are solved using innovative binary search methods. We consider several acceleration techniques such as warm starts, primal heuristics, variable fixing and symmetry breaking. We perform a thorough computational analysis and show that the proposed method is competitive against several MIP models from the scientific literature. We also comment on the limitations of our method and propose avenues of future research.