Refine
Year of publication
Document Type
- ZIB-Report (26)
- Article (13)
- In Proceedings (13)
- Other (1)
Is part of the Bibliography
- no (53)
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)
Institute
- Mathematical Optimization (52)
- Mathematics of Transportation and Logistics (28)
- Mathematics of Health Care (16)
- Network Optimization (2)
- Visual Data Analysis (2)
- Visual and Data-centric Computing (2)
- Computational Medicine (1)
- Numerical Mathematics (1)
- Visual Data Analysis in Science and Engineering (1)
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.
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.
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.
Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations
(2016)
The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects
and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution,
and a fixed assignment of jobs to machines must be computed.
We propose a cutting-plane approach to solve the robust counterpart of this optimization problem.
To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities.
The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions.
We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which
only approximation approaches were known. Our model can
be extended to balance the load over several planning periods in a rolling horizon.
We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that:
(i) our approach performs well compared to a previous model that ignored the distribution of case durations;
(ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost;
(iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available.
Finally, we draw a number of managerial implications from these observations.
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 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 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.
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 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.
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 consider the stochastic extensible bin packing problem (SEBP) in which $n$ items of stochastic size are packed into $m$ bins of unit capacity. In contrast to the classical bin packing problem, bins can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible.
This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of $2$. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of $1+1/e \approx 1.368$ under a reasonable assumption on the distributions of job durations.
Furthermore, we prove that the price of fixed assignments, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for.
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.
A design point is inessential when it does not contribute to an optimal design, and can therefore be safely discarded from the design space. We derive three inequalities for the detection of such inessential points in c-optimal design: the first two are direct consequences of the equivalence theorem for c-optimality; the third one is derived from a second-order cone programming formulation of c-optimal design. Elimination rules for A-optimal design are obtained as a byproduct. When implemented within an optimization algorithm, each inequality gives a screening test that may provide a substantial acceleration by reducing the size of the problem online. Several examples are presented with a multiplicative algorithm to illustrate the effectiveness of the approach.