@article{SagnolPauwels2019, author = {Sagnol, Guillaume and Pauwels, Edouard}, title = {An unexpected connection between Bayes A-optimal designs and the group lasso}, volume = {60}, journal = {Statistical Papers}, number = {2}, doi = {10.1007/s00362-018-01062-y}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73059}, pages = {215 -- 234}, year = {2019}, abstract = {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.}, language = {en} } @inproceedings{SagnolSchmidtgenanntWaldschmidtTesch2018, author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Tesch, Alexander}, title = {The Price of Fixed Assignments in Stochastic Extensible Bin Packing}, volume = {11312}, booktitle = {WAOA 2018: Approximation and Online Algorithms}, doi = {10.1007/978-3-030-04693-4_20}, pages = {327 -- 347}, year = {2018}, abstract = {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.}, language = {en} } @misc{DuarteSagnolWong2017, author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Wong, Weng Kee}, title = {An algorithm based on Semidefinite Programming for finding minimax optimal designs}, issn = {1438-0064}, doi = {10.1016/j.csda.2017.09.008}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66249}, year = {2017}, abstract = {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.}, language = {en} } @misc{SagnolBlancoSauvage2017, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {The Cone of Flow Matrices: Approximation Hierarchies and Applications}, issn = {1438-0064}, doi = {10.1002/net.21820}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64399}, year = {2017}, abstract = {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.}, language = {en} } @misc{DuarteSagnol2017, 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}, issn = {1438-0064}, doi = {10.1007/s00362-018-01075-7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66256}, year = {2017}, abstract = {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.}, language = {en} } @article{DuarteSagnol2020, author = {Duarte, Belmiro and Sagnol, Guillaume}, title = {Approximate and exact optimal designs for 2^k factorial experiments for generalized linear models via second order cone programming}, volume = {61}, journal = {Statistical Papers}, doi = {10.1007/s00362-018-01075-7}, pages = {2737 -- 2767}, year = {2020}, abstract = {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.}, language = {en} } @misc{BorndoerferTeschSagnol2019, author = {Bornd{\"o}rfer, Ralf and Tesch, Alexander and Sagnol, Guillaume}, title = {Algorithmen unterst{\"u}tzen OP-Planung}, journal = {Management \& Krankenhaus}, number = {12}, publisher = {Wiley}, pages = {20}, year = {2019}, abstract = {Mathematische Algorithmen k{\"o}nnen durch Vorhersage von Unsicherheiten optimierte OP-Pl{\"a}ne berechnen, sodass mehrere Zielkriterien wie {\"U}berstunden, Wartezeit und Ausf{\"a}lle im OP minimiert werden.}, language = {de} } @misc{SagnolSchmidtgenanntWaldschmidtTesch2018, author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Tesch, Alexander}, title = {The Price of Fixed Assignments in Stochastic Extensible Bin Packing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68415}, year = {2018}, abstract = {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.}, language = {en} } @article{SagnolBlancoSauvage2018, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {The Cone of Flow Matrices: Approximation Hierarchies and Applications}, volume = {72}, journal = {Networks}, number = {1}, doi = {10.1002/net.21820}, pages = {128 -- 150}, year = {2018}, abstract = {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.}, language = {en} } @misc{SagnolBlancoSauvage2018, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {Approximation Hierarchies for the cone of flow matrices}, issn = {1438-0064}, doi = {10.1016/j.endm.2018.02.002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68424}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{SagnolBlancoSauvage2018, author = {Sagnol, Guillaume and Blanco, Marco and Sauvage, Thibaut}, title = {Approximation Hierarchies for the cone of flow matrices}, volume = {64}, booktitle = {INOC 2017 - 8th International Network Optimization Conference}, doi = {10.1016/j.endm.2018.02.002}, pages = {275 -- 284}, year = {2018}, abstract = {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.}, language = {en} } @article{SagnolBarnerBorndoerferetal.2018, author = {Sagnol, Guillaume and Barner, Christoph and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Mathes and Spies, Claudia and Wernecke, Klaus}, title = {Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations}, volume = {271}, journal = {European Journal of Operational Research}, number = {2}, doi = {10.1016/j.ejor.2018.05.022}, pages = {420 -- 435}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{SagnolHegeWeiser2016, author = {Sagnol, Guillaume and Hege, Hans-Christian and Weiser, Martin}, title = {Using sparse kernels to design computer experiments with tunable precision}, booktitle = {22nd Intern. Conf. on Computational Statistics - COMPSTAT 2016, Oviedo, Spain, 23-26 August 2016, Proceedings ISBN 978-90-73592-36-0}, pages = {397 -- 408}, year = {2016}, language = {en} } @inproceedings{Sagnol2012, author = {Sagnol, Guillaume}, title = {Network-related problems in optimal experimental design and second order cone programming}, volume = {51}, booktitle = {Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications}, doi = {10.2478/v10127-012-0016-x}, pages = {161 -- 171}, year = {2012}, abstract = {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.}, language = {en} } @article{Sagnol2013, author = {Sagnol, Guillaume}, title = {On the semidefinite representation of real functions applied to symmetric matrices}, volume = {439}, journal = {Linear Algebra and its Applications}, number = {10}, doi = {10.1016/j.laa.2013.08.021}, pages = {2829 -- 2843}, year = {2013}, abstract = {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.}, language = {en} } @article{Sagnol2013, author = {Sagnol, Guillaume}, title = {Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs}, volume = {161}, journal = {Discrete Applied Mathematics}, number = {1-2}, doi = {10.1016/j.dam.2012.07.016}, pages = {258 -- 276}, year = {2013}, abstract = {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\$.}, language = {en} } @article{Sagnol2011, author = {Sagnol, Guillaume}, title = {A class of Semidefinite Programs with rank-one solutions}, volume = {435}, journal = {Linear Algebra and its Applications}, number = {6}, doi = {10.1016/j.laa.2011.03.027}, pages = {1446 -- 1463}, year = {2011}, abstract = {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.}, language = {en} } @misc{SagnolHarman2013, author = {Sagnol, Guillaume and Harman, Radoslav}, title = {Computing exact D-optimal designs by mixed integer second order cone programming}, issn = {1438-0064}, doi = {10.1214/15-AOS1339}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-41932}, year = {2013}, abstract = {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.}, language = {en} } @misc{SagnolBarnerBorndoerferetal.2016, 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}, title = {Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations}, issn = {1438-0064}, doi = {10.1016/j.ejor.2018.05.022}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-58502}, year = {2016}, abstract = {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.}, language = {en} } @misc{SagnolBorndoerferGrimaetal.2016, author = {Sagnol, Guillaume and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia}, title = {Robust Allocation of Operating Rooms with Lognormal case Durations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-58497}, year = {2016}, abstract = {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.}, language = {en} } @misc{Sagnol2012, author = {Sagnol, Guillaume}, title = {Picos Documentation. Release 0.1.1.}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17396}, year = {2012}, abstract = {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.}, language = {en} }