INFORMS Nashville – 2016
49
2 - Parallel Branch And Bound Revisited
Lluis-Miquel Munguia, Georgia Institute of Technology,
lluis.munguia@gatech.edu,Geoffrey Malcolm Oxberry,
Deepak Rajan
Branch and Bound (B&B) is a widely used algorithm for solving Mixed Integer
Programs (MIPs). Despite its straightforward parallelization, current B&B
implementations have shown to scale inconsistently. In this talk, we propose a
new decentralized and lightweight implementation of parallel Branch & Bound
for PIPS-SBB, a distributed-memory parallel stochastic MIP solver. In this work,
we exploit parallelism at two levels of the optimization process with the objective
of increasing parallel efficiency. We present computational results to evaluate the
effectiveness of our approach.
3 - Scalable Strategies Exploited by Parallel Nonlinear
Solver PIPS-NLP
Nai-Yuan Chiang, United Technology Research Center,
chiangn@utrc.utc.comWe present PIPS-NLP, a software library for the solution of large-scale structured
nonconvex optimization problems on high-performance computers. We focus on
linear algebra parallelization strategies and discuss how such strategies influence
the choice of algorithmic frameworks, while all the proposed approaches
guarantee global convergence. Small examples about using parallel solver PIPS-
NLP via AMPL or StructureJuMP are given, to illustrate how to exploit the
problem structures. Numerical studies from large-scale security-constrained
ACOPF and line-pack dispatch in natural gas networks also demonstrate the
robustness and efficiency of PIPS-NLP.
SB19
106B-MCC
Bilevel Programming: Methodology and Applications
Sponsored: Computing
Sponsored Session
Chair: Juan S. Borrero, University of Pittsburgh, 1012 Benedum Hall,
Pittsburgh, PA, 15261, United States,
jsb81@pitt.eduCo-Chair: M. Hosein Zare, University of Pittsburgh, 1012 Benedum
Hall, Pittsburgh, PA, 15260, United States,
moz3@pitt.edu1 - A Sampling-based Exact Approach For The Bilevel Mixed Integer
Programming Problem
Leonardo Lozano, Clemson University,
llozano@g.clemson.eduCole Smith
We examine bilevel mixed integer programs which are difficult to solve because
the leader feasible region is defined in part by optimality conditions governing the
follower variables, which are difficult to characterize because of the nonconvexity
of the follower problem. We propose an exact finite algorithm for these problems
based on an adaptive sampling scheme, and demonstrate how this algorithm can
be tailored to accommodate either optimistic or pessimistic assumptions on the
follower behavior. Computational experiments demonstrate that our approach
outperforms existing algorithms that are tailored to problems in which all
functions are assumed to be linear.
2 - On Bilevel Progams With Inexact Follower
M. Hosein Zare, University of Pittsburgh,
moz3@pitt.eduWe consider classes of bilevel programs, where the upper-level decision-maker
(i.e., the leader) needs to consider the uncertain behavior of the lower-level
decision maker (i.e., the follower). We derive some theoretical properties of the
proposed models, and illustrate our results with numerical illustrations.
3 - Reliable Vehicle Sharing Program Network Design
Ran Zhang, University of South Florida,
ranzhang@mail.usf.edu,
Bo Zeng
This talk develops a bi-level optimization model to achieve a reliable vehicle
sharing program network design. A set of numerical study will be presented to
demonstrate our design model.
4 - Sequential Max-min Bilevel Programming With Incomplete
Information And Learning
Juan S. Borrero, University of Pittsburgh,
jsb81@pitt.eduOleg A Prokopyev, Denis R. Saure
We consider an adversarial bilevel problem where the leader and follower interact
repeatedly. At each period the leader implements an upper-level solution after
which the follower reacts by solving the lower-level problem. The leader has
incomplete information about the variables, constraints, and data of the follower’s
problem, and learns about them from observing his reaction to her actions. Given
that the leader’s objective is to maximize the costs the follower incurs across all
periods, we study a set of greedy and robust decision policies that are able to find
an optimal solution to the full-information bilevel problem in finite time periods,
and moreover, are worse-case optimal.
SB20
106C-MCC
Methods and Applications of Network Sampling
Invited: Tutorial
Invited Session
Chair: Mohammad Al Hasan, Indiana University/Purdue University,
Department of Computer Science, Indianapolis, IN, 46202,
United States,
alhasan@iupui.edu1 - Methods And Applications Of Network Sampling
Mohammad Al Hasan, Indiana University/Purdue University,
Indianapolis, IN, 46202, United States,
alhasan@iupui.eduNetwork data appears in various domains, including social, communication, and
information sciences. Analysis of such data is crucial for making inferences and
predictions about these networks, and moreover, for understanding the different
processes that drive their evolution. However, a major bottleneck to perform such
an analysis is the massive size of real-life networks, which makes modeling and
analyzing these networks simply infeasible. Further, many networks, specifically,
those that belong to social and communication domains are not visible to the
public due to privacy concerns, and other networks, such as the Web, are only
accessible via crawling. Therefore, to overcome the above challenges, researchers
use network sampling overwhelmingly as a key statistical approach to select a
sub-population of interest that can be studied thoroughly. In this tutorial, we aim
to cover a diverse collection of methodologies and applications of network
sampling. We will base the discussion of network sampling in terms of population
of interest (vertices, edges, motifs), and sampling methodologies (such as
Metropolis-Hastings, random walk, and importance sampling). We will also
present a number of applications of these methods.
SB21
107A-MCC
Applications in Healthcare
Sponsored: Health Applications
Sponsored Session
Chair: Sarah Kadish, Dana-Farber Cancer Instititue, 450 Brookline Ave,
Boston, MA, 02215, United States,
sarah_kadish@dfci.harvard.edu1 - Determining The Optimal Schedule For Premixing
Chemotherapy Drugs
Donald Richardson, University of Michigan, 2753 IOE Building,
1205 Beal, Ann Arbor, MI, 48109-2117, United States,
donalric@umich.edu, Amy Cohn
In collaboration with the University of Michigan Comprehensive Cancer Center,
we have developed an optimization-based approach to improve make-ahead
policies for chemotherapy drugs for infusion patients. We first present our
optimization model. Then we present our proposed user interface to aid our
collaborators with interpreting the solutions.
2 - Operations Research Applications At A Comprehesive
Cancer Center
Victoria Jordan, University of Texas MD,
vsjordan@mdanderson.orgIndustrial and Systems Engineering is an emerging field in healthcare. The
University of Texas MD Anderson Cancer Center has Healthcare Systems
Engineers working in the Office of Performance Improvement. This session will
provide a high level overview of OR applications to improve patient flow and the
patient experience, reduce costs, and improve safety. Also presented will be more
clinical applications to improve delivery of care and the care itself.
3 - Factors That Predict Discharge Disposition At Admission
For Veterans
Nicholas Ballester, Wright State University, 207 Russ Center,
3640 Col Glenn Hwy, Dayton, OH, 45435, United States,
ballester.2@wright.edu, Pratik J Parikh
Discharge delays reduce inpatient quality of care and reverberate back through
the health care system, tying up valuable resources needed by incoming patients.
Discharge disposition, in particular, has a significant effect as different dispositions
require vastly different procedures for insurance and transportation coordination.
We have developed model to predict discharge disposition upon admission for
veterans admitted to a general internal medicine unit. This model considers
patient factors known at admission such as demographics, medical history, and
living status. Preliminary findings from a trial implementation will also be
discussed.
SB21