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)
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.
We consider the stochastic scheduling problem of minimizing the expected makespan on m parallel identical machines. While the (adaptive) list scheduling policy achieves an approximation ratio of 2, any (non-adaptive) fixed assignment policy has performance guarantee Ω(logm/loglogm). Although the performance of the latter class of policies are worse, there are applications in which non-adaptive policies are desired. In this work, we introduce the two classes of δ-delay and τ-shift policies whose degree of adaptivity can be controlled by a parameter. We present a policy - belonging to both classes - which is an O(loglogm)-approximation for reasonably bounded parameters. In other words, an exponential improvement on the performance of any fixed assignment policy can be achieved when allowing a small degree of adaptivity. Moreover, we provide a matching lower bound for any δ-delay and τ-shift policy when both parameters, respectively, are in the order of the expected makespan of an optimal non-anticipatory policy.
Model-based optimal designs of experiments (M-bODE) for nonlinear models are typically hard to compute. The literature on the computation of M-bODE for nonlinear models when the covariates are categorical variables, i.e. factorial experiments, is scarce. We propose second order cone programming (SOCP) and Mixed Integer Second Order Programming (MISOCP) formulations to find, respectively, approximate and exact A- and D-optimal designs for 2𝑘 factorial experiments for Generalized Linear Models (GLMs). First, locally optimal (approximate and exact) designs for GLMs are addressed using the formulation of Sagnol (J Stat Plan Inference 141(5):1684–1708, 2011). Next, we consider the scenario where the parameters are uncertain, and new formulations are proposed to find Bayesian optimal designs using the A- and log det D-optimality criteria. A quasi Monte-Carlo sampling procedure based on the Hammersley sequence is used for computing the expectation in the parametric region of interest. We demonstrate the application of the algorithm with the logistic, probit and complementary log–log models and consider full and fractional factorial designs.
We show that the A-optimal design optimization problem over m design points in R^n is equivalent to minimizing a quadratic function plus a group lasso sparsity inducing term over n x m real matrices. This observation allows to describe several new algorithms for A-optimal design based on splitting and block coordinate decomposition. These techniques are well known and proved powerful to treat large scale problems in machine learning and signal processing communities. The proposed algorithms come with rigorous convergence guarantees and convergence rate estimate stemming from the optimization literature. Performances are illustrated on synthetic benchmarks and compared to existing methods for solving the optimal design problem.
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.
Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations
(2018)
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.
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.
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, the number of bins is fixed and they 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+e−1)≈1.368 under a reasonable assumption on the distributions of job durations.
Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, 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 $\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.
An algorithm based on a delayed constraint generation method for solving semi-infinite programs
for constructing minimax optimal designs for nonlinear models is proposed. The outer optimization level of the minimax
optimization problem is solved using a semidefinite programming based approach that requires
the design space be discretized. A nonlinear programming solver is then used to solve the inner program
to determine the combination of the parameters that yields the worst-case value of the design criterion.
The proposed algorithm is applied to find minimax optimal designs for the logistic model, the flexible 4-parameter
Hill homoscedastic model and the general nth order consecutive reaction model, and shows that it
(i) produces designs that compare well with minimax $D-$optimal designs obtained from semi-infinite programming method in the literature;
(ii) can be applied to semidefinite representable optimality criteria, that include the common A-, E-,G-, I- and D-optimality criteria;
(iii) can tackle design problems with arbitrary linear constraints on the weights; and
(iv) is fast and relatively easy to use.
We propose (Mixed Integer) Second Order Cone Programming formulations to find approximate and exact $D-$optimal designs for $2^k$
factorial experiments for Generalized Linear Models (GLMs). Locally optimal designs are addressed with Second Order Cone Programming
(SOCP) and Mixed Integer Second Order Cone Programming (MISOCP) formulations.
The formulations are extended for scenarios of parametric uncertainty employing the Bayesian framework for
\emph{log det} $D-$optimality criterion. A quasi Monte-Carlo sampling procedure based
on the Hammersley sequence is used for integrating the optimality criterion in the parametric region. The problems are solved in \texttt{GAMS}
environment using \texttt{CPLEX} solver. We demonstrate the application of the algorithm with the logistic, probit and complementary log-log models
and consider full and fractional factorial designs.
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.