@conference {aoga2017jfpc,
title = {Algorithme Efficace pour la Fouille de S{\'e}quences Fr{\'e}quentes avec la Programmation par Contraintes},
booktitle = {Treizi{\`e}mes journ{\'e}es Francophones de Programmation par Contraintes - JFPC{\textquoteright}17},
year = {2017},
abstract = {La programmation par contraintes (CP) a s{\'e}duit la communaut{\'e} de fouille de donn{\'e}es gr{\^a}ce {\`a} son approche hautement d{\'e}clarative et sa flexibilit{\'e}. Cependant, ces avantages n{\textquoteright}offrent pas une garantie d{\textquoteright}efficacit{\'e}. En t{\'e}moigne la litt{\'e}rature o{\`u} les m{\'e}thodes bas{\'e}es sur la CP n{\textquoteright}ont toujours pas r{\'e}ussi {\`a} {\^e}tre aussi performante que les m{\'e}thodes sp{\'e}cialis{\'e}es. Dans ce papier publi{\'e} au ECML-PKDD{\textquoteright}16 aoga2016pkdd, nous montrons comment en combinant les techniques des deux mondes on peut arriver {\`a} une m{\'e}thode tr{\`e}s robuste et efficace en plus d{\textquoteright}{\^e}tre modulaire et flexible pour r{\'e}soudre les probl{\`e}mes de fouille de s{\'e}quences fr{\'e}quentes. Notre approche, intitul{\'e}e PPIC, est une contrainte globale, con{\c c}ue sur les m{\'e}thodes de projection de base de donn{\'e}es. Cette contrainte utilise une structure de donn{\'e}es auto-backtraquante (trailing) pour stocker et restaurer efficacement les bases de donn{\'e}es projet{\'e}es. Le calcul des supports et le filtrage reposent sur des am{\'e}liorations algorithmiques utilisant des donn{\'e}es pr{\'e}-calcul{\'e}es. Des exp{\'e}riences d{\'e}taill{\'e}es montrent comment cette approche, pour la premi{\`e}re fois, surpasse {\`a} la fois les m{\'e}thodes bas{\'e}es sur la CP et celles sp{\'e}cialis{\'e}es. Ainsi, le moindre qu{\textquoteright}on puisse dire est que le tandem fouille de donn{\'e}es et CP a encore de beaux jours devant lui.},
author = {Aoga, John O. R. and Guns, Tias and Pierre Schaus}
}
@conference {DBLP:conf/cp/SchausAG17,
title = {CoverSize: {A} Global Constraint for Frequency-Based Itemset Mining},
booktitle = {Principles and Practice of Constraint Programming: 23rd International Conference, {CP 2017}},
volume = {10416},
year = {2017},
pages = {529{\textendash}546},
publisher = {Springer International Publishing},
organization = {Springer International Publishing},
address = {Melbourne, VIC, Australia},
abstract = {Constraint Programming is becoming competitive for solving certain data-mining problems largely due to the development of global constraints. We introduce the CoverSize constraint for itemset mining problems, a global constraint for counting and constraining the number of transactions covered by the itemset decision variables. We show the relation of this constraint to the well-known table constraint, and our filtering algorithm internally uses the reversible sparse bitset data structure recently proposed for filtering table. Furthermore, we expose the size of the cover as a variable, which opens up new modelling perspectives compared to an existing global constraint for (closed) frequent itemset mining. For example, one can constrain minimum frequency or compare the frequency of an itemset in different datasets as is done in discriminative itemset mining. We demonstrate experimentally on the frequent, closed and discriminative itemset mining problems that the CoverSize constraint with reversible sparse bitsets allows to outperform other CP approaches.},
isbn = {978-3-319-66158-2},
doi = {10.1007/978-3-319-66158-2_34},
url = {https://doi.org/10.1007/978-3-319-66158-2_34},
author = {Pierre Schaus and Aoga, John O. R. and Guns, Tias}
}
@article {aoga2017constraint,
title = {Mining Time-constrained Sequential Patterns with Constraint Programming},
journal = {Constraints},
volume = {22},
year = {2017},
abstract = {Constraint Programming (CP) has proven to be an effective platform for constraint-based sequence mining. Previous work has focused on standard frequent sequence mining, as well as frequent sequence mining with a maximum {\textquoteright}gap{\textquoteright} between two matching events in a sequence. The main challenge in the latter is that this constraint can not be imposed independently of the omnipresent frequency constraint. Indeed, the gap constraint changes whether a subsequence is included in a sequence, and hence its frequency. In this work, we go beyond that and investigate the integration of timed events and constraining the minimum/maximum gap as well as minimum/maximum span. The latter constrains the allowed time between the first and last matching event of a pattern. We show how the three are interrelated, and what the required changes to the frequency constraint are. Key in our approach is the concept of an extension window defined by gap/span and we develop techniques to avoid scanning the sequences needlessly, as well as using a backtracking-aware data structure. Experiments demonstrate that the proposed approach outperforms both specialized and CP-based approaches in almost all cases and that the advantage increases as the minimum frequency threshold decreases. This paper is an extension of the original manuscript presented at CPAIOR{\textquoteright}17 aoga2017cpaior.},
keywords = {constraint programming, Data mining, Gap constraint, Global Constraint, Sequential pattern mining, Span constraint, Time constraint},
author = {Aoga, John O. R. and Guns, Tias and Pierre Schaus}
}
@conference {aoga2017cpaior,
title = {Mining Time-constrained Sequential Patterns with Constraint Programming},
booktitle = {International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR17)},
year = {2017},
abstract = {See Constraint Journal paper aoga2017constraint.},
author = {Aoga, John O. R. and Guns, Tias and Pierre Schaus}
}
@proceedings {166,
title = {Rescheduling Railway Traffic on Real Time Situations using Time-Interval Variables},
year = {2017},
author = {Quentin Cappart and Pierre Schaus}
}
@proceedings {168,
title = { Verification of interlocking systems using statistical model checking},
year = {2017},
author = {Quentin Cappart and Christophe Limbree and Pierre Schaus and Jean Quilbeuf and Louis-Marie Traonouez and Axel Legay}
}
@proceedings {167,
title = {A dedicated algorithm for verification of interlocking systems},
year = {2016},
author = {Quentin Cappart and Pierre Schaus}
}
@conference {aoga2016pkdd,
title = {An Efficient Algorithm for Mining Frequent Sequence with Constraint Programming},
booktitle = {Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part II},
year = {2016},
pages = {315{\textendash}330},
publisher = {Springer International Publishing},
organization = {Springer International Publishing},
address = {Cham},
abstract = {The main advantage of Constraint Programming (CP)
approaches for sequential pattern mining (SPM) is their modularity,
which includes the ability to add new constraints (regular expressions,
length restrictions, etc.). The current best CP approach for SPM uses
a global constraint (module) that computes the projected database and
enforces the minimum frequency; it does this with a filtering algorithm
similar to the PrefixSpan method. However, the resulting system is not
as scalable as some of the most advanced mining systems like Zaki{\textquoteright}s
cSPADE. We show how, using techniques from both data mining and
CP, one can use a generic constraint solver and yet outperform existing
specialized systems. This is mainly due to two improvements in the
module that computes the projected frequencies: first, computing the
projected database can be sped up by pre-computing the positions at
which a symbol can become unsupported by a sequence, thereby avoiding
to scan the full sequence each time; and second by taking inspiration
from the trailing used in CP solvers to devise a backtracking-aware
data structure that allows fast incremental storing and restoring of the
projected database. Detailed experiments show how this approach outperforms
existing CP as well as specialized systems for SPM, and that
the gain in efficiency translates directly into increased efficiency for other
settings such as mining with regular expressions. The data and software
related to this paper are available at http://sites.uclouvain.be/cp4dm/
spm/},
isbn = {978-3-319-46227-1},
doi = {10.1007/978-3-319-46227-1_20},
url = {http://dx.doi.org/10.1007/978-3-319-46227-1_20},
author = {Aoga, John O. R. and Guns, Tias and Pierre Schaus},
editor = {Frasconi, Paolo and Landwehr, Niels and Manco, Giuseppe and Vreeken, Jilles}
}
@conference {van2016efficient,
title = {Efficient Filtering for the Unary Resource with Family-Based Transition Times},
booktitle = {International Conference on Principles and Practice of Constraint Programming},
year = {2016},
pages = {520{\textendash}535},
publisher = {Springer},
organization = {Springer},
author = {Sascha Van Cauwelaert and Cyrille Dejemeppe and Jean-No{\"e}l Monette and Pierre Schaus}
}
@conference {aoga2016scalable,
title = {Scalable Constraint Programming approach for Mining Frequent Sequence with gap constraints},
booktitle = {BENELEARN, 2016},
year = {2016},
author = {Aoga, John and Pierre Schaus and Guns, Tias}
}
@conference {156,
title = {Derivative-Free Optimization: Lifting Single-Objective to Multi-Objective Algorithm},
booktitle = {CPAIOR2015},
year = {2015},
publisher = {Springer},
organization = {Springer},
address = {Barcelona, Spain},
abstract = {Most of the derivative-free optimization (DFO) algorithms rely on a comparison function able to compare any pair of points with respect to a black- box objective function. Recently, new dedicated derivative-free optimization al- gorithms have emerged to tackle multi-objective optimization problems and pro- vide a Pareto front approximation to the user. This work aims at reusing single ob- jective DFO algorithms (such as Nelder-Mead) in the context of multi-objective optimization. Therefore we introduce a comparison function able to compare a pair of points in the context of a set of non-dominated points. We describe an algorithm, MOGEN, which initializes a Pareto front approximation composed of a population of instances of single-objective DFO algorithms. These algorithms use the same introduced comparison function relying on a shared Pareto front approximation. The different instances of single-objective DFO algorithms are collaborating and competing to improve the Pareto front approximation. Our ex- periments comparing MOGEN with the state-of the-art Direct Multi-Search al- gorithm on a large set of benchmarks shows the practicality of the approach, allowing to obtain high quality Pareto fronts using a reasonably small amount of function evaluations.},
author = {Cyrille Dejemeppe and Pierre Schaus and Yves Deville}
}
@conference {148,
title = {Time-Table Disjunctive Reasoning for the Cumulative Constraint},
booktitle = {CPAIOR},
year = {2015},
month = {2015/5/18},
publisher = {Springer},
organization = {Springer},
address = {Barcelona, Spain},
abstract = {Scheduling has been a successful domain of application for constraint programming since its beginnings. The cumulative constraint {\textendash} which enforces the usage of a limited resource by several tasks {\textendash} is one of the core components that are surely responsible of this success. Unfortunately, ensuring bound-consistency for the cumulative constraint is already NP-Hard. Therefore, several relaxations were proposed to reduce domains in polynomial time such as Time-Tabling, Edge-Finding, Energetic Reasoning, and Not-First-Not-Last. Recently, Vilim introduced the Time-Table Edge-Finding reasoning which strengthens Edge-Finding by considering the time-table of the resource. We pursue the idea of exploiting the time-table to detect disjunctive pairs of tasks dynamically during the search. This new type of filtering {\textendash} which we call time-table disjunctive reasoning {\textendash} is not dominated by existing filtering rules. We propose a simple algorithm that implements this filtering rule with a O(n^2) time complexity (where n is the number of tasks) without relying on complex data structures. Our results on well known benchmarks highlight that using this new algorithm can substantially improve the solving process for some instances and only adds a marginally low computation overhead for the other ones.},
author = {Steven Gay and Renaud Hartert and Pierre Schaus}
}
@conference {dejemeppe2015unary,
title = {The unary resource with transition times},
booktitle = {International Conference on Principles and Practice of Constraint Programming},
year = {2015},
pages = {89{\textendash}104},
publisher = {Springer},
organization = {Springer},
author = {Cyrille Dejemeppe and Sascha Van Cauwelaert and Pierre Schaus}
}
@conference {149,
title = {Understanding the Potential of Propagators},
booktitle = {The Twelfth International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming},
year = {2015},
author = {Sascha Van Cauwelaert and Michele Lombardi and Pierre Schaus}
}
@proceedings {169,
title = {Verification by discrete simulation of interlocking systems},
year = {2015},
author = {Quentin Cappart and Christophe Limbr{\'e}e and Pierre Schaus and Axel Legay}
}
@proceedings {170,
title = {Verification of railway interlocking systems},
year = {2015},
author = {Simon Busard and Pierre Schaus and Quentin Cappart and Christophe Limbr{\'e}e and Charles Pecheur}
}
@conference {152,
title = {Continuous Casting Scheduling with Constraint Programming.},
booktitle = {CP2014: International Conference on Principles and Practice of Constraint Programming},
year = {2014},
publisher = {Springer},
organization = {Springer},
address = {Lyon, France},
abstract = {Although the Steel Mill Slab problem (prob 38 of CSPLib) has already been studied by the CP community, this approach is unfor- tunately not used anymore by steel producers since last century. Continuous casting is preferred instead, allowing higher throughput and better steel quality. This paper presents a CP model related to scheduling of op- erations for steel making with continuous casting. Activities considered range from the extraction of iron in the furnace to its casting in con- tinuous casters. We describe the problem, detail a CP scheduling model that is finally used to solve real-life instances of some of the PSI Metals{\textquoteright} customers.},
author = {Steven Gay},
editor = {Pierre Schaus}
}
@conference {136,
title = {Cost Impact Guided LNS},
booktitle = {CPAIOR: The Eleventh International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming},
year = {2014},
abstract = {InLargeNeighborhoodSearch(LNS)[14],aproblemissolved by repeatedly exploring (via tree search) a neighborhood of an incum- bent solution. Whenever an improving solution is found, this replaces the current incumbent. LNS can improve dramatically the scalability of CP on large real world problems, provided a good neighborhood selection heuristic is available. Unfortunately, designing a neighborhood heuristic for LNS is still largely an art and on many problems beating a random selection requires a considerable amount of both cleverness and domain knowledge. Recently, some authors have advocated the idea to include in the neighborhood the variables that are most directly affecting the cost of the current solution. The proposed approaches, however, are either domain dependent or require non-trivial solver modifications. In this pa- per, we rely on constraint propagation and basic solver support to design a set of simple, cost based, domain independent neighborhood selection heuristics. Those techniques are applied on Steel Mill Slab problems il- lustrating the superiority of some of them over pure random relaxations.},
author = {Michele Lombardi and Pierre Schaus}
}
@proceedings {150,
title = {The StockingCost Constraint},
volume = {8656},
year = {2014},
month = {09/2014},
pages = {382-397},
publisher = {Springer International Publishing},
abstract = {Many production planning problems call for the minimization of stocking/storage costs. This paper introduces a new global constraint StockingCost([X1,...,Xn],[d1,...,dn],H,c) that holds when each item Xi is produced on or before its due date di, the capacity c of the machine is respected, and H is an upper bound on the stocking cost. We propose a linear time algorithm to achieve bound consistency on the StockingCost constraint. On a version of the Discrete Lot Sizing Problem, we demonstrate experimentally the pruning and time efficiency of our algorithm compared to other state-of-the-art approaches.},
keywords = {constraint programming, Discrete Lot Sizing, Global Constraint, Production Planning},
author = {Vinas{\'e}tan Ratheil Houndji and Pierre Schaus and Laurence Wolsey and Yves Deville}
}
@conference {153,
title = {Supervised Learning to Control Energetic Reasoning : Feasibility Study},
booktitle = {CP 2014 Doctoral Program},
year = {2014},
author = {Sascha Van Cauwelaert and Michele Lombardi and Pierre Schaus}
}
@conference {151,
title = {A Support-Based Algorithm for the Bi-Objective Pareto Constraint},
booktitle = {AAAI 2014},
year = {2014},
publisher = { In Twenty-Eighth AAAI Conference on Artificial Intelligence},
organization = { In Twenty-Eighth AAAI Conference on Artificial Intelligence},
address = {Quebec},
abstract = {Bi-Objective Combinatorial Optimization problems are ubiquitous in real-world applications and designing approaches to solve them efficiently is an important research area of Artificial Intelligence. In Constraint Programming, the recently introduced bi-objective Pareto constraint allows one to solve bi-objective combinatorial optimization problems exactly. Using this constraint, every non-dominated solution is col- lected in a single tree-search while pruning sub-trees that cannot lead to a non-dominated solution. This paper introduces a simpler and more efficient filtering algo- rithm for the bi-objective Pareto constraint. The effi- ciency of this algorithm is experimentally confirmed on classical bi-objective benchmarks.},
keywords = {Bi-Objective, Global Constraint, OscaR},
author = {Renaud Hartert},
editor = {Pierre Schaus}
}
@article {135,
title = {Bound-Consistent Spread Constraint, Application to load balancing in nurse-to-patient assignments},
journal = {(EJCO) EURO Journal on Computational Optimization},
year = {2013},
abstract = {Given a vector of finite domain variables, the spread constraint aims at minimizing the sum of squares of these variables while constraining the sum of these to be equal to a given value. We improve the existing filtering for spread achieving a bound-consistent filtering without increasing the complexity. Previous versions of the algorithm considered a relaxed version of the bound-consistency assuming interval domains defined on rational numbers rather than integers. We apply our new algorithm to a real life problem: the daily assignment of newborn infant patients to nurses in a hospital. The objective is to balance the workload of the nurses, while satisfying a variety of side constraints. Prior work proposed a MIP model for this problem, which unfortunately did not scale to large instances and only approximated the objective function, since minimizing the variance cannot be expressed in a linear model. This paper presents a two-step approach, first assigning nurses to region of the hospital then assigning the patients to these. We show that our approach allows to tackle large instances with hundreds of patients and nurses in a few seconds using the OscaR optimization system.},
author = {Pierre Schaus and Jean-Charles R{\'e}gin}
}
@proceedings {126,
title = {Multi-Objective Large Neighborhood Search},
year = {2013},
edition = {Springer},
abstract = {Large neighborhood search (LNS) [25] is a framework that combines the expressiveness of constraint programming with the efficiency of local search to solve combinatorial optimization problems. This paper introduces an extension of LNS, called multi-objective LNS (MO-LNS), to solve multi-objective combi- natorial optimization problems ubiquitous in practice. The idea of MO-LNS is to maintain a set of nondominated solutions rather than just one best-so-far solu- tion. At each iteration, one of these solutions is selected, relaxed and optimized in order to strictly improve the hypervolume of the maintained set of nondom- inated solutions. We introduce modeling abstractions into the OscaR solver for MO-LNS and show experimentally the efficiency of this approach on various multi-objective combinatorial optimization problems.},
author = {Pierre Schaus},
editor = {Renaud Hartert}
}
@proceedings {128,
title = { Revisiting the cardinality reasoning for BinPacking constraint },
year = {2013},
abstract = {In a previous work, we introduced a filtering for the Bin- Packing constraint based on a cardinality reasoning for each bin com- bined with a global cardinality constraint. We improve this filtering with an algorithm providing tighter bounds on the cardinality variables. We experiment it on the Balanced Academic Curriculum Problems demon- strating the benefits of the cardinality reasoning for such bin-packing problems.},
author = {Fran{\c c}ois Pelsser},
editor = {Pierre Schaus}
}
@proceedings {132,
title = {Sparse-Sets for Domain Implementation},
year = {2013},
abstract = {This paper discusses the usage of sparse sets for integer do- main implementation over traditional representations. A first benefit of sparse sets is that they are very cheap to trail and restore. A second key advantage introduced in this work is that sparse sets permit to get delta changes with a very limited cost, allowing efficient incremental propaga- tion. Sparse sets can also be used to represent subset bound domains for set variables.},
keywords = {constraint programming, domain implementation, domain representation, sparse sets},
author = {Vianney le Cl{\'e}ment and Pierre Schaus and Christine Solnon and Christophe Lecoutre}
}
@proceedings {125,
title = { Variable Objective Large Neighborhood Search: A practical approach to solve over-constrained problems},
year = {2013},
edition = {IEEE},
abstract = {Everyone having used Constraint Programming (CP) to solve hard combinatorial optimization problems with a standard exhaustive Branch \& Bound Depth First Search (B\&B DFS) has probably experienced scalability issues. In the 2011 Panel of the Future of CP, one of the identified challenges was the need to handle large-scale problems. In this paper, we address the scalability issues of CP when minimizing a sum objective function. We suggest extending the Large Neighborhood Search (LNS) framework enabling it with the possibility of changing dynamically the objective function along the restarts. The motivation for this extended framework - called the Variable Objective Large Neighborhood Search (VO-LNS) - is solving efficiently a real-life over-constrained timetabling application. Our experiments show that this simple approach has two main benefits on solving this problem: 1) a better pruning, boosting the speed of LNS to reach high quality solutions, 2) a better control to balance or weight the terms composing the sum objective function, especially in over- constrained problems.},
author = {Pierre Schaus}
}
@conference {tap_cp2012,
title = {Cardinality Reasoning for bin-packing constraint. Application to a tank allocation problem},
booktitle = {CP2012: 18th International Conference on Principles and Practice of Constraint Programming, Qu{\'e}bec City, Canada},
year = {2012},
abstract = {Flow reasoning has been successfully used in CP for more than a decade. It was originally introduced by R ́egin in the well-known Alldifferent and Global Cardinality Constraint (GCC) available in most of the CP solvers. The BinPacking constraint was introduced by Shaw and mainly uses an independent knapsack reasoning in each bin to filter the possible bins for each item. This paper considers the use of a cardinal- ity/flow reasoning for improving the filtering of a bin-packing constraint. The idea is to use a GCC as a redundant constraint to the BinPacking that will count the number of items placed in each bin. The cardinality variables of the GCC are then dynamically updated during the propaga- tion. The cardinality reasoning of the redundant GCC makes deductions that the bin-packing constraint cannot see since the placement of all items into every bin is considered at once rather than for each bin in- dividually. This is particularly well suited when a minimum loading in each bin is specified in advance. We apply this idea on a Tank Allocation Problem (TAP). We detail our CP model and give experimental results on a real-life instance demonstrating the added value of the cardinality reasoning for the bin-packing constraint.},
author = {Pierre Schaus and Jean-Charles R{\'e}gin and Rowan Van Schaeren and Wout Dullaert and Birger Raa}
}
@article {constraints2010_steelmillslab,
title = {Solving Steel Mill Slab Problems with Constraint-Based Techniques: CP, LNS, and CBLS},
journal = {Journal of Constraints},
year = {2011},
abstract = {The Steel Mill Slab Problem is an optimization benchmark that has been studied for a long time in the constraint-programming community but was only solved efficiently in the two last years. Gargani and Refalo solved the problem using Large Neighborhood Search and Van Hentenryck and Michel made use of constraint programming with an improved symmetry breaking scheme. In the first part of this paper, we build on those approaches, present improvements of those two techniques, and study how the problem can be tackled by Constraint-Based Local Search. As a result, the classical instances of CSPLib can now be solved in less than 50ms. To improve our understanding of this problem, we also introduce a new set of harder instances, which highlight the strengths and the weaknesses of the various approaches. In a second part of the paper, we present a variation of the Steel Mill Slab Problem whose aim is to minimize the number of slabs. We show how this problem can be tackled with slight modifications of our proposed algorithms. In particular, the constraint-programming solution is enhanced by a global symmetric cardinality constraint, which, to our knowledge, has never been implemented and used before. All the proposed approaches to solve this problem have been modeled and evaluated using Comet.},
author = {Pierre Schaus and Pascal Van Hentenryck and Jean-No{\"e}l Monette and C. Coffrin and L. Michel and Yves Deville}
}
@conference { ,
title = {Consistency check for the bin packing constraint revisited},
booktitle = {CPAIOR 2010},
volume = {6140/2010},
year = {2010},
month = {14/06/2010},
pages = {117-122},
publisher = {Springer Berlin / Heidelberg},
organization = {Springer Berlin / Heidelberg},
edition = {Springer},
address = {Bologna},
abstract = {In addition to a filtering algorithm, the Pack constraint for bin packing introduced by Shaw [Shaw04] uses a failure detection algorithm. This test is based on a reduction of the partial solution to a standard bin packing problem and the computation of a bin packing lower bound on the reduced problem. We propose two new reduction algorithms and prove that one of them theoretically dominates the others. Experimental results show that a combination of our reductions improves the quality of the failure detection.},
keywords = {bin packing, constraint programming, reduction},
isbn = {978-3-642-13519-4},
author = {Julien Dupuis and Pierre Schaus and Yves Deville}
}
@conference {123,
title = {Generic Adaptive Heuristics for Large Neighborhood Search},
booktitle = {Seventh International Workshop on Local Search Techniques in Constraint Satisfaction (LSCS2010)},
year = {2010},
abstract = {The Large Neighborhood Search (LNS) approach for solving Constrained Optimization Problems has been proved to be effective on a wide range of problems. LNS is a local search metaheuristic that uses a complete search method (such as CP) to explore a large neighborhood. At each step, the neighborhood is defined by relaxing a subset, called fragment, of the variables in the current solution. Despite the success of LNS, no general principle has emerged on how to choose the fragment from one restart to the other. Practitioners often prefer to relax randomly the solution to favor diversification. This work focuses on the design of generic adaptive heuristics for choosing automatically the fragment in LNS, improving the standard random choice. The defined heuristics are tested on the Car Sequencing problem for which we introduce a new original relaxation. From those experiments, we conclude that all our heuristics except one are performing better than a random fragment selection. We also show that our mean dynamic impact proximity and min/max dynamic impact proximity heuristics are significantly better than all the others.},
author = {Jean-Baptiste Mairy and Pierre Schaus and Yves Deville}
}
@conference {122,
title = {Revisiting the soft global cardinality constraint},
booktitle = {The seventh International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) techniques in Constraint Programming (CPAIOR) },
year = {2010},
abstract = {he Soft Global Cardinality Constraint (softggc) relaxes the Global Cardinality Constraint (gcc) by introducing a violation variable representing unmet requirements on the number of value occur- rences. A first domain consistent filtering algorithm was introduced by Van Hoeve et al. in 2004 using a minimum cost flow algorithm. A simpler and more efficient filtering algorithm was introduced in 2006 by Zanarini et al. using matchings in bipartite graphs. While the consistency check introduced in the second algorithm is correct, we show that the algorithm may not achieve domain consistency when cardinality requirements con- tain zeroes. We give new domain consistent conditions and show how to achieve domain consistency within the same time bounds. The softggc constraint was implemented in Comet (now also available in OscaR and OR-Tools).},
author = {Pierre Schaus and Pascal Van Hentenryck and Alessandro Zanarini}
}
@proceedings { ,
title = {V{\'e}rification de consistance pour la contrainte de bin packing revisit{\'e}e},
year = {2010},
author = {Julien Dupuis and Pierre Schaus and Yves Deville}
}
@conference { ,
title = {Failure detection for the Bin-Packing Constraint},
booktitle = {Second International Workshop on Bin Packing and Placement Constraints (BPPC{\textquoteright}09)},
year = {2009},
month = {20/09/2009},
abstract = {In addition to a filtering algorithm, the Pack constraint introduced by Shaw uses a failure detection algorithm. This test is based on a reduction of the partial solution to a standard bin-packing problem and the computation of a bin-packing lower bound (BPLB) on the reduced problem. A first possible improvement on Shaw?s test is to use a stronger BPLB. In particular, Labb{\'e} ?s lower bound was recently proved to dominate Martello?s lower bound used by Shaw. A second possible improvement is to use a reduction different from the one introduced by Shaw. We propose two new reduction algorithms and prove that one of them theoretically dominates the others. All the proposed improvements on the failure test are evaluated using the COMET System.},
keywords = {bin-packing, failure detection, pack constraint, reduction},
author = {Julien Dupuis and Pierre Schaus and Yves Deville}
}
@conference {115,
title = {Scalable load balancing in nurse to patient assignment problems},
booktitle = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR)},
year = {2009},
abstract = {This paper considers the daily assignment of newborn infant patients to nurses in a hospital. The objective is to balance the workload of the nurses, while satisfying a variety of side constraints. Prior work proposed a MIP model for this problem, which unfortunately did not scale to large instances and only approximated the objective function, since minimizing the variance cannot be expressed in a linear model. This paper presents constraint programming (CP) models of increasing complexity to solve large instances with hundreds of patients and nurses in a few seconds using the Comet optimization system. The CP models use the recent spread global constraint to minimize the variance, as well as an exact decomposition technique.},
author = {Pierre Schaus and Pascal Van Hentenryck and Jean-Charles R{\'e}gin}
}
@conference { ,
title = {A Global Constraint for Bin-Packing with Precedences: Application to the Assembly Line Balancing Problem.},
booktitle = {Twenty-Third AAAI Conference on Artificial Intelligence (AAAI-08)},
year = {2008},
month = {13/07/08},
publisher = {Association for the Advancement of Artificial Intelligence},
organization = {Association for the Advancement of Artificial Intelligence},
address = {Chicago},
abstract = {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.},
keywords = {Assembly Line Balancing, constraint programming, Global Constraints, Redundant Constraints},
author = {Pierre Schaus and Yves Deville}
}
@conference { ,
title = {Global Constraints for the Mean Absolute Deviation and the Variance: Application to the Vertical Line Balancing.},
booktitle = {Quantitative Methods for Decision Making. 22nd national conference of the Belgian Operations Research Society.},
year = {2008},
month = {16/01/2008},
pages = {15-16},
address = {Brussels},
author = {Pierre Schaus and Yves Deville}
}
@conference { ,
title = {Hybridization of CP and VLNS for Eternity II.},
booktitle = {Quatri{\`e}me Journ{\'e}es Francophones de Programmation par Contraintes (JFPC{\textquoteright}08)},
year = {2008},
abstract = {Eternity II is an edge-matching puzzle created by Christopher Monckton for the game editor Tomy(TM). Given 256 squared pieces with a color on each of the four sides of pieces and a $16 \times 16$ board, the goal is to place all the pieces such that two adjacent pieces have their common side of same color. This problem is NP-complete, has very few structure and is highly combinatorial ($256!\cdot 4^{256}$ possible combinations). Christopher Monkton is so confident in the difficulty of the problem that he promises a \$2 million prize to the first person who finds the solution. We don{\textquoteright}t have any hope (anymore) to find a solution to this problem, but we nevertheless decided to explain our strategy which might be useful for someone else still believing in his/her chances of success. Our procedure first initializes the board with constraint programming by relaxing the problem. Then we improve the solution with a very large neighborhood stochastic local search. Our neighborhood is very large (i.e. exponential) but can be explored in polynomial time by solving an assignment problem. Our procedure allows us to obtain rapidly good solutions with scores reaching 458/480 number of satisfied junctions. Our very large neighborhood can also be used in a brute-force approach to test $256!/128! \cdot 4^{128}$ combinations instead of $256!\cdot 4^{256}$. This paper is also an example of VLNS that can be applied on other matching problems.},
author = {Pierre Schaus and Yves Deville}
}
@proceedings { ,
title = {Une contrainte globale de bin-packing avec pr{\'e}c{\'e}dences: Application au probl{\`e}me d{\textquoteright}{\'e}quilibrage de lignes d{\textquoteright}assemblage},
year = {2008},
author = {Pierre Schaus and Yves Deville}
}
@conference { ,
title = {Bound-Consistent Deviation Constraint},
booktitle = {Principles and Practice of Contraint Programming (CP 2007)},
volume = {4741},
year = {2007},
month = {23/09/2007},
edition = {Springer},
address = {Providence, RI, USA},
author = {Pierre Schaus and Yves Deville and Pierre Dupont}
}
@proceedings { ,
title = {A CP Approach to the Balanced Academic Curriculum Problem},
year = {2007},
month = {23/09/2007},
abstract = {The Balanced Academic Curriculum Problem (BACP) has received little attention in Constraint Programming. Only a few articles deals with this problem with experimental results on the three small instances publicly available in CSPLIB. The present article describes an approach to efficiently solve this challenging problem. Optimal solutions are produced on a variety of randomly generated instances which generalize the CSPLIB test cases. This work describes four contributions to the resolution of this problem: a new branching heuristic, the use of dominance relations, experiments on several balance criteria and several search strategies among which an hybridization of Constraint Programming and Local Search.},
author = {Jean-No{\"e}l Monette and Pierre Schaus and St{\'e}phane Zampelli and Yves Deville and Pierre Dupont}
}
@conference { ,
title = {The Deviation Constraint},
booktitle = {4th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR{\textquoteright}07)},
volume = {4510},
year = {2007},
month = {23/09/2007},
pages = {260-274},
publisher = {Springer-Verlag},
organization = {Springer-Verlag},
address = {Brussels},
keywords = {Deviation, Global Constraints, Statistical Constraints},
author = {Pierre Schaus and Yves Deville and Pierre Dupont and Jean-Charles R{\'e}gin},
editor = {Pascal Van Hentenryck and Laurence Wolsey}
}
@conference { ,
title = {La Contrainte D{\'e}viation},
booktitle = {Troisi{\`e}me Journ{\'e}es Francophones de Programmation par Contraintes (JFPC{\textquoteright}07)},
year = {2007},
month = {04/06/2007},
pages = {173-182},
address = {Rocquencourt, France},
author = {Pierre Schaus and Yves Deville and Pierre Dupont and Jean-Charles R{\'e}gin}
}
@inbook { ,
title = {Simplification and extension of the SPREAD Constraint},
booktitle = {Future and Trends of Constraint Programming},
year = {2007},
pages = {95-99},
author = {Pierre Schaus and Yves Deville and Pierre Dupont and Jean-Charles R{\'e}gin},
editor = {F. Benhamou and N. Jussien and B. O{\textquoteright}Sullivan}
}
@conference { ,
title = {Simplification and extension of the SPREAD Constraint},
booktitle = {CP2006 Third International Workshop on Constraint Propagation and Implementation},
year = {2006},
pages = {72-92},
address = {Nantes},
author = {Pierre Schaus and Yves Deville and Pierre Dupont and Jean-Charles R{\'e}gin}
}