Informs 2015

238 / 552

INFORMS Philadelphia – 2015
236
MD13
13-Franklin 3, Marriott
Stochastic Integer Programming
Sponsor: Optimization/Optimization Under Uncertainty
Sponsored Session
Chair: Kibaek Kim, Argonne National Laboratory, 9700 South Cass
Avenue, Argonne, IL, 60439, United States of America,
1 - A Scalable Approach to Solving Multi-stage Stochastic
Integer Programs
Osman Ozaltin, Assistant Professor, North Carolina State
University, Raleigh, NC, United States of America,
, Burhaneddin Sandikci
Despite being a flexible modeling framework, multi-stage SPs are not widely
adopted in practice, mostly due to their unbearable size. Moreover, incorporating
integer variables renders multi-stage SPs even less tractable. We propose a
bounding-based solution approach, which does not assume convexity but it
rather relies on scenario decomposition and is inherently parallelizable. Our
results demonstrate that the proposed method scales nicely with problem size and
produces high quality solutions.
2 - On Solving General Two-stage Stochastic Programs
Manish Bansal, Postdoctoral Fellow, Department of Industrial
Engineering and Management Science, Northwestern University,
2145 Sheridan Road, Evanston, IL, 60208, United States of
America, , Sanjay Mehrotra
We study general two-stage stochastic programs (TSSPs) and present conditions
under which the second stage programs can be convexified. This generalizes the
results of Bansal et al. (2015) for two-stage stochastic mixed integer programs. We
present finitely convergent decomposition algorithms to solve many classes of
TSSPs including TSSP with some non-convex program in the second stage. We
computationally evaluate our convexification approach by solving two-stage
stochastic lot-sizing problems.
3 - Algorithmic Innovations and Software for the Dual Decomposition
Method Applied to SMIP
Kibaek Kim, Argonne National Laboratory, 9700 South Cass
Avenue, Argonne, IL, 60439, United States of America,
Victor M. Zavala
We develop algorithmic innovations for the dual decomposition method to
address two-stage stochastic programs with mixed-integer recourse and provide a
parallel software implementation. Our innovations include the derivation of valid
inequalities that tighten Lagrangian subproblems and the stabilization of dual
variables by solving the master problem with a primal-dual interior point method
and provide termination criteria that guarantee finite termination of the
algorithm.
4 - Updates to PIPS-SBB: A Parallel Distributed Memory
Stochastic Mip Solver
Geoff Oxberry, Lawrence Livermore National Laboratory,
P.O. Box 808, L-792, Livermore, CA, United States of America,
, Deepak Rajan, Thomas Edmunds,
Pedro Sotorrio, Lluís Miquel Munguía, Cosmin Petra
Deterministic equivalent formulations of stochastic MIPs from applications such
as unit commitment (UC) can exceed available memory on a single workstation.
To overcome this limitation, we have developed PIPS-SBB, a parallel distributed
memory stochastic MIP solver based on the distributed memory stochastic LP
solver PIPS-S. Here, we discuss ongoing work on PIPS-SBB, with a focus on
parallel implementations of B&B techniques. We also present a path forward to
solving large UC problem instances.
MD14
14-Franklin 4, Marriott
Robust Optimization in Radiation Therapy Planning
Sponsor: Optimization/Optimization Under Uncertainty
Sponsored Session
Chair: Wei Liu, Assistant Professor, Mayo Clinic Arizona,
5777 E Mayo Blvd., Phoenix, AZ, 85054, United States of America,
1 - Scenario-based Radiotherapy Margins: Handling Tissue
Inhomogeneity, Range Errors, and Organ Motion
Rasmus Bokrantz, RaySearch Laboratories, Sveavägen 44,
Stockholm, 111 34, Sweden,
, Albin Fredriksson
We consider a scenario-based optimization formulation to handle the effects of
errors in radiotherapy planning. The formulation coincides with margin-based
planning if the implicit assumptions made when the margins are delineated are
valid, but also generalizes to more difficult situations such as irradiation of
inhomogeneous tissue or irradiation with proton fields. We extend the model to
account for tissue inhomogeneity, proton range errors, and organ motion.
2 - Robust Optimization Methods for Breast Cancer
Radiation Therapy
Houra Mahmoudzadeh, University of Toronto, Toronto ON,
Canada,, , Timothy Chan, Thomas Purdie
We explore robust optimization methods for improving the quality of treatment
in left-sided breast cancer radiation therapy. Our robust models take into account
breathing uncertainty and minimize the dose to the organs at risk while meeting
the clinical dose-volume limits on the cancerous target. We use clinical data from
several breast cancer patients and compare the outcomes of our robust models
with those of the current clinical methods.
3 - Chance-constrained Robust Optimization in Proton Therapy to
Account for Beam Delivery Uncertainties
Yu An, Mayo Clinic, 5777 East Mayo Blvd., Phoenix, AZ, 85054,
United States of America, , Jianming Liang,
Wei Liu
We propose a chance-constrained model in intensity-modulated proton therapy
treatment planning by explicitly accounting for range and patient setup
uncertainties in optimization algorithm. Decomposition methods are applied to
render the large-scale optimization problems tractable and achieve the best trade-
off between plan quality and robustness. The results are then checked by patient
population study to demonstrate the statistically significant advantages of our
planning method.
4 - Robust Spatiotemporally Integrated Fractionation in Radiotherapy
Archis Ghate, University of Washington, Industrial & Systems
Engineering, University of Washington Box 352650, Seattle,
United States of America, Ali Ajdari
Feasibility of the fluence-maps in the spatiotemporally integrated fractionation
problem crucially depends on the linear-quadratic dose-response parameters of
the organs-at-risk. We present a robust formulation of this problem whereby the
resulting dosing schedule remains feasible as long as the dose-response
parameters vary within a known range. This robust model is non-convex and
high-dimensional. We discuss approximate solution techniques rooted in convex
programming.
MD15
15-Franklin 5, Marriott
Distributed Convex Optimization
Sponsor: Optimization/Nonlinear Programming
Sponsored Session
Chair: Necdet Serhat Aybat, Assistant Professor, Industrial Engineering
Dept., Penn State University, University Park, PA,
United States of America,
1 - A New Globally Convergent Incremental Newton Method
Mert Gurbuzbalaban, Massachusetts Institute of Technology, 32
Vassar St, Cambridge, MA, United States of America,
, Asu Ozdaglar, Pablo Parrilo
We develop and analyze a new globally convergent incremental Newton method
for minimizing the sum of strongly convex functions, motivated by machine
learning problems over large data sets and distributed optimization over
networks. We discuss its convergence rate and prove its linear convergence under
some assumptions.
2 - Multiagent Distributed Admm: Rate of Convergence
Ali Makhdoumi, Massachusetts Institute of Technology,
32 Vassar St, Cambridge, MA, 02139, United States of America,
Asu Ozdaglar
We consider a multi agent optimization problem where a network of agents
collectively solves a global optimization problem with the objective function given
by the sum of locally known convex functions. This problem arises in many
applications in large-scale distributed statistical estimation. We propose a fully
distributed ADMM algorithm and characterize its rate of convergence as well as
its dependence on the network structure.
3 - An Asynchronous Distributed Proximal Method for Composite
Convex Optimization
Zi Wang, Penn State University, 1400 Martin St, Apt. 2112, State
College, PA, 16803, United States of America, ,
Necdet Serhat Aybat, Garud Iyengar
We propose an asynchronous distributed first-order augmented Lagrangian
(DFAL) algorithm to minimize sum of composite convex functions, where each
term is a private function to one node, and only nodes connected by an edge can
communicate. We show any limit point of iterates is optimal; an eps-optimal and
eps-feasible solution can be computed with probability at least 1-p within O(1/eps
log(1/p)) communications. We demonstrate the efficiency of DFAL on large scale
sparse-group LASSO problems.
MD13