### Refine

#### Document Type

- ZIB-Report (26)
- In Proceedings (13)
- Article (9)

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

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.

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

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.

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.

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.