thematic bibliography
nonsmooth nonconvex optimization
 PJO24

Ksenia Syrtseva, Welington de Oliveira, Sophie Demassey, Wim van Ackooij
Minimizing the difference of convex and weakly convex functions via bundle method
Pacific Journal of Optimization (2024) In honor of the 75th Birthday of Professor Masao Fukushima.
We continue our work on solving nonsmooth nonconvex problems with proximal methods, addressing here a still broader class of problems defined by difference of convex and weakly convex functions in the objective and in the constraints. We present a new reformulation, still based on the improvement function, and an original rule to update the proximal parameter which provides stronger convergence results. The performance of the algorithm is illustrated on different stochastic problems.
 COA 20

Wim van Ackooij, Sophie Demassey, Paul Javal, Hugo Morais, Welington de Oliveira, Bhargav Swaminathan
A bundle method for nonsmooth DC programming with application to chanceconstrained problems
Computational Optimization and Applications (2021) 78: 451490.
We address nonsmooth nonconvex problems with objective and constraints defined by DifferenceofConvex (aka DC, aka convexconcave) functions. The DC constraints are handled through an improvement function instead of penalization or linearization. The resulting convexlyconstrained DC program is solved with a proximal bundle method, leading to a critical point of the original DCconstrained program and even a Bstationary point under some additional regularity properties. We also propose a reformulation of probabilistic constraints as DC constraints and assess the method on several classes of deterministic and chanceconstrained optimization problems.
scheduling and planning in power systems
 SEGAN23

Ksenia Syrtseva, Welington de Oliveira, Sophie Demassey, Hugo Morais, Paul Javal, Bhargav Swaminathan
DifferenceofConvex Approach to ChanceConstrained Optimal Power Flow modelling the DSO Power Modulation Lever for Distribution Networks
Sustainable Energy, Grids and Networks 36 (2023) article 101168
We address the joint chanceconstrained variant of a nonconvex OPF issuing from the operational planning of a distribution network, to take into account the correlation between the generation and load profiles. We model this stochastic problem accurately as a DC program by approximating only the characteristic function that appears in the expected value operator, but not the load flow equations, then solve it with the proximal bundle algorithm of [COA20]. The approach yields a natural and embarrassingly parallelizable scenario decomposition.
 ROADEF 20

Arnold N'Goran, Sophie Demassey
Engagement optimal de production d’une centrale solaire photovoltaique
21ème congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF'20), Montpellier, France.
In this market, the independent PV electricity producers declare the profile they commit to supply to the grid the day after, then will pay penalties for each deviation to this commitment. We propose and compare deterministic, stochastic and robust optimization approaches to solve this tactical problem.
 ISGT 19

Arnold N'Goran, Bruno Daugrois, Marc Lotteau, Sophie Demassey
Optimal engagement and operation of a gridconnected PV/battery system
2019 IEEE PES Innovative Smart Grid Technologies Europe (ISGTEurope'19), Bucharest, Romania.
An experimental comparison between a coarsegrained MIQP model solved at optimality with a finegrained numerical model optimized by a genetic algorithm to control a gridconnected PV/battery system. Our conclusion: seeking for optimality is financially profitable even if it requires to consider loose approximation of the system dynamics to remain fast. The periodic recomputation of the optimal command makes up for the model flaws. Preliminary results presented at Roadef'18.
 ICAE 19

Gildas Siggini, Edi Assoumou, Sophie Demassey
Investment choices and capacities at risk in decarbonizing the EU electric system
11th International Conference on Applied Energy (ICAE'19), Västerås, Sweden.
In this paper, we analyze the implications of fully or nearly fully decarbonizing the European electric system by 2050 with a new ETSAP TIMES linear programming model.
 PGMO 19a

Paul Javal, Wim van Ackooij, Sophie Demassey, Welington de Oliveira
A DifferenceofConvex Approach for Optimal Power Flow Problems with Probability Constraints
Annual meeting of the Gaspard Monge Program for Optimization and Operations Research and their interactions with Data Sciences (PGMO'19), Paris Saclay, France.
Modelling the optimal power flow with probability constraints as a DCconstrained DC program. Also presented at PID'19, ROADEF'20.
 ISMP 18a

Sophie Demassey, Edi Assoumou, Welington De Oliveira
Robust optimisation of storage in a power generation expansion planning problem
23rd International Symposium on Mathematical Programming (ISMP'18), Bordeaux, France.
Coupling a longterm power generation expansion planning model with a midterm storage optimization model to handle uncertainties in renewable production.
Also presented at PGMO days 18.
 ISMP 18b

Paul Javal, Welington de Oliveira, Hugo Morais, Wim van Ackooij, Sophie Demassey
Modelling distributed energy resources uncertainties in shortterm operational planning optimisation
23rd International Symposium on Mathematical Programming (ISMP'18), Bordeaux, France.
Identifying the new levers to operate when controlling the power distribution network.
 EuroPar 17

Fabien Hermenier, Giovanni Giuliani, Andrea Milani, Sophie Demassey
2017
Scaling Energy Adaptive Applications for Sustainable Profitability
Lecture Notes in Computer Science (2017) 10417: 2335.
EuroPar'17 Parallel Processing: 23rd International Conference, Santiago de Compostella, Spain.
Carver is a CPbased solution developed in the context of the european project DC4Cities to orchestrate energyadaptive applications in datacenters, according to performance and environmental preferences, given forecasts of the renewable energy production.
 EURO 16b

Aurélien Havel, Sophie Demassey
2016
Robust optimisation for a smart grid
28th European Conference on Operational Research (EURO'16), 36 july 2016, Poznan.
We extended the bilevel math programming model by P.L. Poirion (PhD Thesis 2015) for the robust design of a microgrid connected to the public grid by implementing distributed load shedding and network service options.
MINLP for water distribution systems
 ISCO 24

Sophie Demassey, Valentina Sessa, Amirhossein Tavakoli
2024
Alternating direction method and deep learning for discrete control with storage
Lecture Notes in Computer Science (2017) 14594: 8596.
ISCO'24 Combinatorial Optimization La Laguna, Tenerife, Spain
Consider optimizing over the continuous storage profiles (the state variables) instead of the dynamic discrete control: we may loose some convergence guarantees but get, in return, a practical approach relying on a tractable decomposition. We adopt an ADMlike way to guide the search, starting from a promising learned storage profile and progressively synchronizing states and control. This results in an original ML/CO hybrid approach which proves to be effective in quickly computing feasible solutions for the pump scheduling problem, by taking advantage of: both spatial and temporal problem decomposition, multiple predictions for multistart ADM, generalization/scaling in Deep Learning. Slides at ISCO'24 and previous talks at Roadef'24: about deep learning and adm.
 Amir 23

Amirhossein Tavakoli
Combinatorial Optimization and deep learning for energyefficient water distribution networks
PhD thesis directed with Valentina Sessa and defended 20/12/2023, SophiaAntipolis.
 ETSAP 23

Sophie Demassey
Combinatorial Optimization for Water Management
Joint autumn School 2023 of IEAETSAP and the Transition Institute 1.5, SophiaAntipolis, nov 2023.
Very short introduction to combinatorial optimization and overview of applications in water management. See the slides.
 OR 23

Sophie Demassey
Monotropic bilevel programming: duality in hydraulic network optimization
Seminar on Water Network Optimization by the working group on network optimization OR of the CNRS research network on Operational Research GdR RO, Paris 20/10/2023.
Slightly augmented version of PMNL 23 with a focus on the water network optimization problems. See the slides.
 PMNL 23

Sophie Demassey
Strong duality reformulation for bilevel optimization over nonlinear flow networks
Day of the working group on nonlinear programming PMNL of the CNRS research network on Operational Research GdR RO, Paris 23/06/2023.
Discussion on the formulation of certain nonconvex MINLPs as bilevel programs with integer variables at the upper level and monotropic programs at the lower level, and how to exploit the duality property of monotropic programming for solving the resulting nonconvex MINLP. We illustrate different options on two water network optimization problems: the convex MINLP reformulation of the pipe sizing problem, generation of valid inequalities and an alternating decomposition method for the pump scheduling problem. See the slides. Preliminary results presented at Roadef 23, PGMO 21.
 ICAE 22

Amirhossein Tavakoli, Valentina Sessa, Sophie Demassey
Strengthening mathematical models for pump scheduling in water distribution
14th International Conference on Applied Energy (ICAE'22), Bochum, Germany.
Intensive OBBT (optimizationbased bound tightening) preprocessing for the nonconvex MINLP model of the pump scheduling problem to speed up the algorithm proposed in OE 20. The variable bounds are computed on suited relaxations exploiting the temporal decomposition of the model. We also employ probing and disjunctive programming techniques to derive conditional bounds relating different elements of the water network, as well as mixed integer rounding techniques to lift valid inequalities for integer compound variables. Also presented by Amir at Roadef 23, Sophia Summit 23.
 MINLP 21

Sophie Demassey
Enhanced branch and check for pump scheduling in water networks
Workshop on Mixed Integer NonLinear Programming (MINLP'21), online.
Discussion on the implementation of branchandcheck algorithm for MINLP on top of MILP solvers, and generation of valid inequalities based on a strong duality reformulation of the pump scheduling problem.
See the talk online and the slides.
 OE 20

Gratien Bonvin, Sophie Demassey, Andrea Lodi
Pump scheduling in drinking water distribution networks with an LP/NLPbased branch and bound
Optimization and Engineering (2021) 22: 12751313.
Our global search scheme for a generic mixed integer nonconvex optimization model of the pump scheduling problem in water distribution networks follows the line of a "logicbased branchandbenders" approach: we solve a mixed integer convex (OA) relaxation by branchandbound, and attempt to enforce the nonconvex hydraulic constraints at each integer node, then raise nogood cuts when infeasible. This solver performed well on different benchmark sets of the literature, being able to compute good lower bounds and solutions with reasonable gap in reasonable time for networks of reasonable size.
We also propose to specialize the algorithm on networks with only binary on/off controllable devices (e.g. fixedspeed pumps, gate valves), as the subproblem boils down to a simple flow analysis. However, in this case, feasible solutions of the discretized model are getting scarce as the discretization step is getting large. We thus embed a primal matheuristic that attempts to derive practically feasible solutions from the unfeasible integer (relaxed) solutions computed during branchandbound, by slightly adjusting the length of the pumping time windows. Preliminary results presented at ISMP 18 and ROADEF 19.
 INOC 19

Gratien Bonvin, Sophie Demassey
2019
Extended linear formulation of the pump scheduling problem in water distribution networks
Network Optimization INOC (2019): 1318. Open Proceedings. [doi]
9th International Network Optimization Conference, 1214 june 2019, Avignon. [slides]
This approximated noncompact LP model of the pump scheduling problem comes from two observations: (1) the time discretization is an artificial assumption which amplifies the problem combinatorial nature, (2) the filling level variation in the water tanks in one hour has a limited impact on the operation of the pumps. Thus, instead of relying on the binary on/off status of the pumps on every time step, our LP model draws on the activation duration of the pump combinations, whose operational characteristics are estimated, in a preprocessing step, approximately by neglecting the tank level variations. Preprocessing is accelerated using network partition and symmetry arguments. A feasible solution (for the theoretical MINLP model) is then searched in the neighborhood of the approximated LP solution, using a combinatorial Benders decomposition approach. The algorithm is made fully generic for networks with uni/bidirectional pipes, fixed/variablespeed pumps, etc. Also presented at PGMO 19
 WCGO 19

Gratien Bonvin, Sophie Demassey, Welington de Oliveira
2019
Robust design of pumping stations in water distribution networks
Optimization of Complex Systems: Theory, Models, Algorithms and Applications. Advances in Intelligent Systems and Computing 991: 957967. [doi]
6th World Congress on Global Optimization (WCGO'19), 810 july 2019, Metz. [slides]
We embed the scheduling model of AE 16 in a stabilized Benders decomposition approach applied to the problem of sizing the pumps in a water distribution network at minimum investment+operation costs. To reduce the complexity of the operational subproblem, we first decompose the scheduling horizon in representative days. We then relax the discrete and nonconvex components of the hydraulic model. The resulting QCP relaxation quickly computes accurate enough estimates of the operation costs and allows to derive optimality cuts. We also enforce the robustness of the sizing by evaluating its feasibility on stressday scenarios (with peak demand and a pump break). We show how to simplify the MIQCP scheduling model when the objective function is ignored and exhibit a dominance argument to derive logic feasibility cuts.
Preliminary results presented at ROADEF'17.
 GB 18

Gratien Bonvin
2018
Contrôle optimal et dimensionnement des stations de pompage dans les réseaux de distribution d’eau potable
PhD Thesis in Computer Science, PSL, 21 december 2018.
 ISMP 18c

Gratien Bonvin, Sophie Demassey, Andrea Lodi
2019
Global optimization for the pump scheduling problem in drinking water networks
23rd International Symposium on Mathematical Programming (ISMP'18), Bordeaux, France.
The generalization of AE 16 to nonbranched networks with variable speed pumps. Tackling the nonconvex MINLP model with an instantiation of branchandcheck, based on a tight convex relaxation and coupled with a time step adjustementbased primal heuristic. Experimented on 5 different benchmarks of the literature.
Also presented a ROADEF'19; preliminary results at EURO'16 (convex relaxation), ROADEF'17 (time step duration adjustment heuristic) and IFORS'17.
 AE 16

Gratien Bonvin, Sophie Demassey, Claude Le Pape, Nadia Maïzi, Vincent Mazauric, Alfredo Sampiero
2017
A convex mathematical program for pump scheduling in a class of branched drinking water networks
Applied Energy vol. 185, 17021711.
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 nonlinear formulation of the dayahead pump scheduling problem can be made quadratic convex by relaxing the flowhead coupling equalities into inequalities. We provide a deep experimental study on a real usecase showing that this tractable model can be solved when the original nonconvex model cannot.
Presented at ROADEF'16.
 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), 1215 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: 28462851.
7th International Conference on Applied Energy (ICAE'15), 2831 march 2015, Abu Dhabi, UAE.
A summary of Gratien's work during his internship at Schneider Electric on the dayahead Pump Scheduling Problem in a drinking water pumping station. We present a convex Mixed Integer Quadratically Constrained Program and a Benderslike heuristic approach.
models and algorithms in CP
 ACPS 2019

Sophie Demassey
2019
Decompositions and hybridizations in Constraint Programming ACP Summer School, Vienna July 15, 2019. [slides]
A short course on how to combine operational research techniques with constraint programming models, endegenously through global constraints, or exogenously with mathematical programming decomposition methods, for solving combinatorial optimization problems, in both efficient and flexible ways.
 HDR 2017

Sophie Demassey
2017
Compositions et hybridations pour l'Optimisation Combinatoire appliquée HDR Thesis in Computer Science, Université Côte d'Azur, 30 juin 2017. [slides]
mémoire d'habilitation à diriger les recherches défendu le 30 juin 2017, axé sur la problématique de la flexibilité en optimisation combinatoire et la réponse apportée par les méthodes de décomposition hybrides déclaratives, dont notamment les contraintes globales.
 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), 1112 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: 113128.
9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'12), 28 may1 june 2012, Nantes.
We call IntervalAmongs a conjunction of among constraints on interval value domains. We prove that such a conjunction is in P (while the general case is NPhard) using a new vertical "cardinalitybased" 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 allshortestpaths filtering with a (flowbased) GCC. This is compared, both theoretically and empirically, to the standard horizontal "amongbased" decomposition. Finally, we prove that BoxAmongs, i.e. the problem in higher dimensions, remains NPhard.
 RR 11

Gilles Chabert, Frédéric Boyer, Sophie Demassey
2011
MultiAgent ElectroLocation and the Among Constraint
INRIA, Research Report 00598712.
The applicationoriented variant of paper (CPAIOR 12) above. Gilles has exhibited the IntervalAmongs 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 nonoverlapping rectangles
Annals of Operations Research(2011) 184 (1): 2750. [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.
 PGMOCOPI 14

Sophie Demassey, Fabien Hermenier
2014
BtrPlace: Flexible VM Management in Data Centers
Conference on Optimization & Practices in Industry (PGMOCOPI'14), 2831 october 2014, ParisSaclay, France. 3p.
Presentation of the last results todate of BtrPlace.
 CP 11

Fabien Hermenier, Sophie Demassey, Xavier Lorca
2011
BinRepacking Scheduling in Virtualized Datacenters
Lecture Notes in Computer Science (2011) 6876: 2741.
17th International Conference on Principles and Practice of Constraint Programming (CP'11), application track, 1316 september 2011, Perugia, Italy.
[doi, slides, annex]
Take an infashion 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), 1013 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 multiweighted automaton from a given set of soft scheduling rules, and then a CP model based on one MulticostRegular 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 1101INFO.
We present an algorithm for intersecting weighted automata as a multiweighted 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 MulticostRegular 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 multicostregular 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), 2731 may 2009, Pittsburgh, USA.
We introduce MulticostRegular, an extension of the CostRegular 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 NPcomplete. We present a lagrangianbased filtering algorithm for this constraint.
Preliminary results presented at ROADEF'09 (lagrangianbased filtering).
 JFPC 09

Julien Menana, Sophie Demassey
2009
Séquencer et compter avec la contrainte multicostregular Proc. p. 125134.
5èmes Journées Francophones de Programmation par Contraintes (JFPC'09), 35 june 2009, Orléans, France.
 Constraints 06

Sophie Demassey, Gilles Pesant, LouisMartin Rousseau
2006
A CostRegular 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 variablevalue selection strategy coupled to the costregular constraint, with a heuristic and a branching strategy for the CPbased column generation model of the Employee Timetabling Problem, and with experiments on two complex realcase studies.
 CPAIOR 05

Sophie Demassey, Gilles Pesant, LouisMartin 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 CostRegular, 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.
Preliminary results presented at JOPT'05.
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), 2527 july 2011, Udine, Italy.
To speed up an ACO procedure on largesize 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.
 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), 2226 may 2011, Lille, France.
We describe our implementation of a CGACO algorithm for the railway infrastructure capacity problem in the RECIFE software.
Preliminary results presented at ROADEF'10 (column generation).
 ROADEF 09a

Aurélien Merel, Xavier Gandibleux, Sophie Demassey, Richard Lusby
2009
An improved upper bound for the railway infrastructure capacity problem on the PierrefitteGonesse junction Long paper in Proc. p. 6276, ISBN 2905267658.
10ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'09), 1112 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
 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)
 ISTE 08

Christian Artigues, Sophie Demassey, Emmanuel Néron (eds.)
2008
ResourceConstrained Project Scheduling: models, algorithms, extensions and applications
ISTE/Wiley, ISBN 9781848210349.
 ISTE 08b

Sophie Demassey
2008
Mathematical Programming Formulations and Lower Bounds for the RCPSP
Chapter 3 in ResourceConstrained Project Scheduling: models, algorithms, extensions and applications, C. Artigues, S. Demassey, E. Néron (eds.), ISTE/Wiley, ISBN 9781848210349.
 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 9780387336435, 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 resourceconstrained 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 continoustime and the timeindexed MIP models. In our experiments, we observe the capacity of the cuts to improve the lower bounds computed by the LPrelaxations in constructive and destructive (progressive UB rejection) ways.
Preliminary results presented at ISMP'00, FRANCORO'01, OR'02, ROADEF'02, CIRO'02.
 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 9782553011450.
 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), 1416 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 CPbased 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 relaxationbased lower bounds for the RCPSP
9th international workshop on project management and scheduling (PMS'04), 2628 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 timedependent costs but no resource constraints, which amounts to a minimum cut problem solvable in polynomial time.
 CPAIOR 02

Sophie Demassey, Christian Artigues, Philippe Michelon
2002
A hybrid constraint propagationcutting plane algorithm for the RCPSP
4th International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'02), 2527 march 2002, Le Croisic, France, Proc. p. 321331.
Preliminary study for IJOC'05: CPbased valid linear inequalities for the timeindexed MIP formulation of the RCPSP.
 Cosolv 01

Sophie Demassey, Christian Artigues, Philippe Michelon
2001
Comparing lower bounds for the RCPSP under a same hybrid constraintlinear programming approach Proc. p. 109123.
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.
 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 AixMarseille 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): 2162. [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: 5974.
12th International Conference on Principles and Practice of Constraint Programming (CP'06), 2429 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 1to1 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), 79 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), 1822 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), 2426 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), 2831 october 2003, Tours.
Resolution Search is a complete nontree 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 almostunexplored 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 AixMarseille I, 1998.