2016 INFORMS Annual Meeting Program

408 / 561

INFORMS Nashville – 2016
408
WB38
206A-MCC
Opt, Robust
Contributed Session
Chair: Alberto Costa, NUS, Singapore, Singapore,
1 - On The Sample Compexity Of Multistage Robust Convex
Optimization Problems
Francesca Maggioni, Assistant Professor, University of Bergamo,
Via dei Caniana n 2, Bergamo, 24127, Italy,
, Fabrizio Dabbene, Marida Bertocchi,
Roberto Tempo
In this talk probabilistic guarantees for constraint sampling of multistage robust
convex optimization problems are derived. The dynamic nature of these problems
is tackled via the scenario-with-certificates approach. This allows to avoid the
conservative use of explicit parametrizations through decision rules, and implies a
significant reduction of the sample complexity to satisfy a given level of reliability.
An explicit bound on the probability of violation is then given. Numerical results
show the efficacy of the proposed approach.
2 - Conditions Under Which Adjustability Lowers The Cost Of A
Robust Linear Program
SeyyedAli Haddadsisakht, Iowa State University, Ames, IA, 50011,
United States, Sarah M Ryan
The adjustable robust counterpart (ARC) of an uncertain linear program lets some
decision variables of the robust counterpart (RC) adjust to uncertainty. It may
produce a less conservative solution than the RC does but cases are known in
which it does not. The affinely adjustable RC (AARC) is a tractable compromise
between RC and ARC. Numerical conditions under which the AARC optimal cost
is lower than the RC optimal cost provide insight into problem structures where
adjustability is valuable.
3 - Robust Optimization For The Transportation Problem Under
Boundedly Rational User Equilibrium
Guanxiang Yun, PhD Student, University of Central Florida, 12800
Pegasus Drive, PO Box 162993, Orlando, FL, 32816, United States,
Qipeng Zheng
We proposed a model for the static transportation path problem when the
evacuation happens. We supposed that all the users in the system will obey the
bounded rational principle. In real world instances, people will feel just fine even
if they do not reach the best utility they can achieve but only attain a certain
level. We proposed totally four conditions for our static models with two of them
having the pricing strategy. By using the pricing strategy, we have a robust
optimization model, we solve it by using the column and constraint generation
method. For transportation path problem, it is also a large scale problem. In order
to solve it, we use the branch and price method.
4 - A Robust Optimization Framework For Electric Power
Grid Protection
Alberto Costa, NUS, Singapore, Singapore,
We consider a flow problem on oriented network, where the decision maker
wants to send a quantity of goods from a source to a destination node, and an
enemy can destroy the arcs of the network at a given cost. The decision maker
can use a fortification budget to increase the cost to destroy the arcs, with the goal
of maximizing the total price that the enemy must pay to disrupt the network.
We model the optimal allocation of the fortification budget as a multistage robust
optimization problem, and we propose an algorithm to find an -approximation of
the global optimum. Computational results show that the algorithm is scalable
and can solve efficiently instances with a few hundred nodes and arcs.
WB39
207A-MCC
Joint Session APS/MSOM: Service Systems in
Applied Probability I
Sponsored: Applied Probability/MSOM
Sponsored Session
Chair: Song-Hee Kim, USC Marshall School of Business,
3670 Trousdale Parkway, Los Angeles, CA, 90089, United States,
1 - Optimal Appointment Schedules
Mor Armony, New York University, ,
Rami Atar, Harsha Honnappa
We consider the problem of optimally scheduling a finite, but large, number of
customers over a finite time horizon at a single server FIFO queue, in the
presence of ‘no-shows’. We study the problem in a large population limiting
regime as the number of customers scales to infinity and the appointment
duration scales to zero. We show that in the fluid scaling heavy-traffic is obtained
as a result of asymptotic optimization. We also characterize the diffusion-scale
optimal schedule.
2 - Efficient Transition To Post-acute Care
Alex Mills, Indiana University, Bloomington, IN, United States,
, Sean Yu, Jonathan Helm
Many hospital patients are discharged to a skilled nursing facility (SNF) for post-
acute care. A shortage of SNF beds can lead to expensive discharge delays. Using a
queueing model, we show that a hospital may want to contract with a SNF to
reserve some capacity. However, when hospitals compete for capacity at multiple
SNFs, such contracting leads to an equilibrium where total SNF capacity is de-
pooled. Although this de-pooling hurts system performance overall, it benefits the
hospital with the lower discharge rate, who becomes the market leader. Under
the de-pooled scenario, the hospital with the higher arrival rate has an incentive
to finance SNF expansion, even if it leads to free-riding.
3 - Steady-state Diffusion Approximations For Discrete-time Markov
Chain In Hospital Inpatient Flow Management
Jiekun Feng, Cornell Universtiy, Ithaca, NY, United States,
, Pengyi Shi
Motivated by the recent development of steady-state approximation via Stein’s
method for Erlang-A and Erlang-C models, we apply the framework to a discrete-
time Markov chain (DTMC), which is motivated from studying hospital inpatient
flow and captures the dynamics of the midnight census in the inpatient
department. We develop diffusion models to approximate the stationary
distribution of the DTMC, and characterize the convergence rate of the
approximations.
4 - A Queueing Model For Internal Wards
Jing Dong, Northwestern University, Evanston, IL, United States,
, Ohad Perry
Hospital queues have unique features, which are not captured by standard
queueing assumptions. In this project we propose a queueing model that takes
into account the most salient features of queues associated with large Internal
Wards (IW’s). We characterize the maximum long-run workload that the IW can
handle. We also introduce a deterministic (fluid) approximation for the non-
stationary dynamics. The fluid model is shown to converge to a unique periodic
equilibrium, so that long-run performance analysis can be carried out by simply
considering that equilibrium.
WB40
207B-MCC
Queueing in Applied Probability I
Sponsored: Applied Probability
Sponsored Session
Chair: Harsha Honnappa, Purdue University, 315 N. Grant St.,
West Lafayette, IN, 47906, United States,
1 - Randomized Load Balancing With General Service Distributions
Kavita Ramanan, Brown University,
Randomized algorithms are used in a variety of applications to balance load to
improve performance. Randomized load balancing algorithms with exponential
service distributions have received much attention, but in practice job sizes have
been observed to be non-exponential. We characterize equilibrium properties of
fluid limits of several randomized load balancing algorithms, including the well-
known “power of two choices” algorithm in the presence of general service
distributions. This is joint work with Pooja Agarwal.
2 - Beyond Heavy-traffic Regimes: Universal Bounds And Controls
For The Single-server Queue
Itai Gurvich, Kellogg School of Management,
Junfei Huang
Brownian approximations provide tractability in the analysis of queues. Their
stationary distributions are used as proxies for those of the original queues and
the convergence of suitably scaled primitives and processes provides mathematical
support for the use of these Brownian models. From a heuristic viewpoint,
however, there is an immediate Brownian analogue of the queueing model that is
derived directly from the primitives. For the M/GI/1+GI queue, this direct
(limitless approach) works: the Brownian model is universally accurate. It
maintains the tractability and appeal of the limit approximations while avoiding
many of the assumptions that facilitate them.
WB38