biblio

Sophie Demassey

xkcd

thematic bibliography

MINLP for water distribution systems

AE 16
Gratien Bonvin, Sophie Demassey, Claude Le Pape, Nadia Maïzi, Vincent Mazauric, Alfredo Sampiero 2016 A convex mathematical program for pump scheduling in a class of branched drinking water networks Applied Energy (accepted). We focus on a specific, still widespread, class of water networks: the typical branched drinking water networks in rural zones with one pumping station and disseminated water towers. We show that, in this context, the mixed integer non-linear formulation of the day-ahead pump scheduling problem can be made convex, thus more tractable. We provide a deep experimental study on a real use-case.
EURO 15
Gratien Bonvin, Sophie Demassey 2015 Energy efficiency in water supply systems : variable speed drives vs pumping scheduling 27th European Conference on Operational Research (EURO'15), 12-15 july 2015, Glasgow. Where we compare the opportunities of installing variable speed drives vs. optimizing the pump schedule in a drinking water pumping station.
ICAE 15
Gratien Bonvin, Alfredo Samperio, Claude Le Pape, Vincent Mazauric, Sophie Demassey, Nadia Maïzi 2015 A heuristic approach to the water networks pumping scheduling issue Energy Procedia (2015) 75: 2846-2851. 7th International Conference on Applied Energy (ICAE'15), 28-31 march 2015, Abu Dhabi, UAE. A summary of Gratien's work during his internship at Schneider Electric on the day-ahead Pump Scheduling Problem in a drinking water pumping station. We present a convex Mixed Integer Quadratically Constrained Program and a Benders-like heuristic approach.

models and algorithms in CP

ROADEF 15
Sophie Demassey, Dominique Feillet 2015 Hybridation de programmation linéaire et de programmation par contraintes pour le problème de déplacement de conteneurs 16ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'15), 11-12 february 2015, Marseille, France. An attempt to solve the Container Relocation Problem with CP: a lower bound is required ! (Note that MIP is really bad on this problem) We MIPped such a lower bound in our CP model and filtered accordingly. By the way Choco/Gurobi is an easy mix under Java.
CPAIOR 12
Gilles Chabert, Sophie Demassey 2012 The Conjunction of Interval Among Constraints Lecture Notes in Computer Science (2012) 7298: 113-128. 9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'12), 28 may-1 june 2012, Nantes. We call Interval-Amongs a conjunction of among constraints on interval value domains. We prove that such a conjunction is in P (while the general case is NP-hard) using a new vertical "cardinality-based" decomposition made of a temporal constraint network and a flow network model. We derive from this a relaxed BC algorithm simple to implement as the conjunction of an all-shortest-paths filtering with a (flow-based) GCC. This is compared, both theoretically and empirically, to the standard horizontal "among-based" decomposition. Finally, we prove that Box-Amongs, i.e. the problem in higher dimensions, remains NP-hard.
RR 11
Gilles Chabert, Frédéric Boyer, Sophie Demassey 2011 Multi-Agent Electro-Location and the Among Constraint INRIA, Research Report 00598712. The application-oriented variant of paper (cpaior12) above. Gilles has exhibited the Interval-Amongs constraint in the problem of localization of robots equipped with the electric sense. This occurs in the context of the reconfigurable anguilliform swimming robot imagined by Frédéric.
AOR 10
Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Emmanuel Poder 2010 New filtering for the cumulative constraint in the context of non-overlapping rectangles Annals of Operations Research(2011) 184 (1): 27-50. [doi] We formalize and study the complexity of the longest hole problem: it is to find the longest period during which tasks can be scheduled on a cumulative resource with a resource vacancy lower than a given slack value. A bounding algorithm for this problem and a filtering for the cumulative constraint based on this bound have been implemented in geost.

flexible datacenter resource management with CP

BtrPlace
BtrPlace is an open source datacenter resource manager based on the Constraint Programming solver Choco. It is mainly developed by Fabien Hermenier at University of Nice The specificities of our approach of resource management are: (1) to dynamically compute not only the target configuration but also the schedule of the reconfiguration actions required to reach it, (2) to offer, thanks to CP, extensibility -- ease to implement new user requirements offline -- and configurability -- automatic integration of predefined user requirements online. The sources are available on the website as well as the documentation, the research papers, and a sandbox to play with it.
Packing 15
Sophie Demassey, Fabien Hermenier, Vincent Kherbache 2015 Dynamic Packing with Side Constraints for Datacenter Resource Management in G. Fasano and J.D. Pintér. eds, Optimized Packings and Their Applications, Springer Optimization and Its Applications vol. 105, Springer, New York. This chapter describes the variant of the vector packing problem considered in BtrPlace in the context of datacenter resource management, giving an insight into its dynamic and heterogeneous nature.
PGMO-COPI 14
Sophie Demassey, Fabien Hermenier 2014 BtrPlace: Flexible VM Management in Data Centers Conference on Optimization & Practices in Industry (PGMO-COPI'14), 28-31 october 2014, Paris-Saclay, France. 3p. Presentation of the last results todate of BtrPlace.
CP 11
Fabien Hermenier, Sophie Demassey, Xavier Lorca 2011 Bin-Repacking Scheduling in Virtualized Datacenters Lecture Notes in Computer Science (2011) 6876: 27-41. 17th International Conference on Principles and Practice of Constraint Programming (CP'11), application track, 13-16 september 2011, Perugia, Italy. [doi, slides, annex] Take an in-fashion domain (cloud !), a combined packing and scheduling problem (where and when to migrate ?), a singular scheduling property (concurrent resource requirements during live migration), and various side placement constraints, and say: CP is fun. We present the CP model and search heuristic implemented with Choco in Entropy the former version of BtrPlace, an autonomous VM manager conceived and developed by Fabien. Since the submission, we have greatly improved our implementation. Newer computational results for the experiments of the paper are available in this annex report (sep 26, 2011).

automata and optimization constraints for rostering

seminar CMP 14
Sophie Demassey 2014 Flexible Optimization: Nurse Scheduling with Constraint Programming and Automata Invited Seminar at CMP, École des Mines de Saint-Étienne, 3 july 2014.
Julien's PhD
Julien Menana 2011 Automates et programmation par contraintes pour la planification de personnel PhD Thesis in Computer Science, University of Nantes, 28 october 2011.
PATAT 10
Julien Menana, Sophie Demassey 2010 Weighted Automata, Constraint Programming, and Large Neighborhood Search Nurse Rostering Competition at the 8th International Conference for the Practice and Theory of Automated Timetabling (PATAT'10), 10-13 august 2010, Belfast, Ireland. We propose an automated planner, implemented with Choco, answering to the specifications of the NRP competition. The parser builds and compounds a multi-weighted automaton from a given set of soft scheduling rules, and then a CP model based on one Multicost-Regular per nurse and one Global Cardinality per period. The model is optimized heuristically through LNS.
RR 10
Julien Menana, Sophie Demassey, Narendra Jussien 2010 Modélisation et optimisation des préférences en planification de personnel École des Mines de Nantes, Research Report 11-01-INFO.
We present an algorithm for intersecting weighted automata as a multi-weighted automaton. In the context of Employee Timetabling with Preferences, this can be used to aggregate the rules which constrain the timetable of an employee and to count their violation degrees. The automaton can be embedded in a Multicost-Regular constraint or in the soft variant, that we introduce in this paper, to handle violations costs associated to the violation degrees through any penalty functions.
CPAIOR 09
Julien Menana, Sophie Demassey 2009 Sequencing and counting with the multicost-regular constraint Lecture Notes in Computer Science (2009) 5547: 178 - 192. 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'09), 27-31 may 2009, Pittsburgh, USA. We introduce Multicost-Regular, an extension of the Cost-Regular constraint to handle vectors of costs. It is equivalent to an instance of the Resource Constrained Longest/Shortest Path Problem in a layered graph and thus is NP-complete. We present a lagrangian-based filtering algorithm for this constraint.
JFPC 09
Julien Menana, Sophie Demassey 2009 Séquencer et compter avec la contrainte multicost-regular Proc. p. 125-134. 5èmes Journées Francophones de Programmation par Contraintes (JFPC'09), 3-5 june 2009, Orléans, France.
ROADEF 09b
Julien Menana, Sophie Demassey, Narendra Jussien 2009 Relaxation lagrangienne pour le filtrage d'une contrainte-automate à coûts multiples 10ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'09), 11-12 february 2009, Nancy, France.
Constraints 06
Sophie Demassey, Gilles Pesant, Louis-Martin Rousseau 2006 A Cost-Regular based Hybrid Column Generation Approach Constraints(2006) 11 (4) : 315 - 333. [doi] This extends the paper of CPAIOR'05 with a discussion about optimization global constraints, with a variable-value selection strategy coupled to the cost-regular constraint, with a heuristic and a branching strategy for the CP-based column generation model of the Employee Timetabling Problem, and with experiments on two complex real-case studies.
CPAIOR 05
Sophie Demassey, Gilles Pesant, Louis-Martin Rousseau 2005 Constraint programming based column generation for employee timetabling Lecture Notes in Computer Science (2005) 3524: 140 - 154. 2nd International Conference on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'05), 30 may - 2 june 2005, Prague, Czech Republic. We introduce Cost-Regular, the optimization variant of the Regular constraint. Given a weighted automaton, it enforces a sequence of variables to belong to the regular language specified by the automaton and a cost variable to be equal to the total weight of the sequence. This constraint is used to optimize the subproblem of column generation in the Set Covering ILP model of the Employee Timetabling Problem.
JOPT 05
Sophie Demassey, Gilles Pesant, Louis-Martin Rousseau 2005 Constraint programming based column generation for employee timetabling Optimization Days (JOPT'05), 9 - 11 may 2005, Montréal, Canada.

column generation for railway infrastructure capacity

Aurélien's PhD
Aurélien Merel 2012 Évaluation biobjectif de la capacité d'infrastructures ferroviaires par génération de colonnes hybride PhD Thesis in Computer Science, University of Nantes, 31 october 2012.
MIC 11
Aurélien Merel, Xavier Gandibleux, Sophie Demassey 2011 A collaborative combination between column generation and ant colony optimization for solving set packing problems 9th Metaheuristics International Conference (MIC'11), 25-27 july 2011, Udine, Italy. To speed up an ACO procedure on large-size SPP instances, a column generation procedure is applied as a preprocessing step: the search space of the heuristic is restricted to the columns (the subsets) generated so far, and bounded by the optimum of the LP relaxation computed in the same time.
RailRome 11
Aurélien Merel, Xavier Gandibleux, Sophie Demassey 2011 Assessing railway infrastructure capacity by solving the saturation problem with an improved column generation algorithm IAROR Conference: 4th International Seminar on Railway Operations Modelling and Analysis (RailRome'11), 16-18 february 2011, Rome, Italy. Long version submitted to Journal of Rail Transport Planning & Management, May 24, 2011.
WCRR 11
Aurélien Merel, Xavier Gandibleux, Sophie Demassey 2011 Towards a Realistic Evaluation of Railway Infrastructure Capacity 9th World Congress on Railway Research (WCRR'11), 22-26 may 2011, Lille, France. We describe our implementation of a CG-ACO algorithm for the railway infrastructure capacity problem in the RECIFE software.
ROADEF 10
Aurélien Merel, Xavier Gandibleux, Sophie Demassey 2010 Un algorithme de génération de colonnes pour le problème de capacité d'infrastructure ferroviaire 11ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'10), 24-26 february 2010, Toulouse, France.
ROADEF 09a
Aurélien Merel, Xavier Gandibleux, Sophie Demassey, Richard Lusby 2009 An improved upper bound for the railway infrastructure capacity problem on the Pierrefitte-Gonesse junction Long paper in Proc. p. 62-76, ISBN 2-905267-65-8. 10ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'09), 11-12 february 2009, Nancy, France. The capacity of a railway node is the maximum number of trains which can be routed through the infrastructure whith respect to safety constraints, given a large set of possible trains, schedules and allowed delays. We tackle the SPP formulation of this problem with column generation. At each iteration, we exploit the redundancy and dominance relation between the constraints of the restricted master program in order to speed up its resolution.

ILP decompositions and CP for the RCPSP

ISTE 08
Christian Artigues, Sophie Demassey, Emmanuel Néron (eds.) 2008 Resource-Constrained Project Scheduling: models, algorithms, extensions and applications ISTE/Wiley, ISBN 978-1-84821-034-9.
ISTE 08b
Sophie Demassey 2008 Mathematical Programming Formulations and Lower Bounds for the RCPSP Chapter 3 in Resource-Constrained Project Scheduling: models, algorithms, extensions and applications, C. Artigues, S. Demassey, E. Néron (eds.), ISTE/Wiley, ISBN 978-1-84821-034-9.
ISORMS 06
Emmanuel Néron, Christian Artigues, Philippe Baptiste, Jacques Carlier, Sophie Demassey, Philippe Laborie 2006 Lower bounds computation for RCPSP chapter in Perspectives in modern project scheduling, J. Weglarz, J. Jozefowska (eds.), Springer, ISBN 978-0-387-33643-5, International Series in Operations Research & Management Science, Vol. 92.
IJOC 05
Sophie Demassey, Christian Artigues, Philippe Michelon 2005 Constraint propagation based cutting planes : an application to the resource-constrained project scheduling problem INFORMS Journal on Computing(2005) 17 (1) : 52 - 65. We examine various filtering rules for the resource and temporal constraints of the RCPSP and use the result of their propagation to preprocess and to generate several valid linear inequalities for both the continous-time and the time-indexed MIP models. In our experiments, we observe the capacity of the cuts to improve the lower bounds computed by the LP-relaxations in constructive and destructive (progressive UB rejection) ways.
PIP 05
Christian Artigues, Sophie Demassey 2005 Gestion de projet chap. IV de Gestion de la production et ressources humaines: méthodes de planification dans les systèmes productifs, A. Hait (éd.), Presses internationales Polytechnique, Montréal, Canada, ISBN 978-2-553-01145-0.
ROADEF 05
Thierry Garaix, Christian Artigues et Sophie Demassey 2005 Bornes basées sur les ensembles interdits pour le problème d'ordonnancement de projet à moyens limités 6ème congrès de la société française de recherche opérationnelle et d'aide à la décision (ROADEF'05), 14-16 february 2005, Tours, France.
ORSpectrum 04
Philippe Baptiste, Sophie Demassey 2004 Tight LP bounds for Resource Constrained Project Scheduling OR Spectrum(2004) 26 : 251 - 262. see also: computational results. We complement the approach followed up in IJOC'05 of CP-based preprocessing and cut generation for MIP models of the RCPSP. We consider Mingozzi's relaxed MIP formulation, propose new valid linear inequalities including cuts based on energetic reasoning, and a strong preprocessing obtained by intensive constraint propagation. This initial CP model includes redundant disjunctive constraints inferred by... MIPs!
PMS 04
Sophie Demassey, Christian Artigues, Philippe Baptiste, Philippe Michelon 2004 Lagrangean relaxation-based lower bounds for the RCPSP 9th international workshop on project management and scheduling (PMS'04), 26-28 april 2004, Nancy, France. We investigate a lagrangian relaxation of Mingozzi's formulation of the RCPSP. The model decomposes in one multiknapsack problem for each time period (to compute a feasible set) and in one project scheduling problem with time-dependent costs but no resource constraints, which amounts to a minimum cut problem solvable in polynomial time.
PhD 03
Sophie Demassey 2003 Méthodes hybrides de programmation par contraintes et programmation linéaire pour le problème d'ordonnancement de projet à contraintes de ressources PhD Thesis in Computer Science - Combinatorial Optimization, University of Avignon, 18 december 2003.
download: .pdf (french, hyperref, 1.2 MB), .ps.gz (french, 792 KB)
CPAIOR 02
Sophie Demassey, Christian Artigues, Philippe Michelon 2002 A hybrid constraint propagation-cutting plane algorithm for the RCPSP 4th International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'02), 25-27 march 2002, Le Croisic, France, Proc. p. 321-331. Preliminary study for IJOC'05: CP-based valid linear inequalities for the time-indexed MIP formulation of the RCPSP.
OR 02
Christian Artigues, Sophie Demassey, Philippe Michelon 2002 A hybrid constraint propagation-cutting plane algorithm for the RCPSP International Conference on Operations Research (OR'02), 2-5 september 2002, Klagenfurt, Germany.
ROADEF 02
Sophie Demassey, Christian Artigues, Philippe Michelon 2002 Bornes inférieures pour le RCPSP : une approche hybride propagation de contraintes - programmation linéaire Proc. p.105-106. 4ème congrès de la société française de recherche opérationnelle et d'aide à la décision (ROADEF'02), 20-22 february 2002, Paris, France.
CIRO 02
Philippe Michelon, Sophie Demassey, Christian Artigues 2002 Bornes inférieures pour le RCPSP : une approche hybride PPC/PL 3ème Conférence Internationale de Recherche Opérationnelle (CIRO'02), 4-6 june 2002, Marrakech, Maroc.
Cosolv 01
Sophie Demassey, Christian Artigues, Philippe Michelon 2001 Comparing lower bounds for the RCPSP under a same hybrid constraint-linear programming approach Proc. p. 109-123. Workshop on Cooperative Solvers in Constraint Programming (CoSolv'01), International Conference on Constraint Programming (CP'01), 2001, Paphos, Cyprus. Preliminary study for IJOC'05: first cuts.
FRANCORO 01
Sophie Demassey, Christian Artigues, Philippe Michelon 2001 Bornes inférieures pour le problème d'ordonnancement de projet à contraintes de ressources 3èmes Journées Francophones de Recherche Opérationnelle (Francoro'01), 9-12 may 2001, Québec, Canada.
ISMP 00
Christian Artigues, Sophie Demassey, Philippe Michelon 2000 A linear programming based approach for resource constrained project scheduling International Symposium on Mathematical Programming (ISMP'00), 2000, Atlanta, USA.
MSc 00
Sophie Demassey 2000 Borne inférieure pour l'ordonnancement de projet à moyens limités MSc Thesis (Mémoire de DEA) in Computer Science - Combinatorial Optimization, University of Aix-Marseille II, 2000.

systematic reformulation of global constraints

Constraints 07
Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Thierry Petit 2007 Global Constraint Catalog: Past, Present and Future Constraints(2007) 12 (1): 21-62. [doi]. We present the objectives of the Global Constraint Catalog and the results to date. The catalog is a base of knowledge referring most of the studies on global constraints of the literature. It is also an electronic dictionary conceived to be processed in a systematic way. This includes the reformulation of constraints in terms of graph properties or of automata.
CP 06
Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Thierry Petit 2006 Graph Properties Based Filtering Lecture Notes in Computer Science (2006) 4204: 59-74. 12th International Conference on Principles and Practice of Constraint Programming (CP'06), 24-29 sep 2006, Nantes, France. Most global constraints of the catalog have a reformulation as a graph in that the solutions of a constraint are in 1-to-1 correspondence with the subgraphs satisfying some given bounds on some given invariants. A previous paper by Nicolas, Thierry and Guillaume Rochart showed how to estimate the most common invariants. In this paper, we show how to filter the graph (remove and fix nodes and arcs) in case of the estimate coincides with a bound. This results in a generic filtering algorithm for various global constraints.
JFPC 06
Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Thierry Petit 2006 Filtrage basé sur des propriétés de graphe 2èmes Journées Francophones de Programmation par Contraintes (JFPC'06), 7-9 jun 2006, Nîmes, France.

resolution search

HYBRID 06
Sophie Demassey 2006 Experiments with Resolution search Workshop on Hybrid methods and branching rules in combinatorial optimization (Hybrid'06), 18-22 september 2006, Montréal, Canada. A terrific optimization algorithm.
Concordia 05
Sophie Demassey 2005 Resolution search and intelligent backtrackings invited seminar ConCoCO, 16 june 2005, University of Concordia, Montréal, Canada.
CRT 04
Sophie Demassey 2004 Resolution search et backtrackings intelligents invited seminar CIRRELT (ex CRT), 5 novembre 2004, Université de Montréal, Canada.
ECCO 04
Sophie Demassey 2004 An application of resolution search to the RCPSP 17th European Conference on Combinatorial Optimization (ECCO'04), 24-26 june 2004, Beyrouth, Lebanon.
PM 03
Sophie Demassey 2003 Resolution search et backtrackings intelligents invited seminar, 1ère journée du GDT Programmation Mathématique, 5 december 2003, Paris.
EARO 03
Sophie Demassey, Serigne Gueye, Philippe Michelon, Christian Artigues 2003 Application de resolution search au RCPSP École d'Automne de Recherche Opérationnelle (EARO'03), 28-31 october 2003, Tours. Resolution Search is a complete non-tree search algorithm created by Vašek Chvátal, which uses some kind of SAT solver to manage the nogood set and thus to guide the search towards almost-unexplored spaces. We have experimented it on a BIP formulation of the RCPSP. The study is described in french with more details in my PhD thesis.

commutative algebra

MSc 98
Sophie Demassey 1998 Élasticité dans les anneaux de Dedekind MSc Thesis (Mémoire de DEA) in Pure Mathematics - Commutative Algebra, University of Aix-Marseille I, 1998.

credits: drawing from XKCD - last update: january 2016