TY - JOUR A1 - Sagnol, Guillaume A1 - Pauwels, Edouard T1 - An unexpected connection between Bayes A-optimal designs and the group lasso JF - Statistical Papers N2 - We show that the A-optimal design optimization problem over m design points in R^n is equivalent to minimizing a quadratic function plus a group lasso sparsity inducing term over n x m real matrices. This observation allows to describe several new algorithms for A-optimal design based on splitting and block coordinate decomposition. These techniques are well known and proved powerful to treat large scale problems in machine learning and signal processing communities. The proposed algorithms come with rigorous convergence guarantees and convergence rate estimate stemming from the optimization literature. Performances are illustrated on synthetic benchmarks and compared to existing methods for solving the optimal design problem. Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73059 VL - 60 IS - 2 SP - 215 EP - 234 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 - Duarte, Belmiro P.M. A1 - Sagnol, Guillaume A1 - Wong, Weng Kee T1 - An algorithm based on Semidefinite Programming for finding minimax optimal designs N2 - An algorithm based on a delayed constraint generation method for solving semi-infinite programs for constructing minimax optimal designs for nonlinear models is proposed. The outer optimization level of the minimax optimization problem is solved using a semidefinite programming based approach that requires the design space be discretized. A nonlinear programming solver is then used to solve the inner program to determine the combination of the parameters that yields the worst-case value of the design criterion. The proposed algorithm is applied to find minimax optimal designs for the logistic model, the flexible 4-parameter Hill homoscedastic model and the general nth order consecutive reaction model, and shows that it (i) produces designs that compare well with minimax $D-$optimal designs obtained from semi-infinite programming method in the literature; (ii) can be applied to semidefinite representable optimality criteria, that include the common A-, E-,G-, I- and D-optimality criteria; (iii) can tackle design problems with arbitrary linear constraints on the weights; and (iv) is fast and relatively easy to use. T3 - ZIB-Report - 18-01 KW - Cutting plane algorithm KW - Design efficiency KW - Equivalence theorem KW - Model-based optimal design KW - Nonlinear programming Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66249 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Blanco, Marco A1 - Sauvage, Thibaut T1 - The Cone of Flow Matrices: Approximation Hierarchies and Applications 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. T3 - ZIB-Report - 17-32 KW - Flows in graphs KW - Approximation Hierarchies KW - Copositive Programming KW - Semidefinite Programming Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64399 SN - 1438-0064 ER - TY - GEN A1 - Duarte, Belmiro P.M. A1 - Sagnol, Guillaume T1 - Approximate and exact D-optimal designs for $2^k$ factorial experiments for Generalized Linear Models via SOCP N2 - We propose (Mixed Integer) Second Order Cone Programming formulations to find approximate and exact $D-$optimal designs for $2^k$ factorial experiments for Generalized Linear Models (GLMs). Locally optimal designs are addressed with Second Order Cone Programming (SOCP) and Mixed Integer Second Order Cone Programming (MISOCP) formulations. The formulations are extended for scenarios of parametric uncertainty employing the Bayesian framework for \emph{log det} $D-$optimality criterion. A quasi Monte-Carlo sampling procedure based on the Hammersley sequence is used for integrating the optimality criterion in the parametric region. The problems are solved in \texttt{GAMS} environment using \texttt{CPLEX} solver. We demonstrate the application of the algorithm with the logistic, probit and complementary log-log models and consider full and fractional factorial designs. T3 - ZIB-Report - 18-02 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66256 SN - 1438-0064 ER - TY - JOUR A1 - Duarte, Belmiro A1 - Sagnol, Guillaume T1 - Approximate and exact optimal designs for 2^k factorial experiments for generalized linear models via second order cone programming JF - Statistical Papers N2 - Model-based optimal designs of experiments (M-bODE) for nonlinear models are typically hard to compute. The literature on the computation of M-bODE for nonlinear models when the covariates are categorical variables, i.e. factorial experiments, is scarce. We propose second order cone programming (SOCP) and Mixed Integer Second Order Programming (MISOCP) formulations to find, respectively, approximate and exact A- and D-optimal designs for 2𝑘 factorial experiments for Generalized Linear Models (GLMs). First, locally optimal (approximate and exact) designs for GLMs are addressed using the formulation of Sagnol (J Stat Plan Inference 141(5):1684–1708, 2011). Next, we consider the scenario where the parameters are uncertain, and new formulations are proposed to find Bayesian optimal designs using the A- and log det D-optimality criteria. A quasi Monte-Carlo sampling procedure based on the Hammersley sequence is used for computing the expectation in the parametric region of interest. We demonstrate the application of the algorithm with the logistic, probit and complementary log–log models and consider full and fractional factorial designs. Y1 - 2020 U6 - https://doi.org/10.1007/s00362-018-01075-7 VL - 61 SP - 2737 EP - 2767 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Tesch, Alexander A1 - Sagnol, Guillaume T1 - Algorithmen unterstützen OP-Planung T2 - Management & Krankenhaus N2 - Mathematische Algorithmen können durch Vorhersage von Unsicherheiten optimierte OP-Pläne berechnen, sodass mehrere Zielkriterien wie Überstunden, Wartezeit und Ausfälle im OP minimiert werden. Y1 - 2019 IS - 12 SP - 20 PB - Wiley ER - 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 - 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 - 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 - 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 - CHAP A1 - Sagnol, Guillaume A1 - Hege, Hans-Christian A1 - Weiser, Martin T1 - Using sparse kernels to design computer experiments with tunable precision T2 - 22nd Intern. Conf. on Computational Statistics - COMPSTAT 2016, Oviedo, Spain, 23-26 August 2016, Proceedings ISBN 978-90-73592-36-0 Y1 - 2016 SP - 397 EP - 408 ER - TY - CHAP A1 - Sagnol, Guillaume T1 - Network-related problems in optimal experimental design and second order cone programming T2 - Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications N2 - In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results. Y1 - 2012 U6 - https://doi.org/10.2478/v10127-012-0016-x VL - 51 SP - 161 EP - 171 ER - TY - JOUR A1 - Sagnol, Guillaume T1 - On the semidefinite representation of real functions applied to symmetric matrices JF - Linear Algebra and its Applications N2 - We present a new semidefinite representation for the trace of a real function f applied to symmetric matrices, when a semidefinite representation of the convex function f is known. Our construction is intuitive, and yields a representation that is more compact than the previously known one. We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices that for a rational number p in the interval (0,1], the matrix X raised to the exponent p is the largest element of a set represented by linear matrix inequalities. We give numerical results for a problem inspired from the theory of experimental designs, which show that the new semidefinite programming formulation yields a speed-up factor in the order of 10. Y1 - 2013 U6 - https://doi.org/10.1016/j.laa.2013.08.021 VL - 439 IS - 10 SP - 2829 EP - 2843 ER - TY - JOUR A1 - Sagnol, Guillaume T1 - Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs JF - Discrete Applied Mathematics N2 - We study a family of combinatorial optimization problems defined by a parameter $p\in[0,1]$, which involves spectral functions applied to positive semidefinite matrices, and has some application in the theory of optimal experimental design. This family of problems tends to a generalization of the classical maximum coverage problem as $p$ goes to $0$, and to a trivial instance of the knapsack problem as $p$ goes to $1$. In this article, we establish a matrix inequality which shows that the objective function is submodular for all $p\in[0,1]$, from which it follows that the greedy approach, which has often been used for this problem, always gives a design within $1-1/e$ of the optimum. We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors. We prove an inequality which generalizes a classical result from the theory of optimal designs, and allows us to give a rounding procedure with an approximation factor which tends to $1$ as $p$ goes to $1$. Y1 - 2013 U6 - https://doi.org/10.1016/j.dam.2012.07.016 VL - 161 IS - 1-2 SP - 258 EP - 276 ER - TY - JOUR A1 - Sagnol, Guillaume T1 - A class of Semidefinite Programs with rank-one solutions JF - Linear Algebra and its Applications N2 - We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite matrix of rank at most $r$, where $r$ is the rank of the matrix involved in the objective function of the SDP. The optimization problems of this class are semidefinite packing problems, which are the SDP analogs to vector packing problems. Of particular interest is the case in which our result guarantees the existence of a solution of rank one: we show that the computation of this solution actually reduces to a Second Order Cone Program (SOCP). We point out an application in statistics, in the optimal design of experiments. Y1 - 2011 U6 - https://doi.org/10.1016/j.laa.2011.03.027 VL - 435 IS - 6 SP - 1446 EP - 1463 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Harman, Radoslav T1 - Computing exact D-optimal designs by mixed integer second order cone programming N2 - Let the design of an experiment be represented by an $s$-dimensional vector $\vec{w}$ of weights with non-negative components. Let the quality of $\vec{w}$ for the estimation of the parameters of the statistical model be measured by the criterion of $D$-optimality defined as the $m$-th root of the determinant of the information matrix $M(\vec{w})=\sum_{i=1}^s w_iA_iA_i^T$, where $A_i$, $i=1,...,s$, are known matrices with $m$ rows. In the paper, we show that the criterion of $D$-optimality is second-order cone representable. As a result, the method of second order cone programming can be used to compute an approximate $D$-optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an \emph{exact} $D$-optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second order cone problems. We prove that some other widely used criteria are also second order cone representable, for instance the criteria of $A$-, and $G$-optimality, as well as the criteria of $D_K$- and $A_K$-optimality, which are extensions of $D$-, and $A$-optimality used in the case when only a specific system of linear combinations of parameters is of interest. We present several numerical examples demonstrating the efficiency and universality of the proposed method. We show that in many cases the mixed integer second order cone programming approach allows us to find a provably optimal exact design, while the standard heuristics systematically miss the optimum. T3 - ZIB-Report - 13-39 KW - Optimal Design of Experiments KW - D-optimality KW - SOCP Representability KW - Exact Designs Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41932 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Barner, Christoph A1 - Borndörfer, Ralf A1 - Grima, Mickaël A1 - Seeling, Matthes A1 - Spies, Claudia A1 - Wernecke, Klaus T1 - Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations 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. T3 - ZIB-Report - 16-18 KW - robust optimization KW - lognormal duration KW - Hilbert's projective metric Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-58502 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Grima, Mickaël A1 - Seeling, Matthes A1 - Spies, Claudia T1 - Robust Allocation of Operating Rooms with Lognormal case Durations N2 - The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. In this article, we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution. We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations to solve the subproblems that identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based on real data from a major hospital in Berlin. T3 - ZIB-Report - 16-16 KW - robust optimization KW - lognormal duration KW - Hilbert's projective metric Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-58497 UR - http://www.pms2016.com/congreso/ficha.en.html SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - Picos Documentation. Release 0.1.1. N2 - PICOS is a user friendly interface to several conic and integer programming solvers, very much like YALMIP under MATLAB. The main motivation for PICOS is to have the possibility to enter an optimization problem as a high level model, and to be able to solve it with several different solvers. Multidimensional and matrix variables are handled in a natural fashion, which makes it painless to formulate a SDP or a SOCP. This is very useful for educational purposes, and to quickly implement some models and test their validity on simple examples. Furthermore, with PICOS you can take advantage of the python programming language to read and write data, construct a list of constraints by using python list comprehensions, take slices of multidimensional variables, etc. T3 - ZIB-Report - 12-48 KW - mathematical programming KW - SDP KW - SOCP KW - python Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17396 SN - 1438-0064 ER -