David Lesaint

IJCAI Conference 2023 Conference Paper

New Bounds and Constraint Programming Models for the Weighted Vertex Coloring Problem

• Olivier Goudet
• Cyril Grelier
• David Lesaint

This paper addresses the weighted vertex coloring problem (WVCP) which is an NP-hard variant of the graph coloring problem with various applications. Given a vertex-weighted graph, the problem consists of partitioning vertices in independent sets (colors) so as to minimize the sum of the maximum weights of the colors. We first present an iterative procedure to reduce the size of WVCP instances and prove new upper bounds on the objective value and the number of colors. Alternative constraint programming models are then introduced which rely on primal and dual encodings of the problem and use symmetry breaking constraints. A large number of experiments are conducted on benchmark instances. We analyze the impact of using specific bounds to reduce the search space and speed up the exact resolution of instances. New optimality proofs are reported for some benchmark instances.

ECAI Conference 2014 Conference Paper

A Decomposition Approach for Discovering Discriminative Motifs in a Sequence Database

• David Lesaint
• Deepak Mehta 0001
• Barry O'Sullivan
• Vincent Vigneron

This paper addresses the discovery of discriminative nary motifs in databases of labeled sequences. We consider databases made up of positive and negative sequences and define a motif as a set of patterns embedded in all positive sequences and subject to alignment constraints. We formulate constraints to eliminate redundant motifs and present a general constraint optimization framework to compute motifs that are exclusive to the positive sequences. We cast the discovery of closed and replication-free motifs in this framework and propose a two-stage approach whose last stage reduces to a minimum set covering problem. Experiments on protein sequence datasets demonstrate its efficiency.

ECAI Conference 2010 Conference Paper

Improving the Global Constraint SoftPrec

• David Lesaint
• Deepak Mehta 0001
• Barry O'Sullivan
• Luis Quesada 0001
• Nic Wilson

A soft global constraint SOFTPREC has been proposed recently for solving optimisation problems involving precedence relations. In this paper we present new pruning rules for this global constraint. We introduce a pruning rule that improves propagation from the objective variable to the decision variables, which is believed to be harder to achieve. We further introduce a pruning rule based on linear programming, and thereby make SOFTPREC a hybrid of constraint programming and linear programming. We present results demonstrating the efficiency of the pruning rules.

IJCAI Conference 2009 Conference Paper

• David Lesaint
• Deepak Mehta
• Barry O’Sullivan
• Luis Quesada
• Nic Wilson

Hard and soft precedence constraints play a key role in many application domains. In telecommunications, one application is the configuration of callcontrol feature subscriptions where the task is to sequence a set of user-selected features subject to a set of hard (catalogue) precedence constraints and a set of soft (user-selected) precedence constraints. When no such consistent sequence exists, the task is to find an optimal relaxation by discarding some features or user precedences. For this purpose, we present the global constraint SOFTPREC. Enforcing Generalized Arc Consistency (GAC) on SOFT- PREC is NP-complete. Therefore, we approximate GAC based on domain pruning rules that follow from the semantics of SOFTPREC; this pruning is polynomial. Empirical results demonstrate that the search effort required by SOFTPREC is up to one order of magnitude less than the previously known best CP approach for the feature subscription problem. SOFTPREC is also applicable to other problem domains including minimum cutset problems for which initial experiments confirm the interest.

ECAI Conference 2008 Conference Paper

A BDD Approach to the Feature Subscription Problem

• Tarik Hadzic
• David Lesaint
• Deepak Mehta 0001
• Barry O'Sullivan
• Luis Quesada 0001
• Nic Wilson

Modern feature-rich telecommunications services offer significant opportunities to human users. To make these services more usable, facilitating personalisation is very important since it enhances the users' experience considerably. However, regardless how service providers organise their catalogues of features, they cannot achieve complete configurability due to the existence of feature interactions. Distributed Feature Composition (DFC) provides a comprehensive methodology, underpinned by a formal architecture model to address this issue. In this paper we present an approach based on using Binary Decision Diagrams (BDD) to find optimal reconfigurations of features when a user's preferences violate the technical constraints defined by a set of DFC rules. In particular, we propose hybridizing constraint programming and standard BDD compilation techniques in order to scale the construction of a BDD for larger size catalogues. Our approach outperforms the standard BDD techniques by reducing the memory requirements by as much as five orders-of-magnitude and compiles the catalogues for which the standard techniques ran out of memory.

ECAI Conference 1994 Conference Paper

Maximal Sets of Solutions for Constraint Satisfaction Problems

• David Lesaint