4 Presentations

• 
  10:30 AM - 10:55 AM

  Data-Driven Cost-Based Filtering for Constraint Programming

  • Emile Jehaes, presenter, Polytechnique Montréal
  • Tristan Riou, Polytechnique Montréal
  • Augustin Parjadis, Polytechnique Montréal
  • Aaron Ferber, University of Southern California
  • Dilkina Bistra, University of Southern California
  • Louis-Martin Rousseau, Polytechnique Montréal
  • Quentin Cappart, Polytechnique Montréal

  Lagrangian relaxation is a versatile mathematical technique employed to relax constraints in an optimization problem, enabling the generation of dual bounds to prove the optimality of feasible solutions and the design of efficient propagators in constraint programming (such as the weighted circuit constraint). However, the conventional process of deriving Lagrangian multipliers (e.g., using subgradient methods) is often computationally intensive, limiting its practicality for large-scale or time-sensitive problems. To address this challenge, we propose an innovative self-supervised learning approach that harnesses the capabilities of neural networks to exploit the problem structure, aiming to generate accurate Lagrangian multipliers efficiently. We apply this technique to the Lagrangian relaxation of
  widely used constraints (such as the weighted circuit constraint). The core idea is to predict accurate Lagrangian multipliers and to employ them as a warm start for generating the Lagrangian relaxation bounds. These bounds are subsequently utilized to enhance the filtering process carried out by branch-and-bound algorithms. In contrast to much of the existing literature, which primarily focuses on finding feasible solutions, our approach operates on the dual side, demonstrating that learning can also accelerate the proof of optimality. We applied our general approach to the Choco solver and observed that it enhances filtering by effectively utilizing the transmission of Lagrangian multipliers from parent to child nodes.

• 
  10:55 AM - 11:20 AM

  The Driver-Aide Problem: Mixed-Integer vs. Constraint Programming Models

  • Hassan Zohali, presenter, Polytechnique
  • Louis-Martin Rousseau, Polytechnique Montréal
  • Vahid Roshanaei, Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Avenue, Tehran, Iran

  We develop novel constraint programming (CP) models for the Driver-Aide Problem (DAP), which has recently been introduced to reduce last-mile delivery costs, constituting approximately 30–35% of total logistics costs. DAP aims to minimize the total travel and service times of visited customer nodes, beginning and ending at the depot, by optimizing the coordination between the driver and their aide. Specifically, it determines at which nodes the driver and aide should work together to reduce service time and where the driver should drop off the aide before embarking on a traveling salesperson tour to individually serve other nodes, ultimately returning to the aide’s drop-off location. By strategically coordinating their efforts, the driver and aide complete all deliveries in the shortest possible time. Our numerical results demonstrate that our proposed CP models outperform an existing mixed-integer optimization model in the literature, providing a state-of-the-art framework for DAP.

• 
  11:20 AM - 11:45 AM

  Car Resequencing Problem with Makespan Minimization: A Branch-and-Price-and-Cut Approach Integrated with Constraint Programming

  • Guo Xinyi, presenter, Tsinghua University
  • Jean-François Côté, Université Laval

  In the physical car resequencing problem, a sequence of cars is readjusted to a new one via a buffer placed between two adjacent production shops to minimize total cost. This paper introduces a new version with a minimum makespan objective, which arises when carmakers adopt a buffer with multiple first-in-first-out lanes and a reverse lane to rearrange cars to a given sequence. The reverse lane enhances resequencing flexibility by permitting car re-entry in the buffer but increases computational intractability. We propose a time-space network formulation and valid lower bounds for this problem, investigate its computational complexity, as well as develop an exact Branch-and-Price-and-Cut approach integrated with Constraint Programming (BPC-CP). In the BPC-CP approach, a Constraint Programming model is solved to find a feasible solution using the partial integer information from the Branch-and-Price to mitigate its over-fractional issue. Otherwise, valid inequalities are generated and added when the partial information is verified to be infeasible. Computational experiments demonstrate the effectiveness of the proposed approach.

• 
  11:45 AM - 12:10 PM

  Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning

  • Max Bourgeat, presenter, Polytechnique Montréal
  • Quentin Cappart, Cirrelt
  • Louis-Martin Rousseau, Polytechnique Montréal
  • Bessa Swann, École Polytechnique
  • Darius Dabert, École Polytechnique

  Lagrangian decomposition (LD) is a relaxation method that provides a dual bound for constrained optimization problems by decomposing them into more manageable sub-problems. This bound can be used in branch-and-bound algorithms to prune the search space effectively. In brief, a vector of Lagrangian multipliers is associated with each sub-problem, and an iterative procedure (e.g., a sub-gradient optimization) adjusts these multipliers to find the tightest bound. Initially applied to integer programming, Lagrangian decomposition also had success in constraint programming due to its versatility and the fact that global constraints provide natural sub-problems. However, the non-linear and combinatorial nature of sub-problems in constraint programming makes it computationally intensive to optimize the Lagrangian multipliers with sub-gradient methods at each node of the tree search. This currently limits the practicality of LD as a general bounding mechanism for constraint programming. To address this challenge, we propose a self-supervised learning approach that leverages neural networks to generate multipliers directly, yielding tight bounds. This approach significantly reduces the number of sub-gradient optimization steps required, enhancing the pruning efficiency and reducing the execution time of constraint programming solvers. This contribution is one of the few that leverage learning to enhance bounding mechanisms on the dual side, a critical element in the design of combinatorial solvers. This work presents a generic method for learning valid dual bounds in constraint programming. We validate our approach on two challenging combinatorial problems: The multi-dimensional knapsack problem and the shift scheduling problem. The results show that our approach can solve more instances than the standard application of LD to constraint programming, reduce execution time by more than half, and has promising generalization ability through fine-tuning.