4 Presentations

• 
  10:30 AM - 10:55 AM

  Introducing some linearization techniques for the quadratic unconstrained binary optimization problem and their comparison with the classical models.

  • Navpreet Kaur, presenter,
  • Abraham Punnen,

  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 well-known 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.
• 
  10:55 AM - 11:20 AM

  Learning in Local Branching

  • Defeng Liu, presenter, Polytechnique Montreal
  • Andrea Lodi, Polytechnique Montreal
  • Matteo Fischetti, University of Padua

  Finding high-quality solutions to mixed-integer 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 so-called 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.
• 
  11:20 AM - 11:45 AM

  Logical constraints without binary variables: The continuous quadrant penalty formulation

  • Sonia Cafieri, ENAC
  • Andrew R. Conn, IBM Research
  • Marcel Mongeau, presenter, ENAC, Université de Toulouse, France

  We propose a continuous-optimization formulation of logical
  constraints that does not rely on the introduction of binary variables
  (contrary to the classical big-M and complementary
  formulations). Based on the simple idea of guiding the search of a
  continuous-optimization method towards the parts of the domain where
  the logical constraint is satisfied, we introduce a smooth
  penalty-function formulation of logical constraints. The continuous
  quadrant penalty (CQP) formulation allows the direct use of
  state-of-the-art continuous optimization solvers for problems whose
  only combinatorial aspect comes from their logical constraints. Its
  effectiveness has been demonstrated on a real-world application in air
  transportation.
• 
  11:45 AM - 12:10 PM

  Ranking decomposition for the discrete ordered median problem

  • Claudio Contardo, ESG UQÀM / GERAD
  • Marilène Cherkesly, ESG UQÀM
  • Matthieu Gruson, presenter, UQÀM - CIRRELT

  Given a set N of size n, a non-negative, integer-valued distance matrix D of dimensions n*n, an integer p and an integer-valued 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 p-center, the p-median and the obnoxious median problem. We introduce an exact branch-and-bound algorithm to solve the DOMP. This branch-and-bound 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.