Willem-Jan van Hoeve

Inverse Optimization Without Inverse Optimization: Direct Solution Prediction with Transformer Models

  • Macarena Navarro
  • Willem-Jan van Hoeve
  • Karan Singh
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We present an end-to-end framework for generating solutions to combinatorial optimization problems with unknown components using transformer-based sequence-to-sequence neural networks. Our framework learns directly from past solutions and incorporates the known components, such as hard constraints, via a constraint reasoning module, yielding a constrained learning scheme. The trained model generates new solutions that are structurally … Read more

    A Single-Level Reformulation of Binary Bilevel Programs using Decision Diagrams

  • Sebastian Vasquez
  • Leonardo Lozano
  • Willem-Jan van Hoeve
    • Categories Bilevel Optimization, Combinatorial Optimization, Integer Programming Tags , ,

    Binary bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower’s value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable … Read more

    Column Elimination: An Iterative Approach to Solving Integer Programs

  • Anthony Karahalios
  • Willem-Jan van Hoeve
    • Categories Branch and Cut Algorithms, Dynamic Programming, Integer Programming Tags , , , , ,

    We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then … Read more

    An Introduction to Decision Diagrams for Optimization

  • Willem-Jan van Hoeve
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming Tags , , , , , ,

    This tutorial provides an introduction to the use of decision diagrams for solving discrete optimization problems. A decision diagram is a graphical representation of the solution space, representing decisions sequentially as paths from a root node to a target node. By merging isomorphic subgraphs (or equivalent subproblems), decision diagrams can compactly represent an exponential solution … Read more

    Column Elimination for Capacitated Vehicle Routing Problems

  • Anthony Karahalios
  • Willem-Jan van Hoeve
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Dynamic Programming Tags , , ,

    We introduce a column elimination procedure for the capacitated vehicle routing problem. Our procedure maintains a decision diagram to represent a relaxation of the set of feasible routes, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram and yields a dual bound. The … Read more

    Dual Bounds from Decision Diagram-Based Route Relaxations: An Application to Truck-Drone Routing

  • Z Tang
  • Willem-Jan van Hoeve
    • Categories Integer Programming, Transportation Tags , , , ,

    For vehicle routing problems, strong dual bounds on the optimal value are needed to develop scalable exact algorithms, as well as to evaluate the performance of heuristics. In this work, we propose an iterative algorithm to compute dual bounds motivated by connections between decision diagrams (DDs) and dynamic programming (DP) models used for pricing in … Read more

    Graph Coloring with Decision Diagrams

  • Willem-Jan van Hoeve
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    We introduce an iterative framework for solving graph coloring problems using decision diagrams. The decision diagram compactly represents all possible color classes, some of which may contain edge conflicts. In each iteration, we use a constrained minimum network flow model to compute a lower bound and identify conflicts. Infeasible color classes associated with these conflicts … Read more

    Exact Multiple Sequence Alignment by Synchronized Decision Diagrams

  • Amin Hosseininasab
  • Willem-Jan van Hoeve
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Integer Programming

    This paper develops an exact solution algorithm for the Multiple Sequence Alignment (MSA) problem. In the first step, we design a dynamic programming model and use it to construct a novel Multi-valued Decision Diagrams (MDD) representation of all pairwise sequence alignments (PSA). PSA MDDs are then synchronized using side constraints to model the MSA problem … Read more

    Snow Plow Route Optimization: A Constraint Programming Approach

  • Joris Kinable
  • Willem-Jan van Hoeve
  • Stephen F. Smith
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming

    Many cities have to cope with annual snowfall, but are struggling to manage their snow plowing activities efficiently. Despite the fact that winter road maintenance has been the subject of many research papers over the last 3 decades, very few practical decision support systems have been developed to deal with the complex decision problems involved … Read more

    A Computational Comparison of Optimization Methods for the Golomb Ruler Problem

  • Burak Kocuk
  • Willem-Jan van Hoeve
    • Categories Integer Programming Tags , ,

    The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and … Read more