Refine
Document Type
- ZIB-Report (11)
- In Proceedings (10)
- Article (7)
Language
- English (28)
Is part of the Bibliography
- no (28)
Keywords
Institute
- Mathematics of Transportation and Logistics (28) (remove)
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.
We consider a stationary discrete-time linear process that can be observed by a finite number of sensors.
The experimental design for the observations consists of an allocation of available resources to these sensors.
We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter,
with respect to a standard optimality criterion, such as $D-$ or $A-$optimality.
This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors.
Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming.
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.
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.
We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.
We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.
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.
We consider a stationary discrete-time linear process that can be observed by a finite number of sensors. The experimental design for the observations consists of an allocation of available resources to these sensors. We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter, with respect to a standard optimality criterion, such as $D-$ or $A-$optimality. This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors. Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming.
Network spot-checking games: Theory and application to toll enforcing in transportation networks
(2015)
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. In an SC game, the pure strategies of network users correspond to paths in a graph, and the pure strategies of the inspectors are subset of arcs to be controlled. 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 (SSE) is more relevant for this problem and we give a mixed integer programming (MIP) formulation for this problem. We show that the computation of such an equilibrium is NP-hard. More generally, we prove that it is NP-hard to compute a SSE in a polymatrix game, even if the game is pairwise zero-sum. Then, we give some bounds on the price of spite, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we report computational experiments on instances constructed from real data, for an application to the enforcement of a truck toll in Germany. These numerical results show the efficiency of the proposed methods, as well as the quality of the bounds derived in this article.
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.
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.
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.
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.
The problem of allocating operating rooms (OR) to surgical cases is a challenging task,
involving both combinatorial aspects and uncertainty handling. In this article,
we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution.
We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end,
we develop an algorithm based on fixed-point iterations to solve the subproblems that
identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based
on real data from a major hospital in Berlin.
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.
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 $1_P 1_P^T \in R^{n\times n}$, where
$1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$.
Several combinatorial problems reduce to a linear optimization problem over $K$.
This cone is intractable, but 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 a maximum flow problem with pairwise arc-capacities.
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 $1_P 1_P^T \in R^{n\times n}$, where
$1_P\in R^n$ is the incidence vector of the $(s,t)$-path $P$.
Several combinatorial problems reduce to a linear optimization problem over $K$.
This cone is intractable, but 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 a maximum flow problem with pairwise arc-capacities.
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.