4 Search Results for "Sagnol, Guillaume"

Document
DOI: 10.4230/LIPIcs.SEA.2024.16
Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods

Authors: Deborah Hendrych, Mathieu Besançon, and Sebastian Pokutta

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
We tackle the Optimal Experiment Design Problem, which consists of choosing experiments to run or observations to select from a finite set to estimate the parameters of a system. The objective is to maximize some measure of information gained about the system from the observations, leading to a convex integer optimization problem. We leverage Boscia.jl, a recent algorithmic framework, which is based on a nonlinear branch-and-bound algorithm with node relaxations solved to approximate optimality using Frank-Wolfe algorithms. One particular advantage of the method is its efficient utilization of the polytope formed by the original constraints which is preserved by the method, unlike alternative methods relying on epigraph-based formulations. We assess our method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of our proposed method, especially on large and challenging instances.
Cite as

Deborah Hendrych, Mathieu Besançon, and Sebastian Pokutta. Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 16:1-16:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hendrych_et_al:LIPIcs.SEA.2024.16,
  author =	{Hendrych, Deborah and Besan\c{c}on, Mathieu and Pokutta, Sebastian},
  title =	{{Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{16:1--16:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.16},
  URN =		{urn:nbn:de:0030-drops-203810},
  doi =		{10.4230/LIPIcs.SEA.2024.16},
  annote =	{Keywords: Mixed-Integer Non-Linear Optimization, Optimal Experiment Design, Frank-Wolfe, Boscia}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.79
Restricted Adaptivity in Stochastic Scheduling

Authors: Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω((log m)/(log log m)). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an 𝒪(log log m)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.
Cite as

Guillaume Sagnol and Daniel Schmidt genannt Waldschmidt. Restricted Adaptivity in Stochastic Scheduling. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sagnol_et_al:LIPIcs.ESA.2021.79,
  author =	{Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel},
  title =	{{Restricted Adaptivity in Stochastic Scheduling}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.79},
  URN =		{urn:nbn:de:0030-drops-146603},
  doi =		{10.4230/LIPIcs.ESA.2021.79},
  annote =	{Keywords: stochastic scheduling, makespan minimzation, approximation algorithm, fixed assignment policy, non-anticipatory policy}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2019.16
Scheduling Self-Suspending Tasks: New and Old Results

Authors: Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen

Published in: LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019)

Abstract
In computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. For real-time systems, such self-suspension behavior has been shown to induce performance degradation. Hence, the researchers in the real-time systems community have devoted themselves to the design and analysis of scheduling algorithms that can alleviate the performance penalty due to self-suspension behavior. As self-suspension and delegation of parts of a job to non-bottleneck resources is pretty natural in many applications, researchers in the operations research (OR) community have also explored scheduling algorithms for systems with such suspension behavior, called the master-slave problem in the OR community. This paper first reviews the results for the master-slave problem in the OR literature and explains their impact on several long-standing problems for scheduling self-suspending real-time tasks. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems, and demonstrate that different approximation metrics can create different levels of difficulty for the approximation. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art.
Cite as

Jian-Jia Chen, Tobias Hahn, Ruben Hoeksma, Nicole Megow, and Georg von der Brüggen. Scheduling Self-Suspending Tasks: New and Old Results. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ECRTS.2019.16,
  author =	{Chen, Jian-Jia and Hahn, Tobias and Hoeksma, Ruben and Megow, Nicole and von der Br\"{u}ggen, Georg},
  title =	{{Scheduling Self-Suspending Tasks: New and Old Results}},
  booktitle =	{31st Euromicro Conference on Real-Time Systems (ECRTS 2019)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-110-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{133},
  editor =	{Quinton, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.16},
  URN =		{urn:nbn:de:0030-drops-107532},
  doi =		{10.4230/LIPIcs.ECRTS.2019.16},
  annote =	{Keywords: Self-suspension, master-slave problem, computational complexity, speedup factors}
}
Document
DOI: 10.4230/OASIcs.SCOR.2012.1
A Case Study on Optimizing Toll Enforcements on Motorways

Authors: Ralf Borndörfer, Guillaume Sagnol, and Elmar Swarat

Published in: OASIcs, Volume 22, 3rd Student Conference on Operational Research (2012)

Abstract
In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.
Cite as

Ralf Borndörfer, Guillaume Sagnol, and Elmar Swarat. A Case Study on Optimizing Toll Enforcements on Motorways. In 3rd Student Conference on Operational Research. Open Access Series in Informatics (OASIcs), Volume 22, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.SCOR.2012.1,
  author =	{Bornd\"{o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar},
  title =	{{A Case Study on Optimizing Toll Enforcements on Motorways}},
  booktitle =	{3rd Student Conference on Operational Research},
  pages =	{1--10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-39-2},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{22},
  editor =	{Ravizza, Stefan and Holborn, Penny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2012.1},
  URN =		{urn:nbn:de:0030-drops-35418},
  doi =		{10.4230/OASIcs.SCOR.2012.1},
  annote =	{Keywords: Vehicle Routing Problem, Duty Rostering, Integer Programming, Operations Research}
}
  • Refine by Author
  • 2 Sagnol, Guillaume
  • 1 Besançon, Mathieu
  • 1 Borndörfer, Ralf
  • 1 Chen, Jian-Jia
  • 1 Hahn, Tobias
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time systems
  • 1 Theory of computation → Branch-and-bound
  • 1 Theory of computation → Convex optimization
  • 1 Theory of computation → Integer programming
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Boscia
  • 1 Duty Rostering
  • 1 Frank-Wolfe
  • 1 Integer Programming
  • 1 Mixed-Integer Non-Linear Optimization
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2012
  • 1 2019
  • 1 2021
  • 1 2024

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact