Pierre Schaus

SoCS Conference 2022 Conference Paper

A Conflict Avoidance Table for Continuous Conflict-Based Search (Extended Abstract)

• Vianney Coppé
• Pierre Schaus

Conflict-Based Search is a state-of-the-art algorithm solving the Multi-Agent Path Finding problem. Given multiple agents with start and goal locations, the problem is to find a set of collision-free paths of minimal cost. Continuous Conflict-Based Search is a recent adaptation of this algorithm for continuous time and agents with physical shapes. However, an important ingredient has not been adapted to this continuous version: the Conflict Avoidance Table. It is used as a tie-breaking strategy in single-agent search phases to favor paths causing fewer conflicts with the other agents. This paper explains how the R-Tree can be used as a Conflict Avoidance Table for Continuous Conflict-Based Search. The experiments show that using the Conflict Avoidance Table can reduce the number of nodes expanded by the algorithm by a large margin. As a result, the solving time is improved proportionally and especially when using the implementation based on R-Trees as opposed to a naive implementation.

IJCAI Conference 2022 Conference Paper

Large Neighborhood Search with Decision Diagrams

• Xavier Gillard
• Pierre Schaus

Local search is a popular technique to solve combinatorial optimization problems efficiently. To escape local minima one generally uses metaheuristics or try to design large neighborhoods around the current best solution. A somewhat more black box approach consists in using an optimization solver to explore a large neighborhood. This is the large-neighborhood search (LNS) idea that we reuse in this work. We introduce a generic neighborhood exploration algorithm based on restricted decision diagrams (DD) constructed from the current best solution. We experiment DD-LNS on two sequencing problems: the traveling salesman problem with time windows (TSPTW) and a production planning problem (DLSP). Despite its simplicity, DD-LNS is competitive with the state-of-the-art MIP approach on DLSP. It is able to improve the best known solutions of some standard instances for TSPTW and even to prove the optimality of quite a few other instances.

JAIR Journal 2021 Journal Article

Generic Constraint-based Block Modeling using Constraint Programming

• Alex Mattenet
• Ian Davidson
• Siegfried Nijssen
• Pierre Schaus

Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings, for an exhaustive search and for a type of local search called Large Neighborhood Search. We show its use in the analysis of real datasets. Finally, we show an application of the CP framework for model selection using the Minimum Description Length principle.

AAAI Conference 2020 Conference Paper

Constraint Programming for an Efficient and Flexible Block Modeling Solver

• Alex Lucía Mattenet
• Ian Davidson
• Siegfried Nijssen
• Pierre Schaus

Constraint Programming (CP) is a powerful paradigm for solving combinatorial problems. In CP, the user creates a model by declaring variables with their domains and expresses the constraints that need to be satisfied in any solution. The solver is then in charge of finding feasible solutions—a value in the domain of each variable that satisfies all the constraints. The discovery of solutions is done by exploring a search tree that is pruned by the constraints in charge of removing impossible values. The CP framework has the advantage of exposing a rich high-level declarative constraint language for modeling, as well as efficient purpose-specific filtering algorithms that can be reused in many problems. In this work, we harness this flexibility and efficiency for the Block Modeling problem. It is a variant of the graph clustering problem that has been used extensively in many domains including social science, spatio-temporal data analysis and even medical imaging. We present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches. We show its use in the analysis of real datasets. This is an extended abstract of an earlier publication at CP2019 (Mattenet et al. 2019).

IJCAI Conference 2020 Conference Paper

Ddo, a Generic and Efficient Framework for MDD-Based Optimization

• Xavier Gillard
• Pierre Schaus
• Vianney Coppé

This paper presents ddo, a generic and efficient library to solve constraint optimization problems with decision diagrams. To that end, our framework implements the branch-and-bound approach which has recently been introduced by Bergman et al. , (2016) to solve dynamic programs to optimality. Our library allowed us to successfully reproduce the results of Bergman et al. for MISP, MCP and MAX2SAT while using a single generic library. As an additional benefit, our ddo library is able to exploit parallel computing for its purpose without imposing any constraint on the user (apart from memory safety). Ddo is released as an open source rust library (crate) alongside with its companion example programs to solve the aforementioned problems. To the best of our knowledge, this is the first public implementation of a generic library to solve combinatorial optimization problems with branch-and-bound MDD.

AAAI Conference 2020 Conference Paper

Learning Optimal Decision Trees Using Caching Branch-and-Bound Search

• Gaël Aglin
• Siegfried Nijssen
• Pierre Schaus

Several recent publications have studied the use of Mixed Integer Programming (MIP) for finding an optimal decision tree, that is, the best decision tree under formal requirements on accuracy, fairness or interpretability of the predictive model. These publications used MIP to deal with the hard computational challenge of finding such trees. In this paper, we introduce a new efficient algorithm, DL8. 5, for finding optimal decision trees, based on the use of itemset mining techniques. We show that this new approach outperforms earlier approaches with several orders of magnitude, for both numerical and discrete data, and is generic as well. The key idea underlying this new approach is the use of a cache of itemsets in combination with branch-and-bound search; this new type of cache also stores results for parts of the search space that have been traversed partially.

IJCAI Conference 2020 Conference Paper

Learning Optimal Decision Trees using Constraint Programming (Extended Abstract)

• Hélène Verhaeghe
• Siegfried Nijssen
• Gilles Pesant
• Claude-Guy Quimper
• Pierre Schaus

Decision trees are among the most popular classification models in machine learning. Traditionally, they are learned using greedy algorithms. However, such algorithms have their disadvantages: it is difficult to limit the size of the decision trees while maintaining a good classification accuracy, and it is hard to impose additional constraints on the models that are learned. For these reasons, there has been a recent interest in exact and flexible algorithms for learning decision trees. In this paper, we introduce a new approach to learn decision trees using constraint programming. Compared to earlier approaches, we show that our approach obtains better performance, while still being sufficiently flexible to allow for the inclusion of constraints. Our approach builds on three key building blocks: (1) the use of AND/OR search, (2) the use of caching, (3) the use of the CoverSize global constraint proposed recently for the problem of itemset mining. This allows our constraint programming approach to deal in a much more efficient way with the decompositions in the learning problem.

IJCAI Conference 2020 Conference Paper

PyDL8. 5: a Library for Learning Optimal Decision Trees

• Gaël Aglin
• Siegfried Nijssen
• Pierre Schaus

Decision Trees (DTs) are widely used Machine Learning (ML) models with a broad range of applications. The interest in these models has increased even further in the context of Explainable AI (XAI), as decision trees of limited depth are very interpretable models. However, traditional algorithms for learning DTs are heuristic in nature; they may produce trees that are of suboptimal quality under depth constraints. We introduce PyDL8. 5, a Python library to infer depth-constrained Optimal Decision Trees (ODTs). PyDL8. 5 provides an interface for DL8. 5, an efficient algorithm for inferring depth-constrained ODTs. The library provides an easy-to-use scikit-learn compatible interface. It cannot only be used for classification tasks, but also for regression, clustering, and other tasks. We introduce an interface that allows users to easily implement these other learning tasks. We provide a number of examples of how to use this library.

IJCAI Conference 2018 Conference Paper

Compact-MDD: Efficiently Filtering (s)MDD Constraints with Reversible Sparse Bit-sets

• Hélène Verhaeghe
• Christophe Lecoutre
• Pierre Schaus

Multi-Valued Decision Diagrams (MDDs) are instrumental in modeling combinatorial problems with Constraint Programming. In this paper, we propose a related data structure called sMDD (semi-MDD) where the central layer of the diagrams is non-deterministic. We show that it is easy and efficient to transform any table (set of tuples) into an sMDD. We also introduce a new filtering algorithm, called Compact-MDD, which is based on bitwise operations, and can be applied to both MDDs and sMDDs. Our experimental results show the practical interest of our approach, both in terms of compression and filtering speed.

AAAI Conference 2017 Conference Paper

Extending Compact-Table to Negative and Short Tables

• HŽlne Verhaeghe
• Christophe Lecoutre
• Pierre Schaus

Table constraints are very useful for modeling combinatorial constrained problems, and thus play an important role in Constraint Programming (CP). During the last decade, many algorithms have been proposed for enforcing the property known as Generalized Arc Consistency (GAC) on such constraints. A state-of-the art GAC algorithm called Compact- Table (CT), which has been recently proposed, significantly outperforms all previously proposed algorithms. In this paper, we extend this algorithm in order to deal with both short supports and negative tables, i. e. , tables that contain universal values and conflicts. Our experimental results show the interest of using this fast general algorithm.

AAAI Conference 2014 Conference Paper

A Support-Based Algorithm for the Bi-Objective Pareto Constraint

• Renaud Hartert
• Pierre Schaus

AAAI Conference 2008 Conference Paper

A Global Constraint for Bin-Packing with Precedences: Application to the Assembly Line Balancing Problem

• Pierre Schaus

Assembly line balancing problems (ALBP) are of capital importance for the industry since the first assembly line for the Ford T by Henry Ford. Their objective is to optimize the design of production lines while satisfying the various constraints. Precedence constraints among the tasks are always present in ALBP. The objective is then to place the tasks among various workstations such that the production rate is maximized. This problem can be modeled as a bin packing problem with precedence constraints (BPPC) where the bins are the workstations and the items are the tasks. Paul Shaw introduced a global constraint for bin-packing (without precedence). Unfortunately this constraint does not capture the precedence constraints of BPPC. In this paper, we first introduce redundant constraints for BPPC combining the precedences and the bin-packing, allowing to solve instances which are otherwise intractable in constraint programming. We also design a global constraint for BPPC, introducing even more pruning in the search tree. We finally used our CP model for BPPC to solve ALBP. We propose two search heuristics, and show the efficiency of our approach on standard ALBP benchmarks. Compared to standard non CP approaches, our method is more flexible as it can handle new constraints that might appear in real applications.