Dr. Guillaume Sagnol

Head of MATH+ Junior Research Group "Optimization under Uncertainty"

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, Sekr. MA 5-2
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Office: MA 518
Telephone: +49 30 314 78846
Email: (lastname)@math.tu-berlin.de

For a list of activities beyond my current position at TU Berlin, see also my personal webpage.

Teaching

Seminar Recent Advances in Discrete Optimization
Summer 2022
Lecture Introduction to Linear and Discrete Optimization (ADM I)
Winter 21/22
Seminar Network Evolution Models
Summer 2021
Lecture Approximation Algorithms (ADM III)
Winter 20/21
Lecture Convex Optimization and Applications (ADM III)
Winter 19/20

Projects

Evolution Models for Historical Networks
Math+ project EF5-6 with Benjamin Ducke and Max Klimm
Stochastic Scheduling with Restricted Adaptivity
Math+ project AA3-6 with Ralf Borndörfer
Flow-Preserving Graph Contractions
Math+ project AA3-4 with Max Klimm, Torsten Mütze and Martin Skutella
LogiScale - BigData in Logistics: Multiscale and Combinatorial Methods in Optimization
4flow Europäischer Fonds für regionale Entwicklung der Europäischen Union (EFRE) with Martin Skutella, Yann Disser, Max Klimm and Torsten Mütze
Robust Optimization of Load Balancing in the Operating Theatre
Einstein Center for Mathematics Berlin Project MI-CH1

Publications

Spatiotemporal reconstruction of ancient road networks through sequential cost–benefit analysis (Maximilian J. Stahlberg, Guillaume Sagnol, Benjamin Ducke and Max Klimm)
PNAS Nexus, to appear.
DOI Bibtex
@article{StahlbergSagnolDuckeKlimm2022,
author = {Maximilian J. Stahlberg and Guillaume Sagnol and Benjamin Ducke and Max Klimm},
title = {Spatiotemporal reconstruction of ancient road networks through sequential cost--benefit analysis},
journal = {PNAS Nexus},
year = {to appear},
doi = {10.1093/pnasnexus/pgac313},
}

Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling (Sven Jäger, Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt and Philipp Warode)
IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization.
PDF arxiv Bibtex
@inproceedings{JaegerSagnolSchmidtGW2023,
arxiv = {2211.02044},
author = {Sven Jäger and Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt and Philipp Warode},
title = {Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling},
year = {2023},
booktitle = {IPCO 2023 – Proc. 24th Conference on Integer Programming and Combinatorial Optimization},
}
Surgery Scheduling in Flexible Operating Rooms by using a Convex Surrogate Model of Second-Stage Costs (Mohammed Majthoub Almoghrabi and Guillaume Sagnol)
Preprint, 2023.
PDF arxiv Bibtex Abstract
@techreport{almoghrabi2023surgery,
title = {Surgery Scheduling in Flexible Operating Rooms by using a Convex Surrogate Model of Second-Stage Costs},
author = {Majthoub Almoghrabi, Mohammed and Sagnol, Guillaume},
year = {2023},
arxiv = {2304.13670},
}

We study the elective surgery planning problem in a hospital with operation rooms shared by elective and emergency patients. This problem can be split in two distinct phases. First, a subset of patients to be operated in the next planning period has to be selected, and the selected patients have to be assigned to a block and a tentative starting time. Then, in the online phase of the problem, a policy decides how to insert the emergency patients in the schedule and may cancel planned surgeries. The overall goal is to minimize the expectation of a cost function representing the assignment of patient to blocks, case cancellations, overtime, waiting time and idle time. We model the offline problem by a two-stage stochastic program, and show that the second-stage costs can be replaced by a convex piecewise linear surrogate model that can be computed in a preprocessing step. This results in a mixed integer program which can be solved in a short amount of time, even for very large instances of the problem. We also describe a greedy policy for the online phase of the problem, and analyze the performance of our approach by comparing it to either heuristic methods or approaches relying on sampling average approximation (SAA) on a large set of benchmarking instances. Our simulations indicate that our approach can reduce the expected costs by as much as 20% compared to heuristic methods and is able to solve problems with 1000 patients in about one minute, while SAA-approaches fail to obtain near-optimal solutions within 30 minutes, already for 100 patients.

PICOS: A Python interface to conic optimization solvers (Guillaume Sagnol and Maximilian Stahlberg)
J. Open Source Softw., 7(70):3915, 2022.
DOI Bibtex
@article{SagnolStahlberg2022,
author = {Sagnol, Guillaume and Stahlberg, Maximilian},
title = {{PICOS}: A Python interface to conic optimization solvers},
journal = {J. Open Source Softw.},
year = {2022},
volume = {7},
number = {70},
pages = {3915},
doi = {10.21105/joss.03915},
}
Competitive Algorithms for Symmetric Rendezvous on the Line (Max Klimm, Guillaume Sagnol, Martin Skutella and Khai Van Tran)
SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, pp. 329–347.
[url] DOI Bibtex
@inproceedings{KlimmSagnolSkutella+2022,
author = {Klimm, Max and Sagnol, Guillaume and Skutella, Martin and Van Tran, Khai},
booktitle = {SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms},
title = {Competitive Algorithms for Symmetric Rendezvous on the Line},
doi = {10.1137/1.9781611977073.16},
pages = {329--347},
year = {2022},
url = {https://epubs.siam.org/doi/reader/10.1137/1.9781611977073.16},
}
Improved Bounds for Stochastic Extensible Bin Packing under Distributional Assumptions (Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt)
ISCO 2022 – Proc. 7th International Symposium on Combinatorial Optimization, pp. 228–241.
PDF DOI arxiv Bibtex
@inproceedings{SagnolSchmidtGW22,
title = {Improved Bounds for Stochastic Extensible Bin Packing under Distributional Assumptions},
author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel},
booktitle = {ISCO 2022 – Proc. 7th International Symposium on Combinatorial Optimization},
year = {2022},
doi = {10.1007/978-3-031-18530-4_17},
series = {Lecture Notes in Computer Science},
volume = {13526},
pages = {228--241},
arxiv = {2002.00060},
}

Removing inessential points in $c-$ and $A-$optimal design (Luc Pronzato and Guillaume Sagnol)
J. Stat. Plan. Inference, 213:233–252, 2021.
[url] DOI Bibtex
@article{PronzatoSagnol2021,
author = {Pronzato, Luc and Sagnol, Guillaume},
title = {Removing inessential points in $c-$ and $A-$optimal design},
journal = {J. Stat. Plan. Inference},
year = {2021},
doi = {10.1016/j.jspi.2020.11.011},
volume = {213},
pages = {233--252},
url = {https://hal.science/hal-02868664},
}
Restricted Adaptivity in Stochastic Scheduling (Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt)
ESA 2021 – Proc. 29th European Symposium on Algorithms, pp. 79:1–79:14.
PDF DOI arxiv Bibtex
@inproceedings{SagnolSchmidtGW21,
author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel},
title = {{Restricted Adaptivity in Stochastic Scheduling}},
booktitle = {ESA 2021 – Proc. 29th European Symposium on Algorithms},
pages = {79:1--79:14},
series = {LIPIcs},
year = {2021},
volume = {204},
doi = {10.4230/LIPIcs.ESA.2021.79},
arxiv = {2106.15393},
}

Approximate and exact D-optimal designs for $2^k$ factorial experiments for Generalized Linear Models via SOCP (Belmiro P.M. Duarte and Guillaume Sagnol)
Stat. Pap., 61:2737–2767, 2020.
[url] DOI Bibtex
@article{DuarteSagnol2020,
author = {Duarte, Belmiro P.M. and Sagnol, Guillaume},
title = {Approximate and exact D-optimal designs for $2^k$ factorial experiments for Generalized Linear Models via SOCP},
year = {2020},
doi = {10.1007/s00362-018-01075-7},
journal = {Stat. Pap.},
volume = {61},
pages = {2737--2767},
url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-66256},
}

An unexpected connection between Bayes $A-$optimal designs and the Group Lasso (Guillaume Sagnol and Edouard Pauwels)
Stat. Pap., 60(2):215–234, 2019.
PDF DOI arxiv Bibtex
@article{SagnolPauwels2019,
author = {Sagnol, Guillaume and Pauwels, Edouard},
title = {An unexpected connection between Bayes $A-$optimal designs and the Group Lasso},
journal = {Stat. Pap.},
year = {2019},
arxiv = {1809.01931},
doi = {10.1007/s00362-018-01062-y},
volume = {60},
number = {2},
pages = {215--234},
}

An algorithm based on Semidefinite Programming for finding minimax optimal designs (Belmiro P.M. Duarte, Guillaume Sagnol and Weng Kee Wong)
Comput. Stat. Data Anal., 119:99–117, 2018.
[url] DOI Bibtex
@article{DuarteSagnolWong2018,
author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Wong, Weng Kee},
title = {An algorithm based on Semidefinite Programming for finding minimax optimal designs},
journal = {Comput. Stat. Data Anal.},
volume = {119},
pages = {99--117},
year = {2018},
doi = {10.1016/j.csda.2017.09.008},
url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-66249},
}
The Cone of Flow Matrices: Approximation Hierarchies and Applications (Guillaume Sagnol, Marco Blanco and Thibault Sauvage)
Networks, 72(1):128–150, 2018.
Extended abstract appeared in Proc. of INOC 2017
[url] DOI Bibtex
@article{SagnolBlancoSauvage2018,
author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibault},
title = {The Cone of Flow Matrices: Approximation Hierarchies and Applications},
journal = {Networks},
doi = {10.1002/net.21820},
year = {2018},
volume = {72},
number = {1},
pages = {128--150},
url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-64399},
}
Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations (Guillaume Sagnol, Christoph Barner, Ralf Borndörfer, Mickaël Grima, Matthes Seeling, Claudia Spies and Klaus Wernecke)
Eur. J. Oper. Res., 271(2):420–435, 2018.
[url] DOI Bibtex
@article{SagnolBarnerBorndoerferetal.2018,
title = {Robust allocation of operating rooms: A cutting plane approach to handle lognormal case durations},
journal = {Eur. J. Oper. Res.},
year = {2018},
volume = {271},
number = {2},
pages = {420--435},
doi = {10.1016/j.ejor.2018.05.022},
author = {Sagnol, Guillaume and Barner, Christoph and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia and Wernecke, Klaus},
url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-58502},
}
Approximation Hierarchies for the Cone of Flow Matrices (Guillaume Sagnol, Marco Blanco and Thibault Sauvage)
INOC 2017 – Proc. 8th International Network Optimization Conference, pp. 275 – 284.
[url] DOI Bibtex
@inproceedings{SagnolBlancoSauvageInoc2017,
title = {Approximation Hierarchies for the Cone of Flow Matrices},
author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibault},
year = {2018},
booktitle = {INOC 2017 – Proc. 8th International Network Optimization Conference},
volume = {64},
pages = {275 -- 284},
doi = {10.1016/j.endm.2018.02.002},
series = {Electron. Notes Discret. Math.},
url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-64399},
}
The Price of Fixed Assignments in Stochastic Extensible Bin Packing (Guillaume Sagnol, Daniel Schmidt genannt Waldschmidt and Alexander Tesch)
WAOA 2018 – Proc. 16th Workshop on Approximation and Online Algorithms, pp. 327–347.
PDF DOI arxiv Bibtex
@inproceedings{SagnolSchmidtGWTesch2018,
title = {The Price of Fixed Assignments in Stochastic Extensible Bin Packing},
year = {2018},
author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Tesch, Alexander},
booktitle = {WAOA 2018 – Proc. 16th Workshop on Approximation and Online Algorithms},
volume = {11312},
pages = {327--347},
doi = {10.1007/978-3-030-04693-4_20},
arxiv = {2002.00060},
}

Optimal duty rostering for toll enforcement inspectors (Ralf Borndörfer, Guillaume Sagnol, Thomas Schlechte and Elmar Swarat)
Ann. Oper. Res., 252(2):383–406, 2017.
[url] DOI Bibtex
@article{BorndoerferSagnolSchlechteetal.2017,
author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar},
title = {Optimal duty rostering for toll enforcement inspectors},
journal = {Ann. Oper. Res.},
doi = {10.1007/s10479-016-2152-1},
year = {2017},
volume = {252},
number = {2},
pages = {383--406},
url = {https://nbn-resolving.org/urn:nbn:de:0297-zib-45107},
}

Dr. Guillaume Sagnol

Teaching

Projects

Publications

to appear

2023

2022

2021

2020

2019

2018

2017