MB7 - CP Applications

In high school timetabling, some institutions adopt a university-like structure in which students follow different curricula and multiple sections are offered for each course, without pre-assigning students to specific sections. In such settings, student sectioning and timetabling are strongly interdependent. Several Canadian high schools construct their schedules according to predefined block patterns designed to ensure a balanced distribution of instructional time. While this structure eliminates many classical timetabling constraints, it introduces a specific challenge: courses occupying half-blocks must be paired to form full blocks, as it directly impacts the balance of students across sections. Based on this context, we introduce a constraint programming approach to generate a feasible half-block courses schedule leading to good student balancing. The model is designed to enhance computational efficiency, accommodate additional practical constraints, and reduce the need for manual adjustments by scheduling operators. The approach is evaluated on anonymized real-world data from Canadian high schools for the 2024-2025 academic year, provided by Dash Computer Solutions, a company responsible for the annual design of many high school schedules in Quebec, and is integrated with their existing student sectioning algorithm.

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 desired molecules.

Search and rescue operations require planning methods that maximize the probability of finding survivors. We study the optimal search path problem, where a searcher trajectory is optimized over an area of interest. We show how approximate decision diagrams strengthen dual bounds and reduce the search tree in a branch-and-bound.

To conduct diagnostic assessments and monitor patients with reading difficulties, speech-language pathologists must draft targeted texts that integrate specific graphemes (speech sounds) at precise locations within words or sentences. Because this task is time-consuming, using LLMs to automate it is attractive but, as demonstrated by the COLLIE benchmark, LLMs struggle to adhere to such strict constraints. The GeAI-BLAnC neuro-symbolic architecture combines Constraint Programming (CP) and an LLM for constrained sequence generation tasks. We apply it here to generate clinical texts for speech therapy. We highlight inherent trade-offs between a few CP modeling choices and report preliminary results. This work is conducted in collaboration with PhonIA, a startup specialized in speech therapy.