biblio
Sophie Demassey
thematic bibliography
- nonsmooth nonconvex optimization (2019-)
- scheduling and planning in power systems (2015-)
- MINLP for water distribution systems (2014-)
- models and algorithms in CP (2010-)
- flexible datacenter resource management with CP (2009-)
- automata and optimization constraints for rostering (NRP) (2005-2012)
- column generation for railway infrastructure capacity (SPP) (2009-2012)
- ILP model decompositions with CP-based processing for project scheduling (RCPSP) (2000-2008)
- systematic reformulation of global constraints (2006-2007)
- resolution search for the RCPSP (2003-2006)
- commutative algebra (1997-1998)
nonsmooth nonconvex optimization
- PJO24
- 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
- A bundle method for nonsmooth DC programming with application to chance-constrained problems Computational Optimization and Applications (2021) 78: 451-490. 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.
scheduling and planning in power systems
- SEGAN23
- Difference-of-Convex Approach to Chance-Constrained 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 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 [COA20]. The approach yields a natural and embarrassingly parallelizable scenario decomposition.
- ROADEF 20
- 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
- Optimal engagement and operation of a grid-connected PV/battery system 2019 IEEE PES Innovative Smart Grid Technologies Europe (ISGT-Europe'19), Bucharest, Romania. 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. Preliminary results presented at Roadef'18.
- ICAE 19
- 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
- A Difference-of-Convex 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 DC-constrained DC program. Also presented at PID'19, ROADEF'20.
- ISMP 18a
- Robust optimisation of storage in a power generation expansion planning problem 23rd International Symposium on Mathematical Programming (ISMP'18), Bordeaux, France. Coupling a long-term power generation expansion planning model with a mid-term storage optimization model to handle uncertainties in renewable production. Also presented at PGMO days 18.
- ISMP 18b
- Modelling distributed energy resources uncertainties in short-term 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
- 2017 Scaling Energy Adaptive Applications for Sustainable Profitability Lecture Notes in Computer Science (2017) 10417: 23-35. Euro-Par'17 Parallel Processing: 23rd International Conference, Santiago de Compostella, Spain. 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.
- EURO 16b
- 2016 Robust optimisation for a smart grid 28th European Conference on Operational Research (EURO'16), 3-6 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
- 2024 Alternating direction method and deep learning for discrete control with storage Lecture Notes in Computer Science (2017) 14594: 85-96. 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 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. Slides at ISCO'24 and previous talks at Roadef'24: about deep learning and adm.
- Amir 23
- Combinatorial Optimization and deep learning for energy-efficient water distribution networks PhD thesis directed with Valentina Sessa and defended 20/12/2023, Sophia-Antipolis.
- ETSAP 23
- Combinatorial Optimization for Water Management Joint autumn School 2023 of IEA-ETSAP and the Transition Institute 1.5, Sophia-Antipolis, nov 2023. Very short introduction to combinatorial optimization and overview of applications in water management. See the slides.
- OR 23
- 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
- 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
- Strengthening mathematical models for pump scheduling in water distribution 14th International Conference on Applied Energy (ICAE'22), Bochum, Germany. Intensive OBBT (optimization-based 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
- Enhanced branch and check for pump scheduling in water networks Workshop on Mixed Integer NonLinear Programming (MINLP'21), online. 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. See the talk online and the slides.
- OE 20
- Pump scheduling in drinking water distribution networks with an LP/NLP-based branch and bound Optimization and Engineering (2021) 22: 1275-1313. 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. Preliminary results presented at ISMP 18 and ROADEF 19.
- INOC 19
- 2019 Extended linear formulation of the pump scheduling problem in water distribution networks Network Optimization INOC (2019): 13-18. Open Proceedings. [doi] 9th International Network Optimization Conference, 12-14 june 2019, Avignon. [slides] 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. Also presented at PGMO 19
- WCGO 19
- 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: 957-967. [doi] 6th World Congress on Global Optimization (WCGO'19), 8-10 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 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. Preliminary results presented at ROADEF'17.
- GB 18
- 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
- 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 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. Also presented a ROADEF'19; preliminary results at EURO'16 (convex relaxation), ROADEF'17 (time step duration adjustment heuristic) and IFORS'17.
- AE 16
- 2017 A convex mathematical program for pump scheduling in a class of branched drinking water networks Applied Energy vol. 185, 1702-1711. 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. Presented at ROADEF'16.
- EURO 15
- 2015 Energy efficiency in water supply systems : variable speed drives vs pumping scheduling 27th European Conference on Operational Research (EURO'15), 12-15 july 2015, Glasgow. Where we compare the opportunities of installing variable speed drives vs. optimizing the pump schedule in a drinking water pumping station.
- ICAE 15
- 2015 A heuristic approach to the water networks pumping scheduling issue Energy Procedia (2015) 75: 2846-2851. 7th International Conference on Applied Energy (ICAE'15), 28-31 march 2015, Abu Dhabi, UAE. A summary of Gratien's work during his internship at Schneider Electric on the day-ahead Pump Scheduling Problem in a drinking water pumping station. We present a convex Mixed Integer Quadratically Constrained Program and a Benders-like heuristic approach.
models and algorithms in CP
- ACPS 2019
- 2019 Decompositions and hybridizations in Constraint Programming ACP Summer School, Vienna July 1-5, 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
- 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
- 2015 Hybridation de programmation linéaire et de programmation par contraintes pour le problème de déplacement de conteneurs 16ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'15), 11-12 february 2015, Marseille, France. An attempt to solve the Container Relocation Problem with CP: a lower bound is required ! (Note that MIP is really bad on this problem) We MIPped such a lower bound in our CP model and filtered accordingly. By the way Choco/Gurobi is an easy mix under Java.
- CPAIOR 12
- 2012 The Conjunction of Interval Among Constraints Lecture Notes in Computer Science (2012) 7298: 113-128. 9th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'12), 28 may-1 june 2012, Nantes. We call Interval-Amongs a conjunction of among constraints on interval value domains. We prove that such a conjunction is in P (while the general case is NP-hard) using a new vertical "cardinality-based" decomposition made of a temporal constraint network and a flow network model. We derive from this a relaxed BC algorithm simple to implement as the conjunction of an all-shortest-paths filtering with a (flow-based) GCC. This is compared, both theoretically and empirically, to the standard horizontal "among-based" decomposition. Finally, we prove that Box-Amongs, i.e. the problem in higher dimensions, remains NP-hard.
- RR 11
- 2011 Multi-Agent Electro-Location and the Among Constraint INRIA, Research Report 00598712. The application-oriented variant of paper (CPAIOR 12) above. Gilles has exhibited the Interval-Amongs constraint in the problem of localization of robots equipped with the electric sense. This occurs in the context of the reconfigurable anguilliform swimming robot imagined by Frédéric.
- AOR 10
- 2010 New filtering for the cumulative constraint in the context of non-overlapping rectangles Annals of Operations Research(2011) 184 (1): 27-50. [doi] We formalize and study the complexity of the longest hole problem: it is to find the longest period during which tasks can be scheduled on a cumulative resource with a resource vacancy lower than a given slack value. A bounding algorithm for this problem and a filtering for the cumulative constraint based on this bound have been implemented in geost.
flexible datacenter resource management with CP
- BtrPlace
- 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
- 2015 Dynamic Packing with Side Constraints for Datacenter Resource Management in G. Fasano and J.D. Pintér. eds, Optimized Packings and Their Applications, Springer Optimization and Its Applications vol. 105, Springer, New York. This chapter describes the variant of the vector packing problem considered in BtrPlace in the context of datacenter resource management, giving an insight into its dynamic and heterogeneous nature.
- PGMO-COPI 14
- 2014 BtrPlace: Flexible VM Management in Data Centers Conference on Optimization & Practices in Industry (PGMO-COPI'14), 28-31 october 2014, Paris-Saclay, France. 3p. Presentation of the last results todate of BtrPlace.
- CP 11
- 2011 Bin-Repacking Scheduling in Virtualized Datacenters Lecture Notes in Computer Science (2011) 6876: 27-41. 17th International Conference on Principles and Practice of Constraint Programming (CP'11), application track, 13-16 september 2011, Perugia, Italy. [doi, slides, annex] Take an in-fashion domain (cloud !), a combined packing and scheduling problem (where and when to migrate ?), a singular scheduling property (concurrent resource requirements during live migration), and various side placement constraints, and say: CP is fun. We present the CP model and search heuristic implemented with Choco in Entropy the former version of BtrPlace, an autonomous VM manager conceived and developed by Fabien. Since the submission, we have greatly improved our implementation. Newer computational results for the experiments of the paper are available in this annex report (sep 26, 2011).
automata and optimization constraints for rostering
- seminar CMP 14
- 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
- 2011 Automates et programmation par contraintes pour la planification de personnel PhD Thesis in Computer Science, University of Nantes, 28 october 2011.
- PATAT 10
- 2010 Weighted Automata, Constraint Programming, and Large Neighborhood Search Nurse Rostering Competition at the 8th International Conference for the Practice and Theory of Automated Timetabling (PATAT'10), 10-13 august 2010, Belfast, Ireland. We propose an automated planner, implemented with Choco, answering to the specifications of the NRP competition. The parser builds and compounds a multi-weighted automaton from a given set of soft scheduling rules, and then a CP model based on one Multicost-Regular per nurse and one Global Cardinality per period. The model is optimized heuristically through LNS.
- RR 10
-
2010
Modélisation et optimisation des préférences en planification de personnel
École des Mines de Nantes, Research Report 11-01-INFO.
We present an algorithm for intersecting weighted automata as a multi-weighted automaton. In the context of Employee Timetabling with Preferences, this can be used to aggregate the rules which constrain the timetable of an employee and to count their violation degrees. The automaton can be embedded in a Multicost-Regular constraint or in the soft variant, that we introduce in this paper, to handle violations costs associated to the violation degrees through any penalty functions. - CPAIOR 09
- 2009 Sequencing and counting with the multicost-regular constraint Lecture Notes in Computer Science (2009) 5547: 178 - 192. 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'09), 27-31 may 2009, Pittsburgh, USA. We introduce Multicost-Regular, an extension of the Cost-Regular constraint to handle vectors of costs. It is equivalent to an instance of the Resource Constrained Longest/Shortest Path Problem in a layered graph and thus is NP-complete. We present a lagrangian-based filtering algorithm for this constraint. Preliminary results presented at ROADEF'09 (lagrangian-based filtering).
- JFPC 09
- 2009 Séquencer et compter avec la contrainte multicost-regular Proc. p. 125-134. 5èmes Journées Francophones de Programmation par Contraintes (JFPC'09), 3-5 june 2009, Orléans, France.
- Constraints 06
- 2006 A Cost-Regular based Hybrid Column Generation Approach Constraints(2006) 11 (4) : 315 - 333. [doi] This extends the paper of CPAIOR'05 with a discussion about optimization global constraints, with a variable-value selection strategy coupled to the cost-regular constraint, with a heuristic and a branching strategy for the CP-based column generation model of the Employee Timetabling Problem, and with experiments on two complex real-case studies.
- CPAIOR 05
- 2005 Constraint programming based column generation for employee timetabling Lecture Notes in Computer Science (2005) 3524: 140 - 154. 2nd International Conference on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'05), 30 may - 2 june 2005, Prague, Czech Republic. We introduce Cost-Regular, the optimization variant of the Regular constraint. Given a weighted automaton, it enforces a sequence of variables to belong to the regular language specified by the automaton and a cost variable to be equal to the total weight of the sequence. This constraint is used to optimize the subproblem of column generation in the Set Covering ILP model of the Employee Timetabling Problem. Preliminary results presented at JOPT'05.
column generation for railway infrastructure capacity
- Aurélien's PhD
- 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
- 2011 A collaborative combination between column generation and ant colony optimization for solving set packing problems 9th Metaheuristics International Conference (MIC'11), 25-27 july 2011, Udine, Italy. To speed up an ACO procedure on large-size SPP instances, a column generation procedure is applied as a preprocessing step: the search space of the heuristic is restricted to the columns (the subsets) generated so far, and bounded by the optimum of the LP relaxation computed in the same time.
- WCRR 11
- 2011 Towards a Realistic Evaluation of Railway Infrastructure Capacity 9th World Congress on Railway Research (WCRR'11), 22-26 may 2011, Lille, France. We describe our implementation of a CG-ACO algorithm for the railway infrastructure capacity problem in the RECIFE software. Preliminary results presented at ROADEF'10 (column generation).
- ROADEF 09a
- 2009 An improved upper bound for the railway infrastructure capacity problem on the Pierrefitte-Gonesse junction Long paper in Proc. p. 62-76, ISBN 2-905267-65-8. 10ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF'09), 11-12 february 2009, Nancy, France. The capacity of a railway node is the maximum number of trains which can be routed through the infrastructure whith respect to safety constraints, given a large set of possible trains, schedules and allowed delays. We tackle the SPP formulation of this problem with column generation. At each iteration, we exploit the redundancy and dominance relation between the constraints of the restricted master program in order to speed up its resolution.
ILP decompositions and CP for the RCPSP
- PhD 03
-
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
- 2008 Resource-Constrained Project Scheduling: models, algorithms, extensions and applications ISTE/Wiley, ISBN 978-1-84821-034-9.
- ISTE 08b
- 2008 Mathematical Programming Formulations and Lower Bounds for the RCPSP Chapter 3 in Resource-Constrained Project Scheduling: models, algorithms, extensions and applications, C. Artigues, S. Demassey, E. Néron (eds.), ISTE/Wiley, ISBN 978-1-84821-034-9.
- ISORMS 06
- 2006 Lower bounds computation for RCPSP chapter in Perspectives in modern project scheduling, J. Weglarz, J. Jozefowska (eds.), Springer, ISBN 978-0-387-33643-5, International Series in Operations Research & Management Science, Vol. 92.
- IJOC 05
- 2005 Constraint propagation based cutting planes : an application to the resource-constrained project scheduling problem INFORMS Journal on Computing(2005) 17 (1) : 52 - 65. We examine various filtering rules for the resource and temporal constraints of the RCPSP and use the result of their propagation to preprocess and to generate several valid linear inequalities for both the continous-time and the time-indexed MIP models. In our experiments, we observe the capacity of the cuts to improve the lower bounds computed by the LP-relaxations in constructive and destructive (progressive UB rejection) ways. Preliminary results presented at ISMP'00, FRANCORO'01, OR'02, ROADEF'02, CIRO'02.
- PIP 05
- 2005 Gestion de projet chap. IV de Gestion de la production et ressources humaines: méthodes de planification dans les systèmes productifs, A. Hait (éd.), Presses internationales Polytechnique, Montréal, Canada, ISBN 978-2-553-01145-0.
- ROADEF 05
- 2005 Bornes basées sur les ensembles interdits pour le problème d'ordonnancement de projet à moyens limités 6ème congrès de la société française de recherche opérationnelle et d'aide à la décision (ROADEF'05), 14-16 february 2005, Tours, France.
- ORSpectrum 04
- 2004 Tight LP bounds for Resource Constrained Project Scheduling OR Spectrum(2004) 26 : 251 - 262. see also: computational results. We complement the approach followed up in IJOC'05 of CP-based preprocessing and cut generation for MIP models of the RCPSP. We consider Mingozzi's relaxed MIP formulation, propose new valid linear inequalities including cuts based on energetic reasoning, and a strong preprocessing obtained by intensive constraint propagation. This initial CP model includes redundant disjunctive constraints inferred by... MIPs!
- PMS 04
- 2004 Lagrangean relaxation-based lower bounds for the RCPSP 9th international workshop on project management and scheduling (PMS'04), 26-28 april 2004, Nancy, France. We investigate a lagrangian relaxation of Mingozzi's formulation of the RCPSP. The model decomposes in one multiknapsack problem for each time period (to compute a feasible set) and in one project scheduling problem with time-dependent costs but no resource constraints, which amounts to a minimum cut problem solvable in polynomial time.
- CPAIOR 02
- 2002 A hybrid constraint propagation-cutting plane algorithm for the RCPSP 4th International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'02), 25-27 march 2002, Le Croisic, France, Proc. p. 321-331. Preliminary study for IJOC'05: CP-based valid linear inequalities for the time-indexed MIP formulation of the RCPSP.
- Cosolv 01
- 2001 Comparing lower bounds for the RCPSP under a same hybrid constraint-linear programming approach Proc. p. 109-123. Workshop on Cooperative Solvers in Constraint Programming (CoSolv'01), International Conference on Constraint Programming (CP'01), 2001, Paphos, Cyprus. Preliminary study for IJOC'05: first cuts.
- MSc 00
- 2000 Borne inférieure pour l'ordonnancement de projet à moyens limités MSc Thesis (Mémoire de DEA) in Computer Science - Combinatorial Optimization, University of Aix-Marseille II, 2000.
systematic reformulation of global constraints
- Constraints 07
- 2007 Global Constraint Catalog: Past, Present and Future Constraints(2007) 12 (1): 21-62. [doi]. We present the objectives of the Global Constraint Catalog and the results to date. The catalog is a base of knowledge referring most of the studies on global constraints of the literature. It is also an electronic dictionary conceived to be processed in a systematic way. This includes the reformulation of constraints in terms of graph properties or of automata.
- CP 06
- 2006 Graph Properties Based Filtering Lecture Notes in Computer Science (2006) 4204: 59-74. 12th International Conference on Principles and Practice of Constraint Programming (CP'06), 24-29 sep 2006, Nantes, France. Most global constraints of the catalog have a reformulation as a graph in that the solutions of a constraint are in 1-to-1 correspondence with the subgraphs satisfying some given bounds on some given invariants. A previous paper by Nicolas, Thierry and Guillaume Rochart showed how to estimate the most common invariants. In this paper, we show how to filter the graph (remove and fix nodes and arcs) in case of the estimate coincides with a bound. This results in a generic filtering algorithm for various global constraints.
- JFPC 06
- 2006 Filtrage basé sur des propriétés de graphe 2èmes Journées Francophones de Programmation par Contraintes (JFPC'06), 7-9 jun 2006, Nîmes, France.
resolution search
- HYBRID 06
- 2006 Experiments with Resolution search Workshop on Hybrid methods and branching rules in combinatorial optimization (Hybrid'06), 18-22 september 2006, Montréal, Canada. A terrific optimization algorithm.
- Concordia 05
- 2005 Resolution search and intelligent backtrackings invited seminar ConCoCO, 16 june 2005, University of Concordia, Montréal, Canada.
- CRT 04
- 2004 Resolution search et backtrackings intelligents invited seminar CIRRELT (ex CRT), 5 novembre 2004, Université de Montréal, Canada.
- ECCO 04
- 2004 An application of resolution search to the RCPSP 17th European Conference on Combinatorial Optimization (ECCO'04), 24-26 june 2004, Beyrouth, Lebanon.
- PM 03
- 2003 Resolution search et backtrackings intelligents invited seminar, 1ère journée du GDT Programmation Mathématique, 5 december 2003, Paris.
- EARO 03
- 2003 Application de resolution search au RCPSP École d'Automne de Recherche Opérationnelle (EARO'03), 28-31 october 2003, Tours. Resolution Search is a complete non-tree search algorithm created by Vašek Chvátal, which uses some kind of SAT solver to manage the nogood set and thus to guide the search towards almost-unexplored spaces. We have experimented it on a BIP formulation of the RCPSP. The study is described in french with more details in my PhD thesis.
commutative algebra
- MSc 98
- 1998 Élasticité dans les anneaux de Dedekind MSc Thesis (Mémoire de DEA) in Pure Mathematics - Commutative Algebra, University of Aix-Marseille I, 1998.
credits: drawing from XKCD - last update: june 2024