3 présentations

• 
  08h30 - 08h52

  A Primal Heuristic for Arc Flow Formulations

  • Anthony Karahalios, prés., Carnegie Mellon University
  • van Hoeve Willem-Jan, Carnegie Mellon University

  We propose a primal heuristic for exact methods that solve arc flow formulations, which are used to model discrete optimization problems. An arc flow formulation is an integer linear program over the state-transition graph of a dynamic program, for which a solution is a collection of paths. The primal heuristic finds an initial solution by solving an integer program over a restricted set of paths. This restricted set must be compiled by the exact method. Then, to improve this solution, we develop a large neighborhood search heuristic. First, a destroy phase eliminates a sub-path from each path in the solution. Then, we define a neighborhood by reconnecting the paths using a restricted search based on the state transition function of the dynamic program. Finally, the repair phase solves the arc flow formulation over the neighborhood. We provide a computational evaluation on graph coloring and vehicle routing problems.

• 
  08h52 - 09h14

  Fractional Chromatic Numbers from Exact Decision Diagrams

  • Timo Brand, prés., TU Munich
  • Stephan Held, University of Bonn

  Recently, Van Hoeve proposed an algorithm for graph coloring based on an integer flow formulation on decision Diagrams for stable sets. We prove that the solution to the linear flow relaxation on exact decision diagrams determines the fractional chromatic number of a graph. This settles the question whether the decision diagram formulation or the fractional chromatic number establishes a stronger lower bound. It also establishes that the integrality gap of the linear programming relaxation is O(log n), where n represents the number of vertices in the graph.
  We also conduct experiments using exact decision diagrams and could determine the chromatic number of r1000.1c from the DIMACS benchmark set. It was previously unknown and is one of the few newly solved DIMACS instances in the last 10 years.

• 
  09h14 - 09h36

  Node Selection Heuristics for Multiobjective Restricted Decision Diagrams

  • Rahul Mihir Patel, prés., University of Toronto
  • Khalil Elias, Polytechnique Montreal / University of Toronto
  • David Bergman, University of Connecticut

  In multicriteria decision-making, a user seeks a set of non-dominated solutions to a (constrained) multiobjective optimization problem, the so-called Pareto frontier. In this work, we bring a state-of-the-art method for exact multiobjective integer linear programming, namely decision diagrams (DDs), into the heuristic realm. A DD is a graph representing all feasible solutions to the problem and can be traversed to extract the Pareto frontier. Because the Pareto frontier may be exponentially large, enumerating it over the DD can be time-consuming. In this work, we develop node-selection heuristics (rule-based and learning-based) to construct width-restricted DDs and obtain a high-quality approximation of the Pareto frontier. Specifically, the node selection heuristic aims to identify states in a DD likely to be used by Pareto optimal solutions. Experiments on the multiobjective knapsack, maximum independent set and traveling salesperson problem showcase the effectiveness of our approach.