Informs Annual Meeting Phoenix 2018

WC42INFORMS Charlotte – 2011

TD06

3 - Submodular Maximization Under Matroid Constraints: A Case for Robustness Alfredo Torrico, Georgia Institute of Technology, Atlanta, GA, United States, Mohit Singh, Sebastian Pokutta In the robust submodular maximization problem subject to a matroid constraint, we are given a collection of k monotone submodular functions and a matroid on a ground set of size n. The goal is to select a feasible set that maximizes the minimum of the submodular functions. This is known to be NP-hard to approximate to any polynomial factor. We design a bi-criteria approximation algorithm that returns a set with (nearly) optimal value and such that it is the union of few feasible sets. This algorithm uses less function evaluations than previous works. Also, we provide a computational study of our algorithm in real- world applications. 4 - Stochastic Load Balancing on Unrelated Machines Xiangkun Shen, University of Michigan, 1205 Beal Ave, Ann Arbor, MI, 48109, United States, Viswanath Nagarajan, Anupam Gupta, Amit Kumar We consider the unrelated machine scheduling problem when job processing- times are stochastic. We provide the first constant factor approximation algorithm for the setting where one wants a fixed assignment of jobs to machines so as to minimize the expected makespan. The identical machines special case has been well-understood for several years, but the problem was previously open even in the case of related machines. The main technical contribution is an efficiently computable lower bound via an exponential-sized LP, and its rounding. n TD05 North Bldg 122B Linear and Conic Optimization in Energy Systems Sponsored: Optimization/Linear and Conic Optimization Sponsored Session Chair: Alberto J. Lamadrid, Lehigh University, 621 Taylor Street, R451, Bethlehem, PA, 18015-3120, United States 1 - Multistage Expansion Planning of Distribution Networks Considering Reliability Javier Contreras, Universidad de Castilla-La Mancha, E.T.S. de Ingenieros Industriales, Campus Universitario s/n, Ciudad Real, 13071, Spain, Gregorio Muñoz-Delgado, Jos M. Arroyo This work presents the multistage expansion planning problem of a distribution network considering reliability. Thus, the best alternative, location, and installation time for the candidate assets are identified while jointly accounting for economic and reliability aspects. Unlike previously-reported works, reliability is implemented through algebraic expressions whereby the effect of the network topology is explicitly represented by decision variables of the optimization process. The resulting optimization problem is cast as an instance of mixed-integer linear programming. 2 - Piecewise Linear Approximation for Separable Concave Programming Problem Quadratic programming (QP) arises in a wide variety of applications, from finance to public policy and electric grids. We report the results of applying an algorithm that uses piecewise linear functions for approximating QP problems with a separable objective function of multiple variables. We compare our results with the results from three other solvers: CPLEX, BARON, and IPOPT. The results show that the new algorithm outperforms the other three solvers both in computational time and objective function value. It also shows that we can reach a near optimal solution faster than the current solvers. 3 - Stochastic Operation for Networked Building Clusters Integrated with Glides and Thermal Storage Yang Chen, Oak Ridge National Laboratory, Oak Ridge, TN, 37830, United States, Patrick O’Connor The Ground-Level Integrated Diverse Energy Storage (GLIDES) technology is a hybrid pumped hydropower-compressed air technology which can use waste-heat as an energy input. A two-stage stochastic model is established with uncertainties from energy loads and solar radiation for community building clusters equipped with GLIDES and thermal storage and an integer L-shaped algorithm is developed to solve the problem efficiently. Amin Nikakhtar, Texas Tech University, 2500 Broadway, Lubbock, TX, 79409, United States, Ismael De-Farias, Victoria Howle

4 - Optimal Scheduling for Power Systems Under Uncertainty Alberto J. Lamadrid, Assistant Professor, Lehigh University, 621 Taylor Street, R451, Bethlehem, PA, 18015-3120, United States, Ray Zimmerman, Carlos Murillo-Sanchez, Haeyong (David) Shin, Robert Thomas, Daniel Munoz We present an open source simulation tool for security-constrained unit commitment (SCUC) problem. We discuss our formulation using a Markov Decision Process with a traditional deterministic approach.We focus on the our proposed stochastic approach to explicitly model of the operational characteristics of the technologies available, the changes over time, the network and congestion effects, and the regulatory constraints that assure reliability and adequacy. n TD06 North Bldg 122C Joint Session OPT/Practice Curated: Recent Advances in Global Optimization and Applications Sponsored: Optimization/Global Optimization Sponsored Session Chair: Erfan Mehmanchi, University of Pittsburgh, Pittsburgh, PA, 15260, United States 1 - Globally Solving Non-convex Quadratic Programs via Linear Integer Programming Techniques Luis F. Zuluaga, Lehigh University, Harold S. Mohler Laboratory, 200 West Packer Avenue, Bethlehem, PA, 18015, United States, Wei Xia, Juan C. Vera Quadratic programming (QP) is a well-studied fundamental NP-hard optimization problem which optimizes a quadratic objective over a set of linear constraints. In this paper, we reformulate QPs as a mixed-integer linear problem (MILP). This is done via the reformulation of QP as a linear complementary problem, and the use of binary variables and big-M constraints, to model the complementary constraints. To obtain such reformulation, we show how to impose bounds on the dual variables without eliminating all the (globally) optimal primal solutions; using some fundamental results on the solution of perturbed linear systems. 2 - Optimizing a Bundle Pricing Problem We are interested in solving a combinatorial matrix assignment problem which appears in literature as a bundle pricing problem in a multi-buyer-single-seller market. The problem has a MIQCQP formulation due to the requirement that a feasible assignment of buyers to bundles have envy-free equilibrium. Literature has many approximation results and polynomial-time algorithms under certain assumptions. We adopt an integer programming approach to solve this problem in general. We test our formulations and polyhedral relaxations on random instances and compare our MIP methodology to the Lagrangian relaxation techniques proposed in literature. 3 - Boundedly Rational User Equilibrium Models in Electricity Consumer Market Studies in Smart Grid Guanxiang Yun, University of Central Florida, 12800 Pegasus Drive, P.O. Box 162993, Orlando, FL, 32816, United States, Qipeng Zheng We propose a new boundedly rational user equilibrium (BRUE) model of the residential users’ behavior for the consumption of energy schedule with the smart grid. People will accept any option with which utilities just less than a certain level compare to the best option’s utility. We also introduce the unit time pricing strategy that can flatten the user’s behavior of energy consumption. The problem is solved by using three methods, use BARON directly, penalty method and lagrangian dual method. Even though the BRUE constraints are non-convex constraints, we still find under our conditions, it have the strong duality. From the result, we find by introducing the price, it can decrease the cost of the system. 4 - On Robust Fractional 0-1 Programming Erfan Mehmanchi, University of Pittsburgh, 4200 Fifth Avenue, Pittsburgh, PA, 15260, United States, Colin P. Gillen, Andres Gomez, Oleg A. Prokopyev We examine single- and multiple-ratio robust fractional 0-1 programming problems (RFPs) under a broad classes of uncertainty sets. In particular, we demonstrate that under budgeted uncertainty sets single-ratio RFPs are polynomially-solvable if the deterministic counterparts are. We also reformulate the multiple-ratio RFPs as several mixed-integer linear programs (MILPs). Finally, computational experiments are conducted to evaluate the performance of MILP reformulations, as well as to compare the various uncertainty sets. Hamid Nazari, Clemson University, Clemson, SC, 29631, United States, Akshay Gupte, Lawrence Joseph McCormick

347