Arrow Research search

Author name cluster

Emmanuel Hebrard

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

27 papers
2 author rows

Possible papers

27

TMLR Journal 2025 Journal Article

Boosting Revisited: Benchmarking and Advancing LP-Based Ensemble Methods

  • Fabian Akkerman
  • Julien Ferry
  • Christian Artigues
  • Emmanuel Hebrard
  • Thibaut Vidal

Despite their theoretical appeal, totally corrective boosting methods based on linear programming have received limited empirical attention. In this paper, we conduct the first large-scale experimental study of six LP-based boosting formulations, including two novel methods, NM-Boost and QRLP-Boost, across 20 diverse datasets. We evaluate the use of both heuristic and optimal base learners within these formulations, and analyze not only accuracy, but also ensemble sparsity, margin distribution, anytime performance, and hyperparameter sensitivity. We show that totally corrective methods can outperform or match state-of-the-art heuristics like XGBoost and LightGBM when using shallow trees, while producing significantly sparser ensembles. We further show that these methods can thin pre-trained ensembles without sacrificing performance, and we highlight both the strengths and limitations of using optimal decision trees in this context.

PDF Details

ICML Conference 2023 Conference Paper

Blossom: an Anytime Algorithm for Computing Optimal Decision Trees

  • Emir Demirovic
  • Emmanuel Hebrard
  • Louis Jean

We propose a simple algorithm to learn optimal decision trees of bounded depth. This algorithm is essentially an anytime version of the state-of-the-art dynamic programming approach. It has virtually no overhead compared to heuristic methods and is comparable to the best exact methods to prove optimality on most data sets. Experiments show that whereas existing exact methods hardly scale to deep trees, this algorithm learns trees comparable to standard heuristics without computational overhead, and can significantly improve their accuracy when given more computation time, even for deep trees.

Details

IJCAI Conference 2022 Conference Paper

An Efficient Approach to Data Transfer Scheduling for Long Range Space Exploration

  • Emmanuel Hebrard
  • Christian Artigues
  • Pierre Lopez
  • Arnaud Lusson
  • Steve Chien
  • Adrien Maillard
  • Gregg Rabideau

Long range space missions, such as Rosetta, require robust plans of data-acquisition activities and of the resulting data transfers. In this paper we revisit the problem of assigning priorities to data transfers in order to maximize safety margin of onboard memory. We propose a fast sweep algorithm to verify the feasibility of a given priority assignment and we introduce an efficient exact algorithm to assign priorities on a single downlink window. We prove that the problem is NP-hard for several windows, and we propose several randomized heuristics to tackle the general case. Our experimental results show that the proposed approaches are able to improve the plans computed for the real mission by the previously existing method, while the sweep algorithm yields drastic accelerations.

PDF Details DOI

JMLR Journal 2022 Journal Article

MurTree: Optimal Decision Trees via Dynamic Programming and Search

  • Emir Demirović
  • Anna Lukina
  • Emmanuel Hebrard
  • Jeffrey Chan
  • James Bailey
  • Christopher Leckie
  • Kotagiri Ramamohanarao
  • Peter J. Stuckey

Decision tree learning is a widely used approach in machine learning, favoured in applications that require concise and interpretable models. Heuristic methods are traditionally used to quickly produce models with reasonably high accuracy. A commonly criticised point, however, is that the resulting trees may not necessarily be the best representation of the data in terms of accuracy and size. In recent years, this motivated the development of optimal classification tree algorithms that globally optimise the decision tree in contrast to heuristic methods that perform a sequence of locally optimal decisions. We follow this line of work and provide a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our algorithm supports constraints on the depth of the tree and number of nodes. The success of our approach is attributed to a series of specialised techniques that exploit properties unique to classification trees. Whereas algorithms for optimal classification trees have traditionally been plagued by high runtimes and limited scalability, we show in a detailed experimental study that our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances, providing several orders of magnitude improvements and notably contributing towards the practical use of optimal decision trees. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2022. ( edit, beta )

PDF Details

JAIR Journal 2020 Journal Article

Constraint and Satisfiability Reasoning for Graph Coloring

  • Emmanuel Hebrard
  • George Katsirelos

Graph coloring is an important problem in combinatorial optimization and a major component of numerous allocation and scheduling problems. In this paper we introduce a hybrid CP/SAT approach to graph coloring based on the addition-contraction recurrence of Zykov. Decisions correspond to either adding an edge between two non-adjacent vertices or contracting these two vertices, hence enforcing inequality or equality, respectively. This scheme yields a symmetry-free tree and makes learnt clauses stronger by not committing to a particular color. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; a branching heuristic emulating Brélaz’ heuristic on the Zykov tree; and dedicated pruning techniques relying on marginal costs with respect to the bound and on reasoning about transitivity when unit propagating learnt clauses. The combination of these techniques in both a branch-and-bound and in a bottom-up search outperforms other SAT-based approaches and Dsatur on standard benchmarks both for finding upper bounds and for proving lower bounds.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost

  • Hao Hu
  • Mohamed Siala
  • Emmanuel Hebrard
  • Marie-José Huguet

Recently, several exact methods to compute decision trees have been introduced. On the one hand, these approaches can find optimal trees for various objective functions including total size, depth or accuracy on the training set and therefore. On the other hand, these methods are not yet widely used in practice and classic heuristics are often still the methods of choice. In this paper we show how the SAT model proposed by [Narodytska et. al 2018] can be lifted to a MaxSAT approach, making it much more practically relevant. In particular, it scales to much larger data sets; the objective function can easily be adapted to take into account combinations of size, depth and accuracy on the training set; and the fine-grained control of the objective function it offers makes it particularly well suited for boosting. Our experiments show promising results. In particular, we show that the prediction quality of our approach often exceeds state of the art heuristics. We also show that the MaxSAT formulation is well adapted for boosting using the well-known AdaBoost Algorithm.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Using Approximation within Constraint Programming to Solve the Parallel Machine Scheduling Problem with Additional Unit Resources

  • Arthur Godet
  • Xavier Lorca
  • Emmanuel Hebrard
  • Gilles Simonin

In this paper, we consider the Parallel Machine Scheduling Problem with Additional Unit Resources, which consists in scheduling a set of n jobs on m parallel unrelated machines and subject to exactly one of r unit resources. This problem arises from the download of acquisitions from satellites to ground stations. We first introduce two baseline constraint models for this problem. Then, we build on an approximation algorithm for this problem, and we discuss about the efficiency of designing an improved constraint model based on these approximation results. In particular, we introduce new constraints that restrict search to executions of the approximation algorithm. Finally, we report experimental data demonstrating that this model significantly outperforms the two reference models.

PDF Details

IJCAI Conference 2019 Conference Paper

Clause Learning and New Bounds for Graph Coloring

  • Emmanuel Hebrard
  • George Katsirelos

Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov’s tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in a branch- and-bound search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.

PDF Details

IJCAI Conference 2018 Conference Paper

Conflict Directed Clause Learning for Maximum Weighted Clique Problem

  • Emmanuel Hebrard
  • George Katsirelos

The maximum clique and minimum vertex cover problems are among Karp's 21 NP-complete problems, and have numerous applications: in combinatorial auctions, for computing phylogenetic trees, to predict the structure of proteins, to analyse social networks, and so forth. Currently, the best complete methods are branch & bound algorithms and rely largely on graph colouring to compute a bound. We introduce a new approach based on SAT and on the "Conflict-Driven Clause Learning" (CDCL) algorithm. We propose an efficient implementation of Babel's bound and pruning rule, as well as a novel dominance rule. Moreover, we show how to compute concise explanations for this inference. Our experimental results show that this approach is competitive and often outperforms the state of the art for finding cliques of maximum weight.

PDF Details

IJCAI Conference 2018 Conference Paper

Reasoning about NP-complete Constraints

  • Emmanuel Hebrard

The concept of local consistency – making global deductions from local infeasibility – is central to constraint programming. When reasoning about NP-complete constraints, however, since achieving a ``complete'' form of local consistency is often considered too hard, we need other tools to design and analyze propagation algorithms. In this paper, we argue that NP-complete constraints are an essential part of constraint programming, that designing dedicated methods has lead to, and will bring, significant breakthroughs, and that we need to carefully investigate methods to deal about a necessarily incomplete inference. In particular, we advocate the use of fixed-parameter tractability and kernelization to this purpose.

PDF Details

IJCAI Conference 2017 Conference Paper

On the Kernelization of Global Constraints

  • Clément Carbonnel
  • Emmanuel Hebrard

Kernelization is a powerful concept from parameterized complexity theory that captures (a certain idea of) efficient polynomial-time preprocessing for hard decision problems. However, exploiting this technique in the context of constraint programming is challenging. Building on recent results for the VertexCover constraint, we introduce novel "loss-less" kernelization variants that are tailored for constraint propagation. We showcase the theoretical interest of our ideas on two constraints, VertexCover and EdgeDominatingSet.

PDF Details

IJCAI Conference 2016 Conference Paper

Ranking Constraints

  • Christian Bessiere
  • Emmanuel Hebrard
  • George Katsirelos
  • Zeynep Kiziltan
  • Toby Walsh

We need to reason about rankings of objects in a wide variety of domains including information retrieval, sports tournaments, bibliometrics, and statistics. We propose a global constraint therefore for modeling rankings. One important application for rankings is in reasoning about the correlation or uncorrelation between two sequences. For example, we might wish to have consecutive delivery schedules correlated to make it easier for clients and employees, or uncorrelated to avoid predictability and complacence. We therefore also consider global correlation constraints between rankings. For both ranking and correlation constraints, we propose efficient filtering algorithms and decompositions, and report experimental results demonstrating the promise of our proposed approach.

PDF Details

IJCAI Conference 2015 Conference Paper

Reasoning about Connectivity Constraints

  • Christian Bessiere
  • Emmanuel Hebrard
  • George Katsirelos
  • Toby Walsh

Many problems in computational sustainability involve constraints on connectivity. When designing a new wildlife corridor, we need it to be geographically connected. When planning the harvest of a forest, we need new areas to harvest to be connected to areas that have already been harvested so we can access them easily. And when town planning, we need to connect new homes to the existing utility infrastructure. To reason about connectivity, we propose a new family of global connectivity constraints. We identify when these constraints can be propagated tractably, and give some efficient, typically linear time propagators for when this is the case. We report results on several benchmark problems which demonstrate the efficiency of our propagation algorithms and the promise offered by reasoning globally about connectivity.

PDF Details

ICAPS Conference 2014 Conference Paper

Satellite Data Download Management with Uncertainty about the Generated Volumes

  • Cédric Pralet
  • Gérard Verfaillie
  • Adrien Maillard
  • Emmanuel Hebrard
  • Nicolas Jozefowiez
  • Marie-José Huguet
  • Thierry Desmousceaux
  • Pierre Blanc-Paques

Earth observation satellites are space sensors which acquire data, compress and record it on board, and then download it to the ground. Because of the use of more and more sophisticated compression algorithms, the amount of data resulting from an acquisition is more and more unpredictable. In such conditions, planning satellite data download activities offline on the ground is more and more problematic. In this paper, we report the results of a work aiming at evaluating the positive impact of planning downloads onboard when the amount of data produced by each acquisition is known. The data download problem to be solved on board is an assignment and scheduling problem with unsharable resources, precedence constraints, time-dependent minimum durations, and a complex optimization criterion. The generic InCELL library is used to model constraints and criterion, to check non temporal constraints, to propagate temporal constraints, and to evaluate the criterion. On top of this library, greedy and local search algorithms have been designed to produce download plans with limited time and computing resources available on board.

Details

IJCAI Conference 2013 Conference Paper

Constraint Acquisition via Partial Queries

  • Christian Bessiere
  • Remi Coletta
  • Emmanuel Hebrard
  • George Katsirelos
  • Nadjib Lazaar
  • Nina Narodytska
  • Claude-Guy Quimper
  • Toby Walsh

We learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. Finally we evaluate our algorithm on some benchmarks.

PDF Details DOI

IJCAI Conference 2013 Conference Paper

Detecting and Exploiting Subproblem Tractability

  • Christian Bessiere
  • Clement Carbonnel
  • Emmanuel Hebrard
  • George Katsirelos
  • Toby Walsh

Constraint satisfaction problems may be nearly tractable. For instance, most of the relations in a problem might belong to a tractable language. We introduce a method to take advantage of this fact by computing a backdoor to this tractable language. The method can be applied to many tractable classes for which the membership test is itself tractable. We introduce therefore two polynomial membership testing algorithms, to check if a language is closed under a majority or conservative Mal’tsev polymorphism, respectively. Then we show that computing a minimal backdoor for such classes is fixed parameter tractable (FPT) if the tractable subset of relations is given, and W[2]complete otherwise. Finally, we report experimental results on the XCSP benchmark set. We identified a few promising problem classes where problems were nearly closed under a majority polymorphism and small backdoors could be computed.

PDF Details DOI

ECAI Conference 2008 Conference Paper

SLIDE: A Useful Special Case of the CARDPATH Constraint

  • Christian Bessière
  • Emmanuel Hebrard
  • Brahim Hnich
  • Zeynep Kiziltan
  • Toby Walsh

We study the CARDPATH constraint. This ensures a given constraint holds a number of times down a sequence of variables. We show that SLIDE, a special case of CARDPATH where the slid constraint must hold always, can be used to encode a wide range of sliding sequence constraints including CARDPATH itself. We consider how to propagate SLIDE and provide a complete propagator for CARDPATH. Since propagation is NP-hard in general, we identify special cases where propagation takes polynomial time. Our experiments demonstrate that using SLIDE to encode global constraints can be as efficient and effective as specialised propagators.

Details

IJCAI Conference 2007 Conference Paper

  • Emmanuel Hebrard
  • Barry O'Sullivan
  • Toby Walsh

Users can often naturally express their preferences in terms of ideal or non-ideal solutions. We show how to reason about logical combinations of distance constraints on ideals and non-ideals using a novel global constraint. We evaluate our approach on both randomly generated and real-world configuration problem instances.

PDF Details

AAAI Conference 2005 Conference Paper

Finding Diverse and Similar Solutions in Constraint Programming

  • Emmanuel Hebrard
  • Barry O'Sullivan

It is useful in a wide range of situations to find solutions which are diverse (or similar) to each other. We therefore define a number of different classes of diversity and similarity problems. For example, what is the most diverse set of solutions of a constraint satisfaction problem with a given cardinality? We first determine the computational complexity of these problems. We then propose a number of practical solution methods, some of which use global constraints for enforcing diversity (or similarity) between solutions. Empirical evaluation on a number of problems show promising results.

PDF Details

IJCAI Conference 2005 Conference Paper

The Range and Roots Constraints: Specifying Counting and Occurrence Problems

  • Christian Bessiere
  • Emmanuel Hebrard
  • Brahim Hnich
  • Zeynep Kiziltan
  • Toby

We propose a simple declarative language for specifying a wide range of counting and occurrence constraints. This specification language is executable since it immediately provides a polynomial propagation algorithm. To illustrate the capabilities of this language, we specify a dozen global constraints taken from the literature. We observe one of three outcomes: we achieve generalized arc-consistency; we do not achieve generalized arc-consistency, but achieving generalized arcconsistency is NP-hard; we do not achieve generalized arc-consistency, but specialized propagation algorithms can do so in polynomial time. Experiments demonstrate that this specification language is both efficient and effective in practice.

PDF

AAAI Conference 2004 Short Paper

Robust Solutions for Constraint Satisfaction and Optimization

  • Emmanuel Hebrard

Super solutions are solutions in which, if a small number of variables lose their values, we are guaranteed to be able to repair the solution with only a few changes. In this paper, we stress the need to extend the super solution framework along several dimensions to make it more useful practically. We demonstrate the usefulness of those extensions on an example from jobshop scheduling, an optimization problem solved through constraint satisfaction. In such a case there is indeed a trade-off between optimality and robustness, however robustness may be increased without sacrificing optimality.

PDF Details

SAT Conference 2003 Conference Paper

Local Consistencies in SAT

  • Christian Bessière
  • Emmanuel Hebrard
  • Toby Walsh

Abstract We introduce some new mappings of constraint satisfaction problems into propositional satisfiability. These encodings generalize most of the existing encodings. Unit propagation on those encodings is the same as establishing relational k -arc consistency on the original problem. They can also be used to establish (i, j)-consistency on binary constraints. Experiments show that these encodings are an effective method for enforcing such consistencies, that can lead to a reduction in runtimes at the phase transition in most cases. Compared to the more traditional (direct) encoding, the search tree can be greatly pruned.

Details