4 Presentations

• 
  04:45 PM - 05:07 PM

  An Exact Framework for Solving the Space-Time Dependent TSP

  • Isaac Rudich, presenter, Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montréal
  • Quentin Cappart, Polytechnique Montréal
  • Michael Röhmer, Universität Bielefeld
  • Manuel López-Ibáñez, University of Manchester

  Many real-world scenarios involve solving bi-level optimization problems in which there is an outer discrete optimization problem, and an inner problem involving expensive or black-box computation. This arises in space-time dependent variants of the Traveling Salesman Problem, such as when planning space missions that visit multiple astronomical objects. Planning these missions presents significant challenges due to the constant relative motion of the objects involved. There is an outer combinatorial problem of finding the optimal order to visit the objects and an inner optimization problem that requires finding the optimal departure time and trajectory to travel between each pair of objects. The constant motion of the objects complicates the inner problem, making it computationally expensive. This paper introduces a novel framework utilizing decision diagrams (DDs) and a DD-based branch-and-bound technique, Peel-and-Bound, to achieve exact solutions for such bi-level optimization problems, assuming sufficient inner problem optimizer quality. The framework leverages problem-specific knowledge to expedite search processes and minimize the number of expensive evaluations required. As a case study, we apply this framework to the Asteroid Routing Problem (ARP), a benchmark problem in global trajectory optimization. Experimental results demonstrate the framework's scalability and ability to generate robust heuristic solutions for ARP instances. Many of these solutions are exact, contingent on the assumed quality of the inner problem's optimizer.

• 
  05:07 PM - 05:29 PM

  Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming

  • Minori Narita, presenter, University of Toronto
  • Ryo Kuroiwa, National Institute of Informatics, Japan
  • J. Christopher Beck, University of Toronto

  Domain-Independent Dynamic Programming (DIDP) is a state-space search paradigm based on dynamic programming for combinatorial optimization. In its current implementation, DIDP guides the search using user-defined dual bounds. Reinforcement learning (RL) is increasingly being applied to combinatorial optimization problems, and shares several key structures with DP, being represented by the Bellman equation and state-based transition systems. We propose using reinforcement learning to obtain a heuristic function to guide the search in DIDP. We develop two RL-based guidance approaches: value-based guidance using Deep Q-Network (DQN) and policy-based guidance using Proximal Policy Optimization (PPO). Our experiments indicate that RL-based guidance outperforms standard DIDP with the same number of node expansions. However, the experiments also reveal challenges, including long solve times and difficulties in providing effective guidance in constrained domains where RL training is particularly challenging.

• 
  05:29 PM - 05:51 PM

  A decision diagram approach for the job shop scheduling problem with chance constraints.

  • Nicolás Casassus, presenter, Pontificia Universidad Católica de Chile
  • Gustavo Angulo, Pontificia Universidad Católica de Chile
  • Margarita Castro, Pontificia Universidad Catolica de Chile

  The Chance Constraint Job Shop Scheduling Problem (CC-JSSP) assigns jobs with uncertain processing times to machines, ensuring that each machine's availability constraints are met with a certain probability. We present a decomposition approach where the master problem assigns jobs to machines, and the subproblems schedule the jobs on each machine while verifying the solution's feasibility under the chance constraint. We proposed two different Decision Diagrams (DD) formulations to solve the subproblems and generate cuts. The first formulation employs DDs with a linear cost function, while the second uses a non-linear cost function to reduce the diagram's size. We show how to generate no-good and irreducibly infeasible subsystems (IIS) cuts based on our DDs. Additionally, we extend the cuts Lozano & Smith (2018) proposed to solve two-stage stochastic programming models. Our DD-based methodology outperforms traditional integer programming models designed to solve the CC-JSSP in several instances.

• 
  05:51 PM - 06:13 PM

  Modeling and solving the tool switching problem

  • Pierre Schaus, presenter, ucl
  • Emma Legrand, UCLouvain
  • Daniele Catanzaro, UCLouvain
  • Vianney Coppe, Hexaly

  We present preliminary results on a new library for solving dynamic programming problems.
  The library incorporates various algorithms: variants of the A* algorithm and branch-and-bound decision diagrams.
  We demonstrate how to solve the Tool Switching Problem within this library, a problem that combines elements of sequencing and machine configuration.
  Additionally, we compare the results obtained for this problem against state-of-the-art methods, including a Mixed Integer Programming (MIP) model and a Branch-and-Bound approach.