TY - GEN A1 - Sagnol, Guillaume A1 - Schmidt genannt Waldschmidt, Daniel A1 - Tesch, Alexander T1 - The Price of Fixed Assignments in Stochastic Extensible Bin Packing N2 - We consider the stochastic extensible bin packing problem (SEBP) in which $n$ items of stochastic size are packed into $m$ bins of unit capacity. In contrast to the classical bin packing problem, bins can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of $2$. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of $1+1/e \approx 1.368$ under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for. T3 - ZIB-Report - 18-19 KW - Approximation Algorithms KW - Stochastic Scheduling KW - Extensible Bin Packing Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68415 SN - 1438-0064 ER - TY - CHAP A1 - Sagnol, Guillaume A1 - Schmidt genannt Waldschmidt, Daniel A1 - Tesch, Alexander T1 - The Price of Fixed Assignments in Stochastic Extensible Bin Packing T2 - WAOA 2018: Approximation and Online Algorithms N2 - We consider the stochastic extensible bin packing problem (SEBP) in which n items of stochastic size are packed into m bins of unit capacity. In contrast to the classical bin packing problem, the number of bins is fixed and they can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of 2. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of (1+e−1)≈1.368 under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-030-04693-4_20 VL - 11312 SP - 327 EP - 347 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Blanco, Marco A1 - Sauvage, Thibaut T1 - Approximation Hierarchies for the cone of flow matrices N2 - Let $G$ be a directed acyclic graph with $n$ arcs, a source $s$ and a sink $t$. We introduce the cone $K$ of flow matrices, which is a polyhedral cone generated by the matrices $1_P 1_P^T \in R^{n\times n}$, where $1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$. Several combinatorial problems reduce to a linear optimization problem over $K$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of $K$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities. T3 - ZIB-Report - 18-20 KW - Flows in graphs KW - Approximation hierarchies KW - Copositive programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68424 SN - 1438-0064 ER - TY - CHAP A1 - Sagnol, Guillaume A1 - Blanco, Marco A1 - Sauvage, Thibaut T1 - Approximation Hierarchies for the cone of flow matrices T2 - INOC 2017 – 8th International Network Optimization Conference N2 - Let $G$ be a directed acyclic graph with $n$ arcs, a source $s$ and a sink $t$. We introduce the cone $K$ of flow matrices, which is a polyhedral cone generated by the matrices $1_P 1_P^T \in R^{n\times n}$, where $1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$. Several combinatorial problems reduce to a linear optimization problem over $K$. This cone is intractable, but we provide two convergent approximation hierarchies, one of them based on a completely positive representation of $K$. We illustrate this approach by computing bounds for a maximum flow problem with pairwise arc-capacities. Y1 - 2018 U6 - https://doi.org/10.1016/j.endm.2018.02.002 VL - 64 SP - 275 EP - 284 ER - TY - JOUR A1 - Sagnol, Guillaume A1 - Blanco, Marco A1 - Sauvage, Thibaut T1 - The Cone of Flow Matrices: Approximation Hierarchies and Applications JF - Networks N2 - Let G be a directed acyclic graph with n arcs, a source s and a sink t. We introduce the cone K of flow matrices, which is a polyhedral cone generated by the matrices $\vec{1}_P\vec{1}_P^T\in\RR^{n\times n}$, where $\vec{1}_P\in\RR^n$ is the incidence vector of the (s,t)-path P. We show that several hard flow (or path) optimization problems, that cannot be solved by using the standard arc-representation of a flow, reduce to a linear optimization problem over $\mathcal{K}$. This cone is intractable: we prove that the membership problem associated to $\mathcal{K}$ is NP-complete. However, the affine hull of this cone admits a nice description, and we give an algorithm which computes in polynomial-time the decomposition of a matrix $X\in \operatorname{span} \mathcal{K}$ as a linear combination of some $\vec{1}_P\vec{1}_P^T$'s. Then, we provide two convergent approximation hierarchies, one of them based on a completely positive representation of~K. We illustrate this approach by computing bounds for the quadratic shortest path problem, as well as a maximum flow problem with pairwise arc-capacities. Y1 - 2018 U6 - https://doi.org/10.1002/net.21820 VL - 72 IS - 1 SP - 128 EP - 150 ER - TY - JOUR A1 - Sagnol, Guillaume A1 - Barner, Christoph A1 - Borndörfer, Ralf A1 - Grima, Mickaël A1 - Seeling, Mathes A1 - Spies, Claudia A1 - Wernecke, Klaus T1 - Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations JF - European Journal of Operational Research N2 - The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution, and a fixed assignment of jobs to machines must be computed. We propose a cutting-plane approach to solve the robust counterpart of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions. We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which only approximation approaches were known. Our model can be extended to balance the load over several planning periods in a rolling horizon. We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that: (i) our approach performs well compared to a previous model that ignored the distribution of case durations; (ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost; (iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available. Finally, we draw a number of managerial implications from these observations. Y1 - 2018 U6 - https://doi.org/10.1016/j.ejor.2018.05.022 VL - 271 IS - 2 SP - 420 EP - 435 ER - TY - JOUR A1 - Duarte, Belmiro P.M. A1 - Sagnol, Guillaume A1 - Wong, Weng Kee T1 - An algorithm based on Semidefinite Programming for finding minimax optimal designs JF - Computational Statistics & Data Analysis Y1 - 2018 U6 - https://doi.org/10.1016/j.csda.2017.09.008 VL - 119 SP - 99 EP - 117 ER -