4 présentations

• 
  10h30 - 10h55

  Constraint programming and global constraints: a new approach to compute complexity

  • Jean-Charles Régin, prés., Université Côte d'Azur

  Global constraints are very important in CP. Algorithms are often compared on the basis of their worst-case complexity. However, CP Solvers use these algorithms in a very special way, by calling them very often. They are therefore often called for nothing, and it is these calls that become costly and sometimes prevent the use of these constraints. We propose a new way of looking at complexity: we differentiate between the case where a filtering (i.e. domain reduction) occurs and the case where the call is useless. Algorithms that are fast in the first case and slower in the second can then be preferred. We demonstrate this approach experimentally.

• 
  10h55 - 11h20

  Learning and fine-tuning a generic value-selection heuristic inside a constraint programming solver

  • Tom Marty, MILA
  • Léo Boisvert, prés., Polytechnique Montréal
  • Tristan François, Polytechnique Paris
  • Pierre Tessier, Polytechnique Paris
  • Louis Gautier, Polytechnique Paris
  • Louis-Martin Rousseau, Polytechnique Montréal
  • Quentin Cappart, Polytechnique Montréal

  This paper addresses a critical challenge in constraint programming (CP): the scarcity of effective generic value-selection heuristics, despite their importance in solver efficiency. While variable-selection heuristics are well-developed, value-selection strategies often require problem-specific expertise that many practitioners lack.
  We present a novel machine learning framework that automatically learns high-quality value-selection heuristics directly within a CP solver. Our approach combines three key innovations: (1) a restart-based training procedure using reinforcement learning that eliminates backtracking complexities during training, (2) a propagation-based reward function that provides meaningful feedback throughout the search process, and (3) a heterogeneous graph neural network architecture that effectively represents CP models with their variables, constraints, and values.
  Experiments on graph coloring, maximum independent set, maximum cut, and minimum vertex cover problems demonstrate that our learned heuristics consistently outperform established approaches like impact-based search and activity-based search. For maximum cut problems with 50 nodes, our approach achieved an optimality gap of 0.09, significantly better than the 0.17 gap of DFS while exploring 27% fewer nodes. On maximum independent set with 100 nodes, our method reduced the optimality gap to 0.02 compared to 0.09-0.10 for baseline approaches.
  Remarkably, even a single dive in the search tree with our learned heuristic often produces competitive solutions, demonstrating its ability to make intelligent branching decisions without backtracking. For graph coloring with 80 nodes, our method finds optimal solutions by exploring just 120 nodes, compared to over 7,000 nodes required by traditional approaches.
  Our framework also shows promising generalization capabilities across problem sizes and transferability between related problem classes. Fine-tuning experiments demonstrate that a model trained on maximum independent set can be effectively adapted to maximum cut problems, reducing the optimality gap from 0.33 to 0.09 with minimal additional training.

• 
  11h20 - 11h45

  A robust scheduling framework for short-term planning of underground mining operations using constraint programming: A Canadian case study

  • Reza Shahin, prés., Department of Mathematics and Industrial Engineering, Polytechnique Montreal
  • Michel Gamache, Polytechnique Montréal
  • Gilles Pesant, Polytechnique Montréal

  Underground mining presents significant challenges due to escalating costs and reduced profit margins, particularly as extraction reaches greater depths. These operations follow a cyclical workflow, comprising sequential tasks—such as drilling, charging, blasting, and loading—that rely on specialized equipment to progress each stage efficiently. Given the complexity and dependency of each step, effective scheduling of tasks and equipment is crucial for optimizing resource management, ensuring operational efficiency, and maintaining profitability. This study introduces a robust scheduling framework tailored specifically for these operations, with a practical application to a Canadian underground mine. By leveraging Constraint Programming, the framework addresses both production and development scheduling across a one-month planning horizon, accounting for the multifaceted nature of the problem. The study models and solves the scheduling problem through three distinct approaches, each capturing varying degrees of certainty and complexity: (1) a deterministic model where task processing times are fully known and fixed, (2) a deterministic model incorporating uncertain processing times, and (3) a two-stage multi-scenario stochastic model where task processing times are generated by a probability distribution, enabling multiple scenarios being solved simultaneously. The stochastic approach is particularly beneficial in handling the inherent uncertainties of the problem, allowing for adaptability to variable real-world conditions. Through a comparative analysis of the three models, this research underscores the value of accounting for uncertainty, revealing that the stochastic model not only achieves an optimal scheduling outcome but also produces schedules that are significantly more resilient and adaptable to unexpected disruptions. By demonstrating the effectiveness of stochastic scheduling in enhancing operational robustness, this framework provides a pathway for improving decision-making in underground mining, offering a scalable solution for resource-intensive and high-risk environments.

• 
  11h45 - 12h10

  Guiding Search with Belief Propagation for Constraint Optimisation Problems

  • Axel Baudot, prés., Polytechnique Montréal
  • Gilles Pesant, Polytechnique Montréal

  As a generalisation of support propagation in Constraint Programming which performs domain filtering, belief propagation infers the distribution of solutions and guides search effectively for Constraint Satisfaction Problems.
  It implements the sum-product message-passing algorithm and performs weighted model counting on individual constraints.
  We show the limitations of the sum-product algorithm for Constraint Optimisation Problems and investigate an alternative message-passing algorithm, max-product.
  We revisit weighted model counting for some of the main global constraints and take advantage of opportunities to make them more efficient in this setting.
  We evaluate our proposal empirically on a diverse set of Constraint Optimisation Problems.