Informs Annual Meeting 2017

TC77

INFORMS Houston – 2017

3 - Multi-objective Maximization of Monotone Submodular Functions Rajan Harish Udwani, Massachusetts Institute of Technology, 70 Pacific Street, 809, Cambridge, MA, 02139, United States, rudwani@mit.edu The best known algorithm for multi-objective maximization of monotone submodular functions, from Chekuri et.al. (2010), is a randomized (1-1/e)- \epsilon approximation algorithm for maximization subject to a Matroid constraint. However, the runtime scales exponentially in the number of functions, limiting this number to be a small constant. We focus on the special case of multi- objective maximization subject to a cardinality constraint (say k elements), and show constant factor approximations for up to o(k) many functions (problem is known to be inapproximable for \Omega(k) functions). We extend the (1-1/e) algorithm from above but also give a simpler and much faster (1-1/e)^2 approximation. 4 - A Logic-based Benders Approach to Home Healthcare Scheduling Ryo Kimura, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, rkimura@andrew.cmu.edu, John Hooker, Aliza R.Heching We propose an exact optimization method for home healthcare scheduling based on logic-based Benders decomposition (LBBD). The objective is to match patients with healthcare aides and schedule multiple home visits over a given time horizon, so as to maximize the number of patients served. Using LBBD, we decompose the problem into a master problem, solved by mixed integer programming, and several small scheduling subproblems, solved by constraint programming. We find that LBBD is far superior to mixed integer programming and optimally solves problems of realistic size, if the aim is to conduct staff planning on a rolling basis, and if there are a limited number of temporal dependencies between visits. 372F Optimization, Integer Programming Contributed Session Chair: Thibaut Vidal, PUC-Rio, Departamento de Informatica, Rio de Janeiro, Brazil, vidalt@inf.puc-rio.br 1 - Scenario Based Economic Dispatch with Adaptable Risk Levels in Uncertain Power Systems M. Sadegh Modarresi, Research Assistant, Texas A&M.University, 1907 Dartmouth St, Apt 602, College Station, TX, 77840, United States, sadegh.modarresi@tamu.edu, Hao Ming, Le Xie This paper presents a data-driven scenario approach to 1- dispatching power systems with high levels of uncertain resources in the real-time stage, and 2-at the day-ahead electricity market clearing process with the presence of demand response providers. By taking historical samples and generating appropriate sample-based uncertainty sets, this approach quantifies the relationship between the risk of violating the constraints and the cost conservativeness of the dispatch. Numerical simulations suggest that this approach could be a promising alternative in future electricity markets with uncertain load and generation resources. 2 - Parametric Analysis of Semidefinite and Second Order Conic Optimization We consider the parametric analysis of semidefinite and second-order conic optimization problems when the right-hand side or the objective coefficients vector is perturbed along a certain direction. We introduce the concept of the optimal partition to characterize the optimal value function and the optimal set mapping and highlight the contrast with the case of LO. We show that under a nondegeneracy condition, the optimal set mapping is continuous, but in order to gain Lipschitz continuity, we need strict complementarity condition too. Further, we show that at a transition point, where the optimal partition changes, the higher order derivatives of the optimal value function do not exist. 3 - Finding Infimum Point with Respect to the Second Order Cone Marta Cavaleiro, Rutgers University, Management Science and Informations Systems, 100 Rockefeller Road, Piscataway, NJ, 08854, United States, marta.cavaleiro@rutgers.edu, Farid Alizadeh We define the notion of infimum and supremum of a set of points with respect to the second order cone. These problems can be formulated as second order cone optimization and thus solved by interior point methods in polynomial time. We present an extension of the simplex method to solve these problems and show some applications. TC77 Ali Mohammad-Nezhad, PhD Student, Lehigh University, 200 W Packer Ave., Bethlehem, PA, 18015, United States, alm413@lehigh.edu, Tamas Terlaky

4 - Cluster Analysis is Convex Madhushini Narayana Prasad, PhD Student, The University of Texas at Austin, 9226 Jollyville Road, Unit 150, Austin, TX, 78759, United States, madhushini@utexas.edu, Grani Adiwena Hanasusanto In this work, we show that the popular k-means clustering problem is amenable to an exact conic programming reformulation. The emerging convex problem is NP-hard but admits a tractable polynomially solvable semidefinite programming (SDP) relaxation. We prove that this resulting SDP is equivalent to the state-of- the-art SDP approximation scheme and enjoys the same 2-approximation ratio. In contrast to this scheme, our proposed SDP reformulation yields solutions that can be used to directly identify the clusters. We assess the performance of our reformulation in numerical experiments and demonstrate its superiority over the state-of-the-art scheme and the classical Lloyd’s algorithm. 5 - A Stochastic Frank-wolf Algorithm for Sparse and Non-stationary Environments Davoud Ataee Tarzanagh, University of Florida, 1400 Stadium Rd, University of Florida, Gainesville,, FL, 32611, United States, Tarzanagh@ufl.edu, George Michailidis The conditional gradient method, also known as - Ω for convex problems has lately regained popularity thanks to its projection-free property and its ability to exploit the structured constraints appearing in machine learning and big data applications. However, our understanding of this algorithm in the online and non- stationary setting is fairly limited, especially for problems with very noisy and/or sparse gradients. In this talk, we propose a stochastic variant of the Frank- Wolfe algorithm, based on adaptive estimates of lower-order moments. Our method is aimed towards problems involving large data sets and/or sparse gradients. 6 - Separable Convex Optimization with Nested Lower and Upper Constraints Thibaut Vidal, PUC-Rio, Departamento de Informatica, Rua Marques de Sao Vicente, 225, Rio de Janeiro, 22453-900, Brazil, vidalt@inf.puc-rio.br, Daniel Gribel, Patrick Jaillet We study a generalized convex resource allocation problem arising in production planning, vessel speed optimization, and support vector machine applications. We propose a decomposition algorithm, which uses monotonicity properties to generate bounds from recursive calls and eliminate linking constraints. These principles are very different from the usual greedy-scaling or even flow- propagation methods currently known. It improves upon the best known complexities, producing an integer or continuous solution in linearithmic time, and solving problems with one million variables in one minute. 381A Low-Carbon Power Sector: Policy and Technology Analysis Sponsored: Energy, Natural Res & the Environment Electricity Sponsored Session Chair: Afzal Siddiqui, University College London, University College London, London, United Kingdom, afzal.siddiqui@ucl.ac.uk 1 - Regional Carbon Policies in an Interconnected Power System. How Expanded Coverage Could Enhance Prospects for Emissions Leakage Makoto Tanaka, National Graduate Institute for Policy Studies (GRIPS), 7-22-1 Roppongi, Minato-ku, Tokyo, 106-8677, Japan, mtanaka@grips.ac.jp, Verena Viskovic, Yihsu Chen, Afzal Siddiqui Reaching objectives under unilateral CO2 reduction policies can be delayed by carbon leakage. In the context of power markets, this is of concern in regional interconnected power systems with inconsistent policies. Using a stylised bi-level model of such a market where regions are connected with a congested line, we explore the effects of mitigating leakage by accounting for emission from the non- regulated region when setting the policy in the regulated region. We find that the overall emissions in the system decrease; however, the marginal value of transmission capacity increases, thus, providing more incentive for expanding the capacity of the line, which could potentially lead to more leakage. TC78

364