TY - GEN A1 - Sagnol, Guillaume A1 - Balzer, Felix A1 - Borndörfer, Ralf A1 - Spies, Claudia A1 - von Dincklage, Falk T1 - Makespan and Tardiness in Activity Networks with Lognormal Activity Durations N2 - We propose an algorithm to approximate the distribution of the completion time (makespan) and the tardiness costs of a project, when durations are lognormally distributed. This problem arises naturally for the optimization of surgery scheduling, where it is very common to assume lognormal procedure times. We present an analogous of Clark's formulas to compute the moments of the maximum of a set of lognormal variables. Then, we use moment matching formulas to approximate the earliest starting time of each activity of the project by a shifted lognormal variable. This approach can be seen as a lognormal variant of a state-of-the-art method used for the statistical static timing analysis (SSTA) of digital circuits. We carried out numerical experiments with instances based on real data from the application to surgery scheduling. We obtained very promising results, especially for the approximation of the mean overtime in operating rooms, for which our algorithm yields results of a similar quality to Monte-Carlo simulations requiring an amount of computing time several orders of magnitude larger. T3 - ZIB-Report - 16-23 KW - scheduling KW - activity network KW - lognormal distribution Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59290 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Hege, Hans-Christian A1 - Weiser, Martin T1 - Using sparse kernels to design computer experiments with tunable precision N2 - Statistical methods to design computer experiments usually rely on a Gaussian process (GP) surrogate model, and typically aim at selecting design points (combinations of algorithmic and model parameters) that minimize the average prediction variance, or maximize the prediction accuracy for the hyperparameters of the GP surrogate. In many applications, experiments have a tunable precision, in the sense that one software parameter controls the tradeoff between accuracy and computing time (e.g., mesh size in FEM simulations or number of Monte-Carlo samples). We formulate the problem of allocating a budget of computing time over a finite set of candidate points for the goals mentioned above. This is a continuous optimization problem, which is moreover convex whenever the tradeoff function accuracy vs. computing time is concave. On the other hand, using non-concave weight functions can help to identify sparse designs. In addition, using sparse kernel approximations drastically reduce the cost per iteration of the multiplicative weights updates that can be used to solve this problem. T3 - ZIB-Report - 16-33 KW - Optimal design of computer experiments KW - Sparse kernels KW - Gaussian Process Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59605 SN - 1438-0064 ER - TY - JOUR A1 - Sagnol, Guillaume A1 - Harman, Radoslav T1 - Computing exact D-optimal designs by mixed integer second-order cone programming JF - The Annals of Statistics N2 - Let the design of an experiment be represented by an $s-$dimensional vector $w$ of weights with nonnegative components. Let the quality of $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(w)=\sum_{i=1}^s w_i A_i A_i^T$, where $A_i$,$i=1,\ldots,s$ are known matrices with $m$ rows. In this 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 exact $D-$optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second-order cone programming problems. Our results extend to the case of the criterion of $D_K-$optimality, which measures the quality of $w$ for the estimation of a linear parameter subsystem defined by a full-rank coefficient matrix $K$. We prove that some other widely used criteria are also second-order cone representable, for instance, the criteria of $A-$, $A_K$-, $G-$ and $I-$optimality. We present several numerical examples demonstrating the efficiency and general applicability 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. Y1 - 2015 U6 - https://doi.org/10.1214/15-AOS1339 VL - 43 IS - 5 SP - 2198 EP - 2224 ER - TY - CHAP A1 - Duarte, Belmiro P.M. A1 - Sagnol, Guillaume A1 - Oliveira, Nuno M.C. T1 - A Robust Minimax Semidefinite Programming Formulation for Optimal Design of Experiments for Model Parametrization T2 - 12th International Symposium on Process Systems Engineering and 25th European Symposium on Computer Aided Process Engineering N2 - Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs. Y1 - 2015 U6 - https://doi.org/10.1016/B978-0-444-63578-5.50146-8 VL - 37 SP - 905 EP - 910 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 - TY - GEN A1 - Duarte, Belmiro P.M. A1 - Sagnol, Guillaume A1 - Oliveira, Nuno M.C. T1 - A robust minimax Semidefinite Programming formulation for optimal design of experiments for model parametrization N2 - Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs. T3 - ZIB-Report - 15-03 KW - Optimal design of experiments KW - Semidefinite Programming KW - Robust minmax designs Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54626 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - Approximation of a Maximum-Submodular-Coverage problem involving spectral functions, with application to Experimental Design 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$. T3 - ZIB-Report - 11-53 KW - Maximum Coverage KW - Optimal Experimental Design KW - Polynomial Time Approximability KW - Kiefer's p-criterion Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14956 SN - 1438-0064 VL - 151 IS - 1--2 SP - 258 EP - 276 ER - TY - GEN A1 - Sagnol, Guillaume T1 - A Class of Semidefinite Programs with rank-one solutions 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. T3 - ZIB-Report - 11-51 KW - SDP KW - Semidefinite Packing Problem KW - rank 1-solution KW - Low-rank solutions KW - SOCP KW - Optimal Experimental Design KW - Multiresponse experiments Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14933 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume T1 - Network-related problems in Optimal Experimental Design and Second Order Cone Programming 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. T3 - ZIB-Report - 11-52 KW - Optimal Experimental Design KW - Second Order Cone Programming KW - Network measurements Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14942 SN - 1438-0064 VL - 51 IS - 51 SP - 161 EP - 171 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach N2 - We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented. T3 - ZIB-Report - 12-47 KW - Stackelberg Equilibrium KW - Game Theory KW - Mixed Integer Programming Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17401 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - An IP Approach to Toll Enforcement Optimization on German Motorways N2 - This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany. T3 - ZIB-Report - 11-42 KW - Toll Enforcement KW - Vehicle Routing Problem KW - Duty Roster Planning KW - Integer Programming Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14299 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - The Price of Spite in Spot-checking games N2 - We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways. T3 - ZIB-Report - 14-38 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52775 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schwartz, Stephan T1 - An Extended Network Interdiction Problem for Optimal Toll Control T2 - INOC 2015 – 7th International Network Optimization Conference N2 - We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways. Y1 - 2016 U6 - https://doi.org/10.1016/j.endm.2016.03.040 VL - 52 SP - 301 EP - 308 ER -