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 - 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 - CHAP A1 - Borndörfer, Ralf A1 - Buwaya, Julia A1 - Sagnol, Guillaume A1 - Swarat, Elmar T1 - Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach T2 - Proceedings of INOC'2013 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. Y1 - 2013 U6 - https://doi.org/http://dx.doi.org//10.1016/j.endm.2013.05.100 VL - 41 SP - 253 EP - 260 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering N2 - We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method. T3 - ZIB-Report - 13-79 KW - vehicle routing KW - crew rostering KW - integer programming KW - bicriteria optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-45107 SN - 1438-0064 ER -