2016 INFORMS Annual Meeting Program

TB12

INFORMS Nashville – 2016

TB13 104C-MCC

4 - Approximation Algorithms For Expected-value Maximum Multiple Coverage Problem And Its Variants Kay Zheng, University of Wisconsin-Madison, kay.zheng@wisc.edu, 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, qhe@umn.edu 1 - Approximation Algorithms For Chance-constrained Problems Shabbir Ahmed, Georgia Institute of Technology, shabbir.ahmed@isye.gatech.edu, 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, jim.luedtke@wisc.edu, 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, sebastian.pokutta@isye.gatech.edu, 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, wuxx1164@umn.edu, 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.

Recent Advances in Stochastic Integer Programs Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Yongjia Song, Virginia Commonwealth University, Richmond, VA, United States, ysong3@vcu.edu 1 - A Scalable Bounding Approach For Multistage Stochastic Programs Osman Yalin Ozaltin, North Carolina State University, Raleigh, NC, 27695, United States, oyozalti@ncsu.edu 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, ysong3@vcu.edu, 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, HaoxiangYang2019@u.northwestern.edu, 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. Chair: Chuangyin Dang, Professor, City University of Hong Kong, Dept of Systems Eng & Eng Mgmt, 83 Tat Chee Avenue, Kowloon, Hong Kong, mecdang@cityu.edu.hk 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, hemantb@ucdavis.edu, 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, k.d.maclean@gmail.com, 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. TB14 104D-MCC Revenue Mgt, Pricing Contributed Session

268