Author name cluster

Guillaume Perez

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.

5 papers

1 author row

AAAI Conference 2023 Conference Paper

Generalized Confidence Constraints

Guillaume Perez
Steve Malalel
Gael Glorian
Victor Jung
Alexandre Papadopoulos
Marie Pelleau
Wijnand Suijlen
Jean-Charles Régin

In robust optimization, finding a solution that solely respects the constraints is not enough. Usually, the uncertainty and unknown parameters of the model are represented by random variables. In such conditions, a good solution is a solution robust to most-likely assignments of these random variables. Recently, the Confidence constraint has been introduced by Mercier-Aubin et al. in order to enforce this type of robustness in constraint programming. Unfortunately, it is restricted to a conjunction of binary inequalities In this paper, we generalize the Confidence constraint to any constraint and propose an implementation based on Multi-valued Decision Diagrams (MDDs). The Confidence constraint is defined over a vector of random variables. For a given constraint C, and given a threshold, the Confidence constraint ensures that the probability for C to be satisfied by a sample of the random variables is greater than the threshold. We propose to use MDDs to represent the constraints on the random variables. MDDs are an efficient tool for representing combinatorial constraints, thanks to their exponential compression power. Here, both random and decision variables are stored in the MDD, and propagation rules are proposed for removing values of decision variables that cannot lead to robust solutions. Furthermore, for several constraints, we show that decision variables can be omitted from the MDD because lighter filtering algorithms are sufficient. This leads to gain an exponential factor in the MDD size. The experimental results obtained on a chemical deliveries problem in factories – where the chemicals consumption are uncertain – shows the efficiency of the proposed approach.

PDF Details DOI

AIJ Journal 2022 Journal Article

Efficient projection algorithms onto the weighted ℓ1 ball

Guillaume Perez
Sebastian Ament
Carla Gomes
Michel Barlaud

Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted ℓ 1 ball has been shown effective in sparse system identification and features selection. In this paper we propose three new efficient algorithms for projecting any vector of finite length onto the weighted ℓ 1 ball. The first two algorithms have a linear worst case complexity. The third one has a highly competitive performances in practice but the worst case has a quadratic complexity. These new algorithms are efficient tools for machine learning methods based on projected gradient descent such as compressed sensing, feature selection. We illustrate this effectiveness by adapting an efficient compressed sensing algorithm to weighted projections. We demonstrate the efficiency of our new algorithms on benchmarks using very large vectors. For instance, it requires only 8 ms, on an Intel I7 3rd generation, for projecting vectors of size 107.

Details DOI

AAAI Conference 2018 Conference Paper

Parallel Algorithms for Operations on Multi-Valued Decision Diagrams

Guillaume Perez
Jean-Charles Régin

Multi-valued Decision Diagrams (MDDs) have been extensively studied in the last ten years. Recently, efﬁcient algorithms implementing operators such as reduction, union, intersection, difference, etc. , have been designed. They directly deal with the graph structure of the MDD and a time reduction of several orders of magnitude in comparison to other existing algorithms have been observed. These operators have permitted a new look at MDDs, because extremely large MDDs can ﬁnally be manipulated as shown by the models used to solve complex application in music generation. However, MDDs become so large (50GB) that minutes are sometimes required to perform some operations. In order to accelerate the manipulation of MDDs, parallel algorithms are required. In this paper, we introduce such algorithms. We carefully design them in order to overcome inherent difﬁculties of the parallelization of sequential algorithms such as data dependencies, software lock-out, false sharing, or load balancing. As a result, we observe a speed-up, i. e. ratio between parallel and sequential runtimes, growing linearly with the number of cores.

PDF Details

AAAI Conference 2017 Conference Paper

Soft and Cost MDD Propagators

Guillaume Perez
Jean-Charles Rgin

Recent developments of efﬁcient propagators, operations and creation methods for MDDs allow us to directly build efﬁcient MDD-based models, without the need for intermediate data structures. In this paper, we take another step in this direction by improving the propagators of cost MDDs. In addition, we introduce a soft MDD propagator in order to deal with unsatisﬁable problems. This directly offers cost and soft versions for table constraints and any constraints which can be represented by an MDD (regular, slide, knapsack. ..).

PDF Details

IJCAI Conference 2015 Conference Paper

Efficient Operations On MDDs for Building Constraint Programming Models

Guillaume Perez
Jean-Charles R
eacute; gin

We propose improved algorithms for defining the most common operations on Multi-Valued Decision Diagrams (MDDs): creation, reduction, complement, intersection, union, difference, symmetric difference, complement of union and complement of intersection. Then, we show that with these algorithms and thanks to the recent development of an efficient algorithm establishing arc consistency for MDD based constraints (MDD4R), we can simply solve some problems by modeling them as a set of operations between MDDs. We apply our approach to the regular constraint and obtain competitive results with dedicated algorithms. We also experiment our technique on a large scale problem: the phrase generation problem and we show that our approach gives equivalent results to those of a specific algorithm computing a complex automaton.

PDF Details