4 Presentations

• 
  10:30 AM - 10:55 AM

  Acquiring and Selecting Implied Constraints with an Application to the BinSeq and Partition Global Constraints

  • Jovial Cheukam Ngouonou, presenter, Université Laval-IMT Atlantique
  • Ramiz Gindullin, IMT Atlantique
  • Claude-Guy Quimper, Université Laval
  • Nicolas Beldiceanu, IMT Atlantique
  • Rémi Douence, IMT Atlantique

  We propose a machine-assisted approach to synthesise implied constraints for global constraints based on combinatorial objects. By reusing the Bound Seeker (BS), we generate thousands of relationships between features. We present a scalable algorithm that automatically selects the relationships that filter the
  most, which we manually prove. We consider the Partition and the BinSeq constraints, which model the
  different ways of dividing a collection of objects into clusters, or the repartition of shifts in a 0–1 sequence. We use Partition and BinSeq in the Balanced Academic Curriculum Problem (BACP), and the Balanced Shift-Scheduling
  Problem (BSSP), where we optimise the distribution of the work to balance the workload. For 2 models of the BACP and 2 models of the BSSP, we show how the filtering inferred by the BS improves the cost of the solution found on
  different solvers. This filtering proved optimality for all CSPLib instances of the BACP.

• 
  10:55 AM - 11:20 AM

  Shaping Reward Signals in Reinforcement Learning Using Constraint Programming

  • Chao Yin, presenter, Polytechnique Montréal
  • Quentin Cappart, Cirrelt
  • Gilles Pesant, Polytechnique Montréal

  Reinforcement learning is a machine learning paradigm in which an agent learns through interaction a policy, that is what sequence of actions to take in some environment in order to maximize the reward it receives. Reward shaping modifies the reward function in an attempt to accelerate agent training. Under some conditions, potential-based reward shaping (pbrs) preserves the optimal policies of the original problem. We propose a pbrs method that automatically derives shaped rewards from a constraint programming (cp) model of the environment and from the probability mass functions over the domains of its variables, as provided by the cpbp framework. In the context of an ai planning task, we investigate the effect of cp modeling choices on the
  effectiveness of our reward shaping method. Our experiments show that our method significantly accelerates training while being rather insensitive to modeling choices, and that the resulting agent’s performance scales well beyond instance sizes seen during training.

• 
  11:20 AM - 11:45 AM

  Optimizing 2D Cutting: A Bin Packing Approach to Minimize Scraps and Maximize their Reusability

  • Manuel Chastenay, presenter, Université Laval
  • Claude-Guy Quimper, Université Laval
  • Jonathan Gaudreault, Université Laval
  • Xavier Zwingmann, Université Laval

  In industrial settings, cutting predefined pieces from one or multiple sheets of material is a common optimization challenge. This problem can be formulated as a variant of the 2D bin packing problem, where the edges of the pieces define the cut lines. This paper presents a constraint programming model developed in collaboration with a construction industry partner in a way to minimize scrap waste generated when cutting insulation pieces. Additionally, the model introduces an objective function designed to maximize the future reusability of leftover material. To fully leverage the model's efficiency, an initial process transforms irregular insulation pieces into rectangles using one of four processing methods. A comparative analysis is conducted to evaluate the impact of these methods, as well as to benchmark the model’s results against the partner's manual approach.

• 
  11:45 AM - 12:10 PM

  Guiding Molecule Generation using Constraint Programming

  • David Saikali, presenter, Polytechnique Montreal
  • Gilles Pesant, Polytechnique Montreal

  Drug discovery is a very time-consuming and costly endeavour due to its huge design space and to the lengthy and failure-fraught process of bringing a product to market. Automating the generation of candidate molecules exhibiting some of the desired properties can help. Among the standard formats to encode molecules, SMILES is a widespread string representation. We propose a constraint programming model showcasing the grammar constraint to express the design space of organic molecules using the SMILES notation. We show how some common physicochemical properties — such as molecular weight and lipophilicity — and structural features can be expressed as constraints in the model. We also contribute a weighted counting algorithm for the grammar constraint, allowing us to use a belief propagation heuristic to guide the generation. Our experiments indicate that such a heuristic is key to driving the search towards valid molecules. The addition of belief propagation to our model also allows us to combine this approach with generative neuronal models, using belief propagation to affect the probabilities and guide the generation towards more feasible solutions.