### Refine

#### Year of publication

#### Document Type

- ZIB-Report (26)
- In Proceedings (13)
- Article (12)
- Other (1)

#### Is part of the Bibliography

- no (52)

#### Keywords

- Optimal Experimental Design (3)
- SDP (3)
- Flows in graphs (2)
- Game Theory (2)
- Hilbert's projective metric (2)
- Integer Programming (2)
- Mixed Integer Programming (2)
- SOCP (2)
- Semidefinite Programming (2)
- Stackelberg Equilibrium (2)

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.

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.

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.

In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour
planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network
and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to
feasible rosters for one month. We present computational results in a
case-study on a German subnetwork which documents the practicability of our approach.

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.

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.

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.

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$.

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.

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.