@misc{BorndoerferSagnolSwarat, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {An IP Approach to Toll Enforcement Optimization on German Motorways}, issn = {1438-0064}, doi = {10.1007/978-3-642-29210-1_51}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14299}, number = {11-42}, abstract = {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.}, language = {en} } @misc{SagnolBlancoSauvage, 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}, 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} } @article{Sagnol, author = {Sagnol, Guillaume}, title = {On the semidefinite representation of real functions applied to symmetric matrices}, series = {Linear Algebra and its Applications}, volume = {439}, journal = {Linear Algebra and its Applications}, number = {10}, doi = {10.1016/j.laa.2013.08.021}, pages = {2829 -- 2843}, 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{Sagnol, author = {Sagnol, Guillaume}, title = {Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs}, series = {Discrete Applied Mathematics}, volume = {161}, journal = {Discrete Applied Mathematics}, number = {1-2}, doi = {10.1016/j.dam.2012.07.016}, pages = {258 -- 276}, 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} } @inproceedings{Sagnol, author = {Sagnol, Guillaume}, title = {Network-related problems in optimal experimental design and second order cone programming}, series = {Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications}, volume = {51}, booktitle = {Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications}, doi = {10.2478/v10127-012-0016-x}, pages = {161 -- 171}, 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{Sagnol, author = {Sagnol, Guillaume}, title = {A class of Semidefinite Programs with rank-one solutions}, series = {Linear Algebra and its Applications}, volume = {435}, journal = {Linear Algebra and its Applications}, number = {6}, doi = {10.1016/j.laa.2011.03.027}, pages = {1446 -- 1463}, 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} } @inproceedings{BorndoerferBuwayaSagnoletal., author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, series = {Proceedings of INOC'2013}, volume = {41}, booktitle = {Proceedings of INOC'2013}, doi = {http://dx.doi.org//10.1016/j.endm.2013.05.100}, pages = {253 -- 260}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferOmontSagnoletal., author = {Bornd{\"o}rfer, Ralf and Omont, Bertrand and Sagnol, Guillaume and Swarat, Elmar}, title = {A Stackelberg game to optimize the distribution of controls in transportation networks}, series = {Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012)}, volume = {105}, booktitle = {Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012)}, doi = {http://dx.doi.org/10.1007/978-3-642-35582-0_17}, pages = {224 -- 235}, abstract = {We propose a game theoretic model for the spatial distribution of inspectors on a transportation network. The problem is to spread out the controls so as to enforce the payment of a transit toll. We formulate a linear program to find the control distribution which maximizes the expected toll revenue, and a mixed integer program for the problem of minimizing the number of evaders. Furthermore, we show that the problem of finding an optimal mixed strategy for a coalition of \$N\$ inspectors can be solved efficiently by a column generation procedure. Finally, we give experimental results from an application to the truck toll on German motorways.}, language = {en} } @article{BorndoerferSagnolSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal duty rostering for toll enforcement inspectors}, series = {Annals of Operations Research}, volume = {252(2)}, journal = {Annals of Operations Research}, edition = {252}, publisher = {Springer US}, doi = {10.1007/s10479-016-2152-1}, pages = {383 -- 406}, abstract = {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, we developed a personalized crew rostering model, to schedule the crews of the tours. 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 main focus of this paper extends our previous publications on how different requirements for the rostering can be modeled in detail. The second focus is on a bi-criteria analysis of the planning problem to find the balance between the control quality and the roster acceptance. Finally, computational results on real-world instances show the practicability of our method and how different input parameters influence the problem complexity.}, language = {en} } @inproceedings{BorndoerferSagnolSwarat, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {An IP Approach to Toll Enforcement Optimization on German Motorways}, series = {Operations Research Proceedings 2011}, booktitle = {Operations Research Proceedings 2011}, doi = {10.1007/978-3-642-29210-1_51}, pages = {317 -- 322}, abstract = {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.}, language = {en} }