-
Notifications
You must be signed in to change notification settings - Fork 3
/
biblio.html
executable file
·706 lines (622 loc) · 58.6 KB
/
biblio.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Window-target" content="_parent" />
<meta name="author" content="Sophie Demassey" />
<meta name="keywords" content="demassey" />
<title>Sophie Demassey</title>
<link type="text/css" rel="stylesheet" href="stylesheets/biblio.css">
<link type="text/css" rel="stylesheet" href="stylesheets/styles.css">
<link type="text/css" rel="stylesheet" href="stylesheets/pygment_trac.css">
<script type="text/javascript" src="javascripts/scale.fix.js"></script>
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<!--[if lt IE 9]><script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script><![endif]-->
</head>
<body><div class="wrapper">
<header>
<h1 class="header">biblio</h1>
<p class="header">Sophie Demassey</p>
<ul>
<li><a href="index.html"><span class="material-symbols-outlined">undo</span> home</a></li>
<li><a href="http://scholar.google.com/citations?user=aLalTi4AAAAJ"><span class="material-symbols-outlined">logout</span> scholar</a></li>
<li><a href="https://cv.archives-ouvertes.fr/sophie-demassey"><span class="material-symbols-outlined">logout</span> hal</a></li></ul>
<a href="http://xkcd.com/664/"><img height="114" width="170" src="images/academia.png" alt="xkcd"/></a>
<!-- a href="http://www.sciencecartoonsplus.com/"><img height="224" width="200" src="images/explicit.png" alt="sharris"/></a -->
</header>
<section>
<h1>thematic bibliography</h1>
<ul>
<li><a href="#dco">nonsmooth nonconvex optimization</a> (2019-)</li>
<li><a href="#dr">scheduling and planning in power systems</a> (2015-)</li>
<li><a href="#water">MINLP for water distribution systems</a> (2014-)</li>
<li><a href="#cp">models and algorithms in CP</a> (2010-)</li>
<li><a href="#dc">flexible datacenter resource management with CP</a> (2009-)</li>
<li><a href="#auto">automata and optimization constraints for rostering (NRP)</a> (2005-2012)</li>
<li><a href="#rail">column generation for railway infrastructure capacity (SPP)</a> (2009-2012)</li>
<li><a href="#rcpsp">ILP model decompositions with CP-based processing for project scheduling (RCPSP)</a> (2000-2008)</li>
<li><a href="#gccat">systematic reformulation of global constraints</a> (2006-2007)</li>
<li><a href="#rs">resolution search for the RCPSP</a> (2003-2006)</li>
<li><a href="#comma">commutative algebra</a> (1997-1998)</dd>
</ul>
<h2 id="dco">nonsmooth nonconvex optimization</h2><dl>
<dt><a href="https://optimization-online.org/?p=21655" name="pjo24">PJO24</a></dt>
<dd>
<span class="author">Ksenia Syrtseva, Welington de Oliveira, Sophie Demassey, Wim van Ackooij</span>
<span class="title"><a href="https://optimization-online.org/?p=21655">Minimizing the difference of convex and weakly convex functions via bundle method</a></span>
Pacific Journal of Optimization (2024) In honor of the 75th Birthday of Professor Masao Fukushima.
<span class="abs">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.</span>
</dd>
<dt><a href="https://rdcu.be/cbe28" name="coa20">COA 20</a></dt>
<dd>
<span class="author">Wim van Ackooij, Sophie Demassey, Paul Javal, Hugo Morais, Welington de Oliveira, Bhargav Swaminathan</span>
<span class="title"><a href="https://rdcu.be/cbe28">A bundle method for nonsmooth DC programming with application to chance-constrained problems</a></span>
Computational Optimization and Applications (2021) 78: 451-490.
<span class="abs">We address nonsmooth nonconvex problems with objective and constraints defined by Difference-of-Convex (aka DC, aka convex-concave) functions. The DC constraints are handled through an improvement function instead of penalization or linearization. The resulting convexly-constrained DC program is solved with a proximal bundle method, leading to a critical point of the original DC-constrained program and even a B-stationary 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 chance-constrained optimization problems.</span>
</dd>
</dl>
<h2 id="dr">scheduling and planning in power systems</h2><dl>
<dt><a href="https://www.sciencedirect.com/science/article/pii/S2352467723001765" name="segan23">SEGAN23</a></dt>
<dd>
<span class="author">Ksenia Syrtseva, Welington de Oliveira, Sophie Demassey, Hugo Morais, Paul Javal, Bhargav Swaminathan</span>
<span class="title"><a href="https://www.sciencedirect.com/science/article/pii/S2352467723001765">Difference-of-Convex Approach to Chance-Constrained Optimal Power Flow modelling the DSO Power Modulation Lever for Distribution Networks</a></span>
Sustainable Energy, Grids and Networks 36 (2023) article 101168
<span class="abs">We address the joint chance-constrained 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 <a href="coa20">[COA20]</a>. The approach yields a natural and embarrassingly parallelizable scenario decomposition.</span>
</dd>
<dt><a name="roadef20b">ROADEF 20</a></dt>
<dd>
<span class="author">Arnold N'Goran, Sophie Demassey</span>
<span class="title">Engagement optimal de production d’une centrale solaire photovoltaique</span>
21ème congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision (<span class="conf">ROADEF'20</span>), Montpellier, France.
<span class="abs">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.</span>
</dd>
<dt><a href="https://hal-mines-paristech.archives-ouvertes.fr/hal-02318181/document" name="isgt19">ISGT 19</a></dt>
<dd>
<span class="author">Arnold N'Goran, Bruno Daugrois, Marc Lotteau, Sophie Demassey</span>
<span class="title"><a href="https://hal-mines-paristech.archives-ouvertes.fr/hal-02318181/document">Optimal engagement and operation of a grid-connected PV/battery system</a></span>
2019 IEEE PES Innovative Smart Grid Technologies Europe (<span class="conf">ISGT-Europe'19</span>), Bucharest, Romania.
<span class="abs">An experimental comparison between a coarse-grained MIQP model solved at optimality with a fine-grained numerical model optimized by a genetic algorithm to control a grid-connected 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.</span> Preliminary results presented at <span class="conf">Roadef'18</span>.
</dd>
<dt><a href="https://hal.archives-ouvertes.fr/hal-02318615/document" name="icae19">ICAE 19</a></dt>
<dd>
<span class="author">Gildas Siggini, Edi Assoumou, Sophie Demassey</span>
<span class="title"><a href="https://hal.archives-ouvertes.fr/hal-02318615/document">Investment choices and capacities at risk in decarbonizing the EU electric system</a></span>
11th International Conference on Applied Energy (<span class="conf">ICAE'19</span>), Västerås, Sweden.
<span class="abs">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.</span>
</dd>
<dt><a name="pgmo19a">PGMO 19a</a></dt>
<dd>
<span class="author">Paul Javal, Wim van Ackooij, Sophie Demassey, Welington de Oliveira</span>
<span class="title">A Difference-of-Convex Approach for Optimal Power Flow Problems with Probability Constraints</span>
Annual meeting of the Gaspard Monge Program for Optimization and Operations Research and their interactions with Data Sciences (<span class="conf">PGMO'19</span>), Paris Saclay, France.
<span class="abs">Modelling the optimal power flow with probability constraints as a DC-constrained DC program.</span> Also presented at <span class="conf">PID'19</span>, <span class="conf">ROADEF'20</span>.
</dd>
<dt><a name="ismp18a">ISMP 18a</a></dt>
<dd>
<span class="author">Sophie Demassey, Edi Assoumou, Welington De Oliveira</span>
<span class="title">Robust optimisation of storage in a power generation expansion planning problem</span>
23rd International Symposium on Mathematical Programming (<span class="conf">ISMP'18</span>), Bordeaux, France.
<span class="abs">Coupling a long-term power generation expansion planning model with a mid-term storage optimization model to handle uncertainties in renewable production.</span>
Also presented at <span class="conf">PGMO days 18</span>.
</dd>
<dt><a name="ismp18b">ISMP 18b</a></dt>
<dd>
<span class="author">Paul Javal, Welington de Oliveira, Hugo Morais, Wim van Ackooij, Sophie Demassey</span>
<span class="title">Modelling distributed energy resources uncertainties in short-term operational planning optimisation</span>
23rd International Symposium on Mathematical Programming (<span class="conf">ISMP'18</span>), Bordeaux, France.
<span class="abs">Identifying the new levers to operate when controlling the power distribution network.</span>
</dd>
<dt><a href="https://fhermeni.github.io/pubs/hermenier-europar17.pdf">EuroPar 17</a></dt>
<dd>
<span class="author">Fabien Hermenier, Giovanni Giuliani, Andrea Milani, Sophie Demassey</span>
<span class="year">2017</span>
<span class="title"><a href="https://fhermeni.github.io/pubs/hermenier-europar17.pdf">Scaling Energy Adaptive Applications for Sustainable Profitability</a></span>
<span class="journal">Lecture Notes in Computer Science</span> (2017) 10417: 23-35.
<span class="conf">Euro-Par'17</span> Parallel Processing: 23rd International Conference, Santiago de Compostella, Spain.</span>
<span class="abs">Carver is a CP-based solution developed in the context of the european project DC4Cities to orchestrate energy-adaptive applications in datacenters, according to performance and environmental preferences, given forecasts of the renewable energy production.</span>
</dd>
<dt><a name="euro16b">EURO 16b</a></dt>
<dd>
<span class="author">Aurélien Havel, Sophie Demassey</span>
<span class="year">2016</span>
<span class="title">Robust optimisation for a smart grid</span>
28th European Conference on Operational Research (<span class="conf">EURO'16</span>), 3-6 july 2016, Poznan.
<span class="abs">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.</span>
</dd>
</dl>
<h2 id="water">MINLP for water distribution systems</h2><dl>
<dt><a href="https://minesparis-psl.hal.science/hal-04506597v1/file/isco24-demassey.pdf" name="isco24">ISCO 24</a></dt>
<dd>
<span class="author">Sophie Demassey, Valentina Sessa, Amirhossein Tavakoli</span>
<span class="year">2024</span>
<span class="title"><a href="https://minesparis-psl.hal.science/hal-04506597v1/file/isco24-demassey.pdf">Alternating direction method and deep learning for discrete control with storage</a></span>
<span class="journal">Lecture Notes in Computer Science</span> (2017) 14594: 85-96.
<span class="conf">ISCO'24</span> Combinatorial Optimization</span> La Laguna, Tenerife, Spain
<span class="abs">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 ADM-like 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 multi-start ADM, generalization/scaling in Deep Learning. <a href="art/demassey24isco.pdf">Slides</a> at <span class="conf">ISCO'24</span> and previous talks at <span class="conf">Roadef'24</span>: about <a href="art/demassey24roadef-dl.pdf">deep learning</a> and <a href="art/demassey24roadef-adm.pdf">adm</a>.
</dd>
<dt><a href="https://cloud.minesparis.psl.eu/index.php/s/y55q0zDX6Tzjvof" name="amir23">Amir 23</a></dt>
<dd>
<span class="author">Amirhossein Tavakoli</span>
<span class="title"><a href="https://cloud.minesparis.psl.eu/index.php/s/y55q0zDX6Tzjvof" name="amir23">Combinatorial Optimization and deep learning for energy-efficient water distribution networks</a></span>
PhD thesis directed with Valentina Sessa and defended 20/12/2023, Sophia-Antipolis.
</dd>
<dt><a href="art/demassey23as.pdf" name="pmnl23">ETSAP 23</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="title">Combinatorial Optimization for Water Management</span>
Joint autumn School 2023 of IEA-ETSAP and the Transition Institute 1.5, Sophia-Antipolis, nov 2023.
<span class="abs">Very short introduction to combinatorial optimization and overview of applications in water management. See the <a href="art/demassey23as.pdf">slides</a></span>.
</dd>
<dt><a href="art/demassey23nets.pdf" name="nets23">OR 23</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="title">Monotropic bilevel programming: duality in hydraulic network optimization</span>
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.
<span class="abs">Slightly augmented version of <a href="pmnl23">PMNL 23</a> with a focus on the water network optimization problems.</span> See the <a href="art/demassey23nets.pdf">slides</a>.
</dd>
<dt><a href="art/demassey23pmnl.pdf" name="pmnl23">PMNL 23</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="title">Strong duality reformulation for bilevel optimization over nonlinear flow networks</span>
Day of the working group on nonlinear programming PMNL of the CNRS research network on Operational Research GdR RO, Paris 23/06/2023.
<span class="abs">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.</span> See the <a href="art/demassey23pmnl.pdf">slides</a>. Preliminary results presented at <span class="conf">Roadef 23, PGMO 21</span>.
</dd>
<dt><a href="https://hal.science/hal-03934746v1/file/Demassey_253_strengthening%20mathematical%20model%20for%20pump%20scheduling%20in%20water%20distribution.pdf" name="icae22">ICAE 22</a></dt>
<dd>
<span class="author">Amirhossein Tavakoli, Valentina Sessa, Sophie Demassey</span>
<span class="title"><a href="https://hal.science/hal-03934746v1/file/Demassey_253_strengthening%20mathematical%20model%20for%20pump%20scheduling%20in%20water%20distribution.pdf">Strengthening mathematical models for pump scheduling in water distribution</a></span>
14th International Conference on Applied Energy (<span class="conf">ICAE'22</span>), Bochum, Germany.
<span class="abs">Intensive OBBT (optimization-based bound tightening) preprocessing for the nonconvex MINLP model of the pump scheduling problem to speed up the algorithm proposed in <a href="oe20">OE 20</a>. 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</span>. Also presented by Amir at <span class="conf">Roadef 23, Sophia Summit 23</span>.
</dd>
<dt><a href="art/demassey21minlp.pdf" name="minlp21">MINLP 21</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="title">Enhanced branch and check for pump scheduling in water networks</span>
Workshop on Mixed Integer NonLinear Programming (<span class="conf">MINLP'21</span>), online.
<span class="abs">Discussion on the implementation of branch-and-check algorithm for MINLP on top of MILP solvers, and generation of valid inequalities based on a strong duality reformulation of the pump scheduling problem.</span>
See the <a href="https://www.youtube.com/watch?v=7g17tYSSlMw">talk</a> online and the <a href="art/demassey21minlp.pdf">slides</a>.
</dd>
<!-- dt><a href="http://www.optimization-online.org/DB_HTML/2020/02/7621.html" name="lpnlp">OO 19</a></dt -->
<dt><a href="art/bonvin20opteng.pdf" name="oe20">OE 20</a></dt>
<dd>
<span class="author">Gratien Bonvin, Sophie Demassey, Andrea Lodi</span>
<span class="title"><a href="art/bonvin20opteng.pdf">Pump scheduling in drinking water distribution networks with an LP/NLP-based branch and bound</a></span>
Optimization and Engineering (2021) 22: 1275-1313.
<span class="abs">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 "logic-based branch-and-benders" approach: we solve a mixed integer convex (OA) relaxation by branch-and-bound, 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. fixed-speed 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 branch-and-bound, by slightly adjusting the length of the pumping time windows.</span> Preliminary results presented at <span class="conf">ISMP 18</span> and <span class="conf">ROADEF 19</span>.
</dd>
<dt><a href="https://openproceedings.org/2019/conf/inoc/INOC_2019_paper_10.pdf" name="inoc19">INOC 19</a></dt>
<dd>
<span class="author">Gratien Bonvin, Sophie Demassey</span>
<span class="year">2019</span>
<span class="title"><a href="art/bonvin19inoc.pdf">Extended linear formulation of the pump scheduling problem in water distribution networks</a></span>
<span class="journal">Network Optimization</span> INOC (2019): 13-18. Open Proceedings. [<a href="http://dx.doi.org/10.5441/002/inoc.2019.04">doi</a>]
9th International Network Optimization Conference, 12-14 june 2019, Avignon. [<a href="art/bonvin19inoc-slidesdemassey.pdf">slides</a>]
<span class="abs">This approximated non-compact 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/variable-speed pumps, etc.</span> Also presented at <span class="conf">PGMO 19</span>
</dd>
<dt><a href="art/bonvin19wcgo.pdf" name="wcgo19">WCGO 19</a></dt>
<dd>
<span class="author">Gratien Bonvin, Sophie Demassey, Welington de Oliveira</span>
<span class="year">2019</span>
<span class="title"><a href="art/bonvin19wcgo.pdf">Robust design of pumping stations in water distribution networks</a></span>
<span class="journal">Optimization of Complex Systems: Theory, Models, Algorithms and Applications</span>. Advances in Intelligent Systems and Computing 991: 957-967. [<a href="https://doi.org/10.1007/978-3-030-21803-4_95">doi</a>]
6th World Congress on Global Optimization (<span class="conf">WCGO'19</span>), 8-10 july 2019, Metz. [<a href="art/bonvin19wcgo-slidesdemassey.pdf">slides</a>]
<span class="abs">We embed the scheduling model of <a href="ae16">AE 16</a> 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 non-convex 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 stress-day 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.</span>
Preliminary results presented at <span class="conf">ROADEF'17</span>.
</dd>
<dt><a href="art/bonvin18phdfinal.pdf" name="phd18">GB 18</a></dt>
<dd>
<span class="author">Gratien Bonvin</span>
<span class="year">2018</span>
<span class="title"><a href="art/bonvin18phdfinal.pdf">Contrôle optimal et dimensionnement des stations de pompage dans les réseaux de distribution d’eau potable</a></span>
PhD Thesis in Computer Science, PSL, 21 december 2018.
</dd>
<dt><a name="ismp18c">ISMP 18c</a></dt>
<dd>
<span class="author">Gratien Bonvin, Sophie Demassey, Andrea Lodi</span>
<span class="year">2019</span>
<span class="title">Global optimization for the pump scheduling problem in drinking water networks</span>
23rd International Symposium on Mathematical Programming (<span class="conf">ISMP'18</span>), Bordeaux, France.
<span class="abs">The generalization of <a href="ae16">AE 16</a> to non-branched networks with variable speed pumps. Tackling the non-convex MINLP model with an instantiation of branch-and-check, based on a tight convex relaxation and coupled with a time step adjustement-based primal heuristic. Experimented on 5 different benchmarks of the literature.</span>
Also presented a <span class="conf">ROADEF'19</span>; preliminary results at <span class="conf">EURO'16</span> (convex relaxation), <span class="conf">ROADEF'17</span> (time step duration adjustment heuristic) and <span class="conf">IFORS'17</span>.
</dd>
<dt><a href="art/bonvin16ae.pdf" name="ae16">AE 16</a></dt>
<dd>
<span class="author">Gratien Bonvin, Sophie Demassey, Claude Le Pape, Nadia Maïzi, Vincent Mazauric, Alfredo Sampiero</span>
<span class="year">2017</span>
<span class="title"><a href="art/bonvin16ae.pdf">A convex mathematical program for pump scheduling in a class of branched drinking water networks</a></span>
<span class="journal">Applied Energy</span> vol. 185, 1702-1711.
<span class="abs">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 quadratic convex by relaxing the flow-head coupling equalities into inequalities. We provide a deep experimental study on a real use-case showing that this tractable model can be solved when the original non-convex model cannot.</span>
Presented at <span class="conf">ROADEF'16</span>.
</dd>
<dt><a name="euro15">EURO 15</a></dt>
<dd>
<span class="author">Gratien Bonvin, Sophie Demassey</span>
<span class="year">2015</span>
<span class="title">Energy efficiency in water supply systems : variable speed drives vs pumping scheduling</span>
27th European Conference on Operational Research (<span class="conf">EURO'15</span>), 12-15 july 2015, Glasgow.
<span class="abs">Where we compare the opportunities of installing variable speed drives vs. optimizing the pump schedule in a drinking water pumping station.</span>
</dd>
<dt><a href="https://hal-mines-paristech.archives-ouvertes.fr/hal-01158960" name="icae15">ICAE 15</a></dt>
<dd>
<span class="author">Gratien Bonvin, Alfredo Samperio, Claude Le Pape, Vincent Mazauric, Sophie Demassey, Nadia Maïzi</span>
<span class="year">2015</span>
<span class="title"><a href="https://hal-mines-paristech.archives-ouvertes.fr/hal-01158960">A heuristic approach to the water networks pumping scheduling issue</a></span>
<span class="journal">Energy Procedia</span> (2015) 75: 2846-2851.
7th International Conference on Applied Energy (<span class="conf">ICAE'15</span>), 28-31 march 2015, Abu Dhabi, UAE.
<span class="abs">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.</span>
</dd>
</dl>
<h2 id="cp">models and algorithms in CP</h2><dl>
<dt><a href="art/acpsummer19decomposition.pdf">ACPS 2019</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">2019</span>
<span class="title"><a href="art/acpsummer19decomposition.pdf">Decompositions and hybridizations in Constraint Programming</a></span> <a href="https://school.a4cp.org/summer2019/"><strong>ACP Summer School</strong></a>, Vienna July 1-5, 2019. [<a href="art/demassey17hdr-slides.pdf">slides</a>]
<span class="abs">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.</span>
</dd>
<dt><a href="art/demassey17hdr.pdf">HDR 2017</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">2017</span>
<span class="title"><a href="art/demassey17hdr.pdf">Compositions et hybridations pour l'Optimisation Combinatoire appliquée</a></span> HDR Thesis in Computer Science, Université Côte d'Azur, 30 juin 2017. [<a href="art/demassey17hdr-slides.pdf">slides</a>]
<span class="abs">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.</span>
</dd>
<dt><a href="https://hal.archives-ouvertes.fr/hal-01109049" name="roadef15">ROADEF 15</a></dt>
<dd>
<span class="author">Sophie Demassey, Dominique Feillet</span>
<span class="year">2015</span>
<span class="title"><a href="https://hal.archives-ouvertes.fr/hal-01109049">Hybridation de programmation linéaire et de programmation par contraintes pour le problème de déplacement de conteneurs</a></span>
16ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (<span class="conf">ROADEF'15</span>), 11-12 february 2015, Marseille, France.
<span class="abs">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.</span>
</dd>
<dt><a href="http://hal.inria.fr/hal-00760044" name="cpaior12">CPAIOR 12</a></dt>
<dd>
<span class="author">Gilles Chabert, Sophie Demassey</span>
<span class="year">2012</span>
<span class="title"><a href="http://hal.inria.fr/hal-00760044">The Conjunction of Interval Among Constraints</a></span>
<span class="journal">Lecture Notes in Computer Science</span> (2012) 7298: 113-128.
9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (<span class="conf">CPAIOR'12</span>), 28 may-1 june 2012, Nantes.
<span class="abs">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.</span>
</dd>
<dt><a href="http://hal.inria.fr/inria-00598712" name="RR11">RR 11</a></dt>
<dd>
<span class="author">Gilles Chabert, Frédéric Boyer, Sophie Demassey</span>
<span class="year">2011</span>
<span class="title"><a href="http://hal.inria.fr/inria-00598712">Multi-Agent Electro-Location and the Among Constraint</a></span>
INRIA, Research Report 00598712.
<span class="abs">The application-oriented variant of paper (<a href="#cpaior12">CPAIOR 12</a>) 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.</span>
</dd>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00485563" name="aor10">AOR 10</a></dt>
<dd>
<span class="author">Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Emmanuel Poder</span>
<span class="year">2010</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00485563">New filtering for the cumulative constraint in the context of non-overlapping rectangles</a></span>
<span class="journal">Annals of Operations Research</span>(2011) 184 (1): 27-50. [<a href="http://dx.doi.org/10.1007/s10479-010-0731-0">doi</a>]
<span class="abs">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 <a href="gccat/gccat/Cgeost.html">geost</a>.</span>
</dd>
</dl>
<h2 id="dc">flexible datacenter resource management with CP</h2><dl>
<dt><a href="http://www.btrplace.org">BtrPlace</a><dt>
<dd>
<span class="author">
BtrPlace is an open source datacenter resource manager based on the Constraint Programming solver <a href="http://www.choco-solver.org/">Choco</a>. It is mainly developed by <a href="https://fhermeni.github.io/">Fabien Hermenier</a> at University of Nice</span>
<span class="abs">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 <a href="http://www.btrplace.org">website</a> as well as the documentation, the research papers, and a sandbox to play with it.</span>
</dd>
<dt><a href="art/demassey15btrp.pdf">Packing 15</a></dt>
<dd>
<span class="author">Sophie Demassey, Fabien Hermenier, Vincent Kherbache</span>
<span class="year">2015</span>
<span class="title"><a href="art/demassey15btrp.pdf">Dynamic Packing with Side Constraints for Datacenter Resource Management</a></span>
<span class="journal">in G. Fasano and J.D. Pintér. eds, <a href="http://www.springer.com/gp/book/9783319188980">Optimized Packings and Their Applications</a>, <i>Springer Optimization and Its Applications</i> vol. 105, Springer, New York.</span>
<span class="abs">This chapter describes the variant of the vector packing problem considered in <a href="http://www.btrplace.org">BtrPlace</a> in the context of datacenter resource management, giving an insight into its dynamic and heterogeneous nature.</span>
</dd>
<dt><a href="art/demassey14pgmo.pdf">PGMO-COPI 14</a></dt>
<dd>
<span class="author">Sophie Demassey, Fabien Hermenier</span>
<span class="year">2014</span>
<span class="title"><a href="art/demassey14pgmo.pdf">BtrPlace: Flexible VM Management in Data Centers</a></span>
<span class="journal">Conference on Optimization & Practices in Industry (PGMO-COPI'14), 28-31 october 2014, Paris-Saclay, France. 3p.</span>
<span class="abs">Presentation of the last results todate of BtrPlace.</span>
</dd>
<dt><a href="https://fhermeni.github.io/pubs/hermenier-etal-cp2011.pdf" name="cp11">CP 11</a></dt>
<dd>
<span class="author">Fabien Hermenier, Sophie Demassey, Xavier Lorca</span>
<span class="year">2011</span>
<span class="title"><a href="https://fhermeni.github.io/pubs/hermenier-etal-cp2011.pdf">Bin-Repacking Scheduling in Virtualized Datacenters</a></span>
<span class="journal">Lecture Notes in Computer Science</span> (2011) 6876: 27-41.
17th International Conference on Principles and Practice of Constraint Programming (<span class="conf">CP'11</span>), application track, 13-16 september 2011, Perugia, Italy.
[<a href="http://dx.doi.org/10.1007/978-3-642-23786-7_5">doi</a>, <a href="https://fhermeni.github.io/pubs/hermenier-etal-cp2011-slides.pdf">slides</a>, <a href="https://fhermeni.github.io/pubs/hermenier-etal-cp2011-update.pdf">annex</a>]
<span class="abs">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 <a href="http://www.choco-solver.org/">Choco</a> in Entropy the former version of <a href="http://btrplace.org">BtrPlace</a>, 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 <a href="https://fhermeni.github.io/pubs/hermenier-etal-cp2011-update.pdf">this annex report (sep 26, 2011)</a>.</span>
</dd>
</dl>
<h2 id="auto">automata and optimization constraints for rostering</h2><dl>
<dt><a href="art/demassey14cmp.pdf" name="CMP14">seminar CMP 14</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">2014</span>
<span class="title"><a href="art/demassey14cmp.pdf">Flexible Optimization: Nurse Scheduling with Constraint Programming and Automata</a></span>
Invited Seminar at CMP, École des Mines de Saint-Étienne, 3 july 2014.
</dd>
<dt><a href="http://tel.archives-ouvertes.fr/tel-00785838" name="phd11">Julien's PhD</a></dt>
<dd>
<span class="author">Julien Menana</span>
<span class="year">2011</span>
<span class="title"><a href="http://tel.archives-ouvertes.fr/tel-00785838">Automates et programmation par contraintes pour la planification de personnel</a></span>
PhD Thesis in Computer Science, University of Nantes, 28 october 2011.
</dd>
<dt><a href="art/menana10patat.pdf" name="patat10">PATAT 10</a></dt>
<dd>
<span class="author">Julien Menana, Sophie Demassey</span>
<span class="year">2010</span>
<span class="title"><a href="art/menana10patat.pdf">Weighted Automata, Constraint Programming, and Large Neighborhood Search</a></span>
Nurse Rostering Competition at the 8th International Conference for the Practice and Theory of Automated Timetabling (<span class="conf">PATAT'10</span>), 10-13 august 2010, Belfast, Ireland.
<span class="abs">We propose an automated planner, implemented with <a href="http://www.choco-solver.org/">Choco</a>, 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.</span>
</dd>
<dt><a href="art/menana10rr.pdf" name="RR10">RR 10</a></dt>
<dd>
<span class="author">Julien Menana, Sophie Demassey, Narendra Jussien</span>
<span class="year">2010</span>
<span class="title"><a href="art/menana10rr.pdf">Modélisation et optimisation des préférences en planification de personnel</a></span>
École des Mines de Nantes, Research Report 11-01-INFO.<br/>
<span class="abs">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.</span>
</dd>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00394434" name="cpaior09">CPAIOR 09</a></dt>
<dd>
<span class="author">Julien Menana, Sophie Demassey</span>
<span class="year">2009</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00394434">Sequencing and counting with the <tt>multicost-regular</tt> constraint</a></span>
<span class="journal">Lecture Notes in Computer Science</span> (2009) 5547: 178 - 192.
6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (<span class="conf">CPAIOR'09</span>), 27-31 may 2009, Pittsburgh, USA.
<span class="abs">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.</span>
Preliminary results presented at <span class="conf">ROADEF'09</span> (lagrangian-based filtering).
</dd>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00387821" name="jfpc09">JFPC 09</a></dt>
<dd class="rgb">
<span class="author">Julien Menana, Sophie Demassey</span>
<span class="year">2009</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00387821">Séquencer et compter avec la contrainte multicost-regular</a></span> Proc. p. 125-134.
5èmes Journées Francophones de Programmation par Contraintes (<span class="conf">JFPC'09</span>), 3-5 june 2009, Orléans, France.
</dd>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00293562" name="ct06">Constraints 06</a></dt>
<dd>
<span class="author">Sophie Demassey, Gilles Pesant, Louis-Martin Rousseau</span>
<span class="year">2006</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00293562">A <tt>Cost-Regular</tt> based Hybrid Column Generation Approach</a></span>
<span class="journal">Constraints</span>(2006) 11 (4) : 315 - 333. [<a href="http://dx.doi.org/10.1007/s10601-006-9003-7">doi</a>]
<span class="abs">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.</span>
</dd>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00293565" name="cpaior05">CPAIOR 05</a></dt>
<dd>
<span class="author">Sophie Demassey, Gilles Pesant, Louis-Martin Rousseau</span>
<span class="year">2005</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00293565">Constraint programming based column generation for employee timetabling</a></span>
<span class="journal">Lecture Notes in Computer Science</span> (2005) 3524: 140 - 154.
2nd International Conference on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (<span class="conf">CPAIOR'05</span>), 30 may - 2 june 2005, Prague, Czech Republic.
<span class="abs">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.</span>
Preliminary results presented at <span class="conf">JOPT'05</span>.
</dl>
<h2 id="rail">column generation for railway infrastructure capacity</h2><dl>
<dt><a href="https://www.theses.fr/169906213" name="phd12">Aurélien's PhD</a></dt>
<dd>
<span class="author">Aurélien Merel</span>
<span class="year">2012</span>
<span class="title"><a href="https://www.theses.fr/169906213">Évaluation biobjectif de la capacité d'infrastructures ferroviaires par génération de colonnes hybride</a></span>
PhD Thesis in Computer Science, University of Nantes, 31 october 2012.
</dd>
<dt><a href="art/merel-al-MIC-2011.pdf" name="mic11">MIC 11</a></dt>
<dd>
<span class="author">Aurélien Merel, Xavier Gandibleux, Sophie Demassey</span>
<span class="year">2011</span>
<span class="title"><a href="art/merel-al-MIC-2011.pdf">A collaborative combination between column generation and ant colony optimization for solving set packing problems</a></span>
9th Metaheuristics International Conference (<span class="conf">MIC'11</span>), 25-27 july 2011, Udine, Italy.
<span class="abs">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.</span>
</dd>
<dt><a href="art/merel-al-WCRR-2011.pdf" name="wcrr11">WCRR 11</a></dt>
<dd>
<span class="author">Aurélien Merel, Xavier Gandibleux, Sophie Demassey</span>
<span class="year">2011</span>
<span class="title"><a href="art/merel-al-WCRR-2011.pdf">Towards a Realistic Evaluation of Railway Infrastructure Capacity</a></span>
9th World Congress on Railway Research (<span class="conf">WCRR'11</span>), 22-26 may 2011, Lille, France.
<span class="abs">We describe our implementation of a CG-ACO algorithm for the railway infrastructure capacity problem in the <a href="http://xgandibleux.free.fr/RECIFE/index.html">RECIFE</a> software.</span>
Preliminary results presented at <span class="conf">ROADEF'10</span> (column generation).
</dd>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00466933" name="roadef09a">ROADEF 09a</a></dt>
<dd>
<span class="author">Aurélien Merel, Xavier Gandibleux, Sophie Demassey, Richard Lusby</span>
<span class="year">2009</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00466933">An improved upper bound for the railway infrastructure capacity problem on the Pierrefitte-Gonesse junction</a></span> 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 (<span class="conf">ROADEF'09</span>), 11-12 february 2009, Nancy, France.
<span class="abs">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.</span>
</dd>
</dl>
<h2 id="rcpsp">ILP decompositions and CP for the RCPSP</h2><dl>
<dt><a href="art/demassey03phd.pdf" name="phd03">PhD 03</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">2003</span>
<span class="title"><a href="art/demassey03phd.pdf">Méthodes hybrides de programmation par contraintes et programmation linéaire pour le problème d'ordonnancement de projet à contraintes de ressources</a></span>
PhD Thesis in Computer Science - Combinatorial Optimization, University of Avignon, 18 december 2003.<br/>
download: <a href="art/demassey03phd.pdf">.pdf</a> (french, hyperref, 1.2 MB), <a href="art/demassey03phd.ps.gz">.ps.gz</a> (french, 792 KB)
</dd>
<dt><a class="nolink" name="iste08">ISTE 08</a></dt>
<dd>
<span class="author">Christian Artigues, Sophie Demassey, Emmanuel Néron (eds.)</span>
<span class="year">2008</span>
<span class="title"><a href="http://www.iste.co.uk/index.php?p=a&ACTION=View&id=172">Resource-Constrained Project Scheduling: models, algorithms, extensions and applications</a></span>
ISTE/Wiley, ISBN 978-1-84821-034-9.
</dd>
<dt><a href="http://www.iste.co.uk/index.php?p=a&ACTION=View&id=172" name="iste08">ISTE 08b</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">2008</span>
<span class="title"><a href="http://www.iste.co.uk/index.php?p=a&ACTION=View&id=172">Mathematical Programming Formulations and Lower Bounds for the RCPSP</a></span>
Chapter 3 in <span class="livre">Resource-Constrained Project Scheduling: models, algorithms, extensions and applications</span>, C. Artigues, S. Demassey, E. Néron (eds.), ISTE/Wiley, ISBN 978-1-84821-034-9.
</dd>
<dt><a href="http://www.springer.com/business/organization/book/978-0-387-33643-5" name="rcpsp06">ISORMS 06</a></dt>
<dd>
<span class="author">Emmanuel Néron, Christian Artigues, Philippe Baptiste, Jacques Carlier, Sophie Demassey, Philippe Laborie</span>
<span class="year">2006</span>
<span class="title"><a href="http://www.springer.com/business/organization/book/978-0-387-33643-5">Lower bounds computation for RCPSP</a></span>
chapter in <span class="livre">Perspectives in modern project scheduling,</span> J. Weglarz, J. Jozefowska (eds.), Springer, ISBN 978-0-387-33643-5, International Series in Operations Research & Management Science, Vol. 92.
</dd>
<dt><a href="art/demassey05ijc.pdf" name="ijc05">IJOC 05</a></dt>
<dd>
<span class="author">Sophie Demassey, Christian Artigues, Philippe Michelon</span>
<span class="year">2005</span>
<span class="title"><a href="art/demassey05ijc.pdf">Constraint propagation based cutting planes : an application to the resource-constrained project scheduling problem</a></span>
<span class="journal">INFORMS Journal on Computing</span>(2005) 17 (1) : 52 - 65.
<span class="abs">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.</span>
Preliminary results presented at <span class="conf">ISMP'00</span>, <span class="conf">FRANCORO'01</span>, <span class="conf">OR'02</span>, <span class="conf">ROADEF'02</span>, <span class="conf">CIRO'02</span>.
</dd>
<dt><a href="art/demassey05chapRCPSP.pdf" name="prod05">PIP 05</a></dt>
<dd>
<span class="author">Christian Artigues, Sophie Demassey</span>
<span class="year">2005</span>
<span class="title"><a href="art/demassey05chapRCPSP.pdf">Gestion de projet</a></span>
chap. IV de <span class="livre">Gestion de la production et ressources humaines: méthodes de planification dans les systèmes productifs,</span> A. Hait (éd.), Presses internationales Polytechnique, Montréal, Canada, ISBN 978-2-553-01145-0.
</dd>
<dt><a class="nolink" name="roadef05">ROADEF 05</a></dt>
<dd class="rgb">
<span class="author">Thierry Garaix, Christian Artigues et Sophie Demassey</span>
<span class="year">2005</span>
<span class="title">Bornes basées sur les ensembles interdits pour le problème d'ordonnancement de projet à moyens limités</span>
6ème congrès de la société française de recherche opérationnelle et d'aide à la décision (<span class="conf">ROADEF'05</span>), 14-16 february 2005, Tours, France.
</dd>
<dt><a href="art/baptiste04ors.pdf" name="ors04">ORSpectrum 04</a></dt>
<dd>
<span class="author">Philippe Baptiste, Sophie Demassey</span>
<span class="year">2004</span>
<span class="title"><a href="art/baptiste04ors.pdf">Tight LP bounds for Resource Constrained Project Scheduling</a></span>
<span class="journal">OR Spectrum</span>(2004) 26 : 251 - 262.
see also: <a href="rcpsp/index.html">computational results</a>.
<span class="abs">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!</span>
</dd>
<dt><a href="art/demassey04pms.pdf" name="pms04">PMS 04</a></dt>
<dd>
<span class="author">Sophie Demassey, Christian Artigues, Philippe Baptiste, Philippe Michelon</span>
<span class="year">2004</span>
<span class="title"><a href="art/demassey04pms.pdf">Lagrangean relaxation-based lower bounds for the RCPSP</a></span>
9th international workshop on project management and scheduling (<span class="conf">PMS'04</span>), 26-28 april 2004, Nancy, France.
<span class="abs">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.</span>
</dd>
<dt><a href="art/demassey02cpaior.pdf" name="cpaior02">CPAIOR 02</a></dt>
<dd>
<span class="author">Sophie Demassey, Christian Artigues, Philippe Michelon</span>
<span class="year">2002</span>
<span class="title"><a href="art/demassey02cpaior.pdf">A hybrid constraint propagation-cutting plane algorithm for the RCPSP</a></span>
4th International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (<span class="conf">CPAIOR'02</span>), 25-27 march 2002, Le Croisic, France, Proc. p. 321-331.
<span class="abs">Preliminary study for IJOC'05: CP-based valid linear inequalities for the time-indexed MIP formulation of the RCPSP.</span>
</dd>
<dt><a href="art/demassey01cosolv.pdf" name="cosolv01">Cosolv 01</a></dt>
<dd>
<span class="author">Sophie Demassey, Christian Artigues, Philippe Michelon</span>
<span class="year">2001</span>
<span class="title"><a href="art/demassey01cosolv.pdf">Comparing lower bounds for the RCPSP under a same hybrid constraint-linear programming approach</a></span> Proc. p. 109-123.
Workshop on Cooperative Solvers in Constraint Programming (<span class="conf">CoSolv'01</span>), International Conference on Constraint Programming (CP'01), 2001, Paphos, Cyprus.
<span class="abs">Preliminary study for IJOC'05: first cuts.</span>
</dd>
<dt><a class="nolink" name="dea00">MSc 00</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">2000</span>
<span class="title"><a class="nolink">Borne inférieure pour l'ordonnancement de projet à moyens limités</a></span>
MSc Thesis (Mémoire de DEA) in Computer Science - Combinatorial Optimization, University of Aix-Marseille II, 2000.
</dd>
</dl>
<h2 id="gccat">systematic reformulation of global constraints</h2><dl>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00481554" name="ct07">Constraints 07</a></dt>
<dd>
<span class="author">Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Thierry Petit</span>
<span class="year">2007</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00481554">Global Constraint Catalog: Past, Present and Future</a></span>
<span class="journal">Constraints</span>(2007) 12 (1): 21-62. [<a href="http://dx.doi.org/10.1007/s10601-006-9010-8">doi</a>].
<span class="abs">We present the objectives of the <a href="gccat/">Global Constraint Catalog</a> 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.</span>
</dd>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00481570" name="cp06">CP 06</a></dt>
<dd>
<span class="author">Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Thierry Petit</span>
<span class="year">2006</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00481570">Graph Properties Based Filtering</a></span>
<span class="journal">Lecture Notes in Computer Science</span> (2006) 4204: 59-74.
12th International Conference on Principles and Practice of Constraint Programming (<span class="conf">CP'06</span>), 24-29 sep 2006, Nantes, France.
<span class="abs">Most global constraints of the <a href="gccat/">catalog</a> 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 <a href="http://dx.doi.org/10.1051/ro:2007001">previous paper</a> 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.</span>
</dd>
<dt><a href="http://hal.inria.fr/inria-00085796" name="jfpc06">JFPC 06</a></dt>
<dd class="rgb">
<span class="author">Nicolas Beldiceanu, Mats Carlsson, Sophie Demassey, Thierry Petit</span>
<span class="year">2006</span>
<span class="title"><a href="http://hal.inria.fr/inria-00085796">Filtrage basé sur des propriétés de graphe</a></span>
2èmes Journées Francophones de Programmation par Contraintes (<span class="conf">JFPC'06</span>), 7-9 jun 2006, Nîmes, France.
</dd>
</dl>
<h2 id="rs">resolution search</h2><dl>
<dt><a href="http://hal.archives-ouvertes.fr/hal-00482955" name="hyb06">HYBRID 06</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">2006</span>
<span class="title"><a href="http://hal.archives-ouvertes.fr/hal-00482955">Experiments with Resolution search</a></span>
Workshop on Hybrid methods and branching rules in combinatorial optimization (<span class="conf"><a href="http://www.crm.umontreal.ca/Hybrid06/">Hybrid'06</a></span>), 18-22 september 2006, Montréal, Canada.
<span class="abs">A terrific optimization algorithm.</span>
</dd>
<dt><a class="nolink" name="chv05">Concordia 05</a></dt>
<dd class="rgb">
<span class="author">Sophie Demassey</span>
<span class="year">2005</span>
<span class="title">Resolution search and intelligent backtrackings</span>
invited seminar <a href="http://users.encs.concordia.ca/~concoco/">ConCoCO</a>, 16 june 2005, University of Concordia, Montréal, Canada.
</dd>
<dt><a class="nolink" name="gdtpm03">CRT 04</a></dt>
<dd class="rgb">
<span class="author">Sophie Demassey</span>
<span class="year">2004</span>
<span class="title">Resolution search et backtrackings intelligents</span>
invited seminar <a href="https://www.cirrelt.ca/">CIRRELT</a> (ex CRT), 5 novembre 2004, Université de Montréal, Canada.
</dd>
<dt><a class="nolink" name="ecco04">ECCO 04</a></dt>
<dd class="rgb">
<span class="author">Sophie Demassey</span>
<span class="year">2004</span>
<span class="title">An application of resolution search to the RCPSP</span>
17th European Conference on Combinatorial Optimization (<span class="conf">ECCO'04</span>), 24-26 june 2004, Beyrouth, Lebanon.
</dd>
<dt><a class="nolink" name="gdtpm03">PM 03</a></dt>
<dd class="rgb">
<span class="author">Sophie Demassey</span>
<span class="year">2003</span>
<span class="title">Resolution search et backtrackings intelligents</span>
invited seminar, 1ère journée du GDT Programmation Mathématique, 5 december 2003, Paris.
</dd>
<dt><a href="art/demassey03earo.pdf" name="earo03">EARO 03</a></dt>
<dd>
<span class="author">Sophie Demassey, Serigne Gueye, Philippe Michelon, Christian Artigues</span>
<span class="year">2003</span>
<span class="title"><a href="art/demassey03earo.pdf">Application de resolution search au RCPSP</a></span>
École d'Automne de Recherche Opérationnelle (<span class="conf">EARO'03</span>), 28-31 october 2003, Tours.
<span class="abs"><a href="http://dx.doi.org/10.1016/S0166-218X(96)00003-0">Resolution Search</a> is a complete non-tree search algorithm created by <a href="http://users.encs.concordia.ca/~chvatal/">Vašek Chvátal</a>, 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.</span>
</dd>
</dl>
<h2 id="comma">commutative algebra</h2><dl>
<dt><a class="nolink" name="dea98">MSc 98</a></dt>
<dd>
<span class="author">Sophie Demassey</span>
<span class="year">1998</span>
<span class="title"><a class="nolink">Élasticité dans les anneaux de Dedekind</a></span>
MSc Thesis (Mémoire de DEA) in Pure Mathematics - Commutative Algebra, University of Aix-Marseille I, 1998.
</dd>
</dl>
<p class="foot">credits: drawing from <a href="http://xkcd.com/">XKCD</a> - last update: june 2024</p>
</section>
</div>
</body>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46018994-1', 'sofdem.github.io');
ga('send', 'pageview');
</script>
</html>