2016 INFORMS Annual Meeting Program

268 / 561

INFORMS Nashville – 2016
268
4 - Approximation Algorithms For Expected-value Maximum Multiple
Coverage Problem And Its Variants
Kay Zheng, University of Wisconsin-Madison,
, Laura Albert McLay, James Luedtke
Motivated by cyber-security planning application, we develop an optimization
framework based on maximum coverage problem addressing multiple coverage,
concave objective function, group budget constraints, and random coverage
failure etc. Polynomial time approximation algorithms with constant performance
guarantees are formulated to solve the integer programming models.
Computational results are presented to demonstrate the efficiency and accuracy of
the algorithms.
TB12
104B-MCC
New Models and Approximation Results in Stochastic
and Combinatorial Optimization
Sponsored: Optimization, Integer and Discrete Optimization
Sponsored Session
Chair: Qie He, University of Minnesota, 111 Church Street SE,
Minneapolis, MN, 55455, United States,
1 - Approximation Algorithms For Chance-constrained Problems
Shabbir Ahmed, Georgia Institute of Technology,
, Weijun Xie
Chance constrained problems (CCPs) are NP-hard. We propose bicriteria
approximation algorithms for CCPs by scaling and rounding optimal solutions to
certain relaxations proposed in the literature. We explore the tractability of the
relaxations under different probability distributions. For a CCP with discrete
support, this approximation algorithm can be reduced to a single criterion one,
and the approximation ratio turns out to be tight.
2 - Valid Inequalities For Separable Concave Constraints With
Indicator Variables
James Luedtke, University of Wisconsin-Madison, Madison, WI,
United States, Cong Han Lim,
Jeff Linderoth
We study valid inequalities for optimization models that contain both binary
indicator variables and separable concave constraints. We propose a technique to
obtain valid inequalities that are based on both the MILP constraints and the
concave constraints. We demonstrate how valid inequalities for the single node
flow set and for the lot-sizing polyhedron can be to “tilted” to give valid
inequalities that also account for separable concave functions of the arc flows. We
present promising computational results demonstrating the utility of the new
inequalities for nonlinear transportation problems and for lot-sizing problems
with concave costs.
3 - Strong Reductions For Linear And Semidefinite Programs
Sebastian Pokutta, Georgia Institute of Technology,
, Gabor Braun, Aurko Roy
Linear and semidefinite programming are two core optimization paradigms with
many important applications. However, the expressive power of these modeling
paradigms is only partially understood so far and extended formulations are a
powerful and natural tool to analyze the possibilities and limitations of linear and
semidefinite programming formulations. We will present a strong reduction
mechanism both for LPs and SDPs, which allows to establish strong
inapproximability results for various problems, including e.g., vertex cover,
bounded-degree matching, and sparsest cut. Moreover, the reduction mechanism
induces an ordering of relative hardness of the underlying problems.
4 - A Matrix Selection Problem
Zeyang Wu, University of Minnesota,
Qie He
Consider a discrete-time dynamic system xk+1 = Mkxk for k = 0,1,2, T. The
matrix Mk can be chosen as one of the given two matrices A or B. The matrix
selection problem is defined as follows: given an initial vector x0, select matrices
M1, ..., MT such that a linear function over the states x1,... xT is minimized. This
problem is motivated by an application in cancer treatment planning. We
formulate this problem as a mixed-integer linear program, and derive several
families of facet-defining inequalities for the resulting formulation.
TB13
104C-MCC
Recent Advances in Stochastic Integer Programs
Sponsored: Optimization, Integer and Discrete Optimization
Sponsored Session
Chair: Yongjia Song, Virginia Commonwealth University,
Richmond, VA, United States,
1 - A Scalable Bounding Approach For Multistage
Stochastic Programs
Osman Yalin Ozaltin, North Carolina State University, Raleigh, NC,
27695, United States,
Despite being a flexible modeling framework, multistage stochastic programs are
not widely adopted in practice, mostly due to their unbearable size. Moreover,
incorporating integer variables renders multistage stochastic programs even less
tractable. We propose a bounding 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 - Adaptive Partition-based Level Decomposition For
Stochastic Programs
Yongjia Song, Virginia Commonwealth University, Richmond, VA,
Wim van Ackooij, Welington de Oliveira
We present a computational study of several strategies to solve two-stage
stochastic programs by integrating the adaptive partition-based approach with
level decomposition. A partition-based formulation is a relaxation of the original
stochastic program, obtained by aggregating variables and constraints according to
a scenario partition. Partition refinements are guided by the optimal second-stage
dual vectors computed at certain first-stage solutions. The proposed approaches
rely on the level decomposition with on-demand accuracy to dynamically adjust
partitions until an optimal solution is found. Numerical results are presented.
3 - A Class Of Sequential Discrete Decision Problems With
Stochastic Disruptions
Haoxiang Yang, Northwestern University, Evanston, IL, United
States, David Morton
We consider a sequential decision problem under uncertainty, where the
uncertainty consists of a small number of disruptions and where both the
magnitude and the timing of the disruption can be random. We first formulate a
stochastic linear programming model and an algorithm to solve it. Furthermore,
we extend the model to handle integer decision variables, investigate methods to
solve this multi-stage stochastic integer program and evaluate the computational
performance of our approach.
TB14
104D-MCC
Revenue Mgt, Pricing
Contributed Session
Chair: Chuangyin Dang, Professor, City University of Hong Kong,
Dept of Systems Eng & Eng Mgmt, 83 Tat Chee Avenue, Kowloon,
Hong Kong,
1 - When Is It Optimal To Offer Free Allowance?
Hemant K Bhargava, University of California, Gh-3108, Graduate
School of Management, Davis, CA, 95616, United States,
Manish Gangwar
In contrast to Two-Part Tariff (2PT), Three Part Tariff (3PT) offers an additional
free allowance. We find that despite free allowance optimal 3PT generates the
same profits as optimal 2PT. However, the free allowance in 3PT can improve
firm’s profit under two conditions, when consumers are uncertain about their
usage or when the market demand involves a multi modal mixture distribution.
2 - Dynamic Stochastic Knapsack Problem With Adaptive Interaction
Kyle Maclean, Ivey Business School, London, ON, Canada,
Fredrik Odegaard
Motivated by group seating requirements in entertainment venues, we formulate
and study an extension to the Dynamic Stochastic Knapsack Problem. We add a
stochastic interaction between the offered set of open compartments and the item
placement, generalizing previously deterministic problems and making the
problem relevant to revenue management customer choice models. Then, using a
specific interaction function inspired by the entertainment industry, we provide
an algorithm to determine the optimal solution. Using this algorithm we obtain
insights into the structural properties of the problem.
TB12