90Cxx Mathematical programming [See also 49Mxx, 65Kxx]
Refine
Document Type
- ZIB-Report (4) (remove)
Language
- English (4)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Keywords
Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue.
First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library.
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.
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.
The steel mill slab design problem from the CSPLIB is a combinatorial
optimization problem motivated by an application of the steel industry. It
has been widely studied in the constraint programming community. Several
methods were proposed to solve this problem. A steel mill slab library was
created which contains 380 instances. A closely related binpacking problem
called the multiple knapsack problem with color constraints, originated
from the same industrial problem, was discussed in the integer programming
community. In particular, a simple integer program for this problem has
been given by Forrest et al. The aim of this paper is to bring these
different studies together. Moreover, we adapt the model of Forrest et
al. for the steel mill slab design problem. Using this model and a
state-of-the-art integer program solver all instances of the steel mill
slab library can be solved efficiently to optimality. We improved,
thereby, the solution values of 76 instances compared to previous results.
Finally, we consider a recently introduced variant of the steel mill slab
design problem, where within all solutions which minimize the leftover one
is interested in a solution which requires a minimum number of slabs. For
that variant we introduce two approaches and solve all instances of the
steel mill slab library with this slightly changed objective function to
optimality.