Informs Annual Meeting 2017

TD77

INFORMS Houston – 2017

3 - On Knapsack Problems Over Time Yuri Faenza, Assistant Professor, Columbia University, 500 West 120th Street, New York, NY, 10025, United States, yf2414@columbia.edu, Igor Malinovic The time-Invariant Incremental Knapsack problem (IIK) has been introduced by Bienstock et al. [2013] as a generalization of the classical Maximum Knapsack to a discrete multi-period setting. At each time, the capacity increases and items can be added, but not removed, from the knapsack. The goal is to maximize the sum of profits of items over all times. IIK naturally models scenarios where resources (e.g. money, labor force) augment over time in a predictable way, allowing an expansion of our portfolio. In this talk, we give algorithmic and structural results on this and, if time permits, on related problems. 4 - A Regularized Cutting Plane Algorithm for Inverse Mixed Integer Programming Problems Vishnu Vijayaraghavan, Texas A.& M.University, 400 Nagle Street, College Station, TX, 77840, United States, vishnunitr@tamu.edu, Kiavah Kianfar, Andrew J.Schaefer An inverse optimization problem is to minimally perturb the cost function of an optimization problem with respect to some Lp-norm, so as to make a given feasible solution the optimal one. Inverse optimization for mixed integer problems is particularly challenging. Wang (2009) proposed a cutting plane algorithm to solve inverse mixed integer problems under a weighted norm. We present an improved version of this cutting plane algorithm by regularizing the addition of more effective cutting planes. Our computational results demonstrate significant gains over the previous approach, more profoundly for problems in large dimensions. 372F Optimization, Integer Programming Contributed Session Chair: Hyeoncheol Baik, Auburn University, Auburn, AL, United States, hbaik@auburn.edu 1 - Bundle Pricing and Inventory Planning for a Multi Products Newsvendor Problem Nooshin Hamidian, University of Tennessee-Knoxville, 5 11Q John D. Tickle Engineering Building, 851 Neyland Dr, Apt A5, Knoxville, TN, 37996, United States, nhamidia@vols.utk.edu, Rupy Sawhney The multi-product newsvendor problem is studied. The objective is to maximize expected revenue while both the selling prices and ordering quantities are decision variables. The demand for all products and bundles are additive stochastic and cross-elastic. The mathematical model for the problem is developed. A two-stage algorithm is proposed in order to solve the mathematical model. The proposed algorithm is based on multi-directional search and Nest Partitioning algorithm and has both methods’ advantageous. Sensitivity analysis is presented to obtain managerial insights. 2 - Biased Random-key Genetic Algorithm for Balanced Edge Partitioning Larissa P.G. Petroianu, PhD Student, University of Washington, 3900 E Stevens Way NE, Mechanical Engineering Building, Vertex partitioning in graphs has received more attention in the literature than edge partitioning. In this talk, we consider an edge-partitioning problem with applications in page-rank computation and delivery routing. We develop a Biased Random-Key Genetic Algorithm (BRKGA) that finds optimal or near-optimal solutions to this problem. We present experimental results, comparing our algorithm with other approaches. 3 - Automatic Design of Algorithms for Knapsack Problems Victor Parada, Dr Sc, Universidad de Santiago de Chile, Av. Ecuador 3659, Departamento de Ingeniería Informática, Santiago, Chile, victor.parada@usach.cl Automatic design of algorithms for combinatorial optimization problems can generate new procedures from existing heuristics. We generated algorithms for the 0-1 binary knapsack and for the multidimensional knapsack problems that efficiently and competitively solve a set of typical problem instances. The automatically constructed algorithms are generated by genetic programming as a result of exploring the heuristic combinations space. TD77 Seattle, WA, 98195, United States, lpetroia@uw.edu, Mauricio G.C. Resende, Wanpracha Art Chaovalitwongse

4 - Unmanned Aircraft System Path Planning for Inspecting Electric Transmission Towers Hyeoncheol Baik, Auburn University, 3331 Shelby Center, Auburn, AL, 36849, United States, hbaik@auburn.edu, Jorge F.Valenzuela Electric utilities inspect transmission towers by dispatching line crews and helicopters. This method has high operation costs and safety concerns. To mitigate these issues, the utilities are using unmanned aircraft system to accomplish this task. We have developed a particle swarm optimization based algorithm to find an efficient flight route for a UAS to inspect a transmission tower. The proposed model contains three sub-objectives: to minimize the total flight distance, maximize the inspection coverage, and maximize the image resolution. We have tested our model and make recommendations for the actual use of a UAS in the field. 381A Market-based Management of Future Electricity Grids Sponsored: Energy, Natural Res & the Environment Electricity Sponsored Session Chair: Wolfgang Ketter, University of Cologne, Cologne, Germany, ketter@wiso.uni-koeln.de 1 - Pricing Mechanisms to Coordinate EV Charging: A Variable Charging Speed Approach Konstantina Valogianni, Assistant Professor, IE Business School, VAT.# ES.B-82334319, Maria de Molina 13, Madrid, 28006, Spain, konstantina.valogianni@ie.edu, Wolfgang Ketter, John Collins, Gediminas Adomavicius We present a decision support system (DSS) that coordinates electric vehicle (EV) charging. It combines the benefits of a decentralized decision making approach with a top-down control mechanism. This hybrid approach creates a less volatile aggregate power demand curve, and therefore a better match between the output of renewable energy sources and overall demand. Our mechanism is based on price signals to individual EV owners. We prove that are sufficient to motivate self-interested EV owners to approach a desired profile, given a range of user preferences. We prove the analytical properties of the mechanism in order to induce desired charging profiles and evaluate its outcome on real-world data. 2 - Risk-neutral and Risk-averse Methods for Bidding in the Energy Market Daniel Jiang, University of Pittsburgh, Pittsburgh, PA, 15261, United States, drjiang@pitt.edu, Warren B. Powell The talk is centered on developing optimal trading/bidding policies for the energy market in the presence of storage. In the context of this application, we describe two general methodological contributions: approximate dynamic programming for monotone value functions and for risk-averse sequential problems. 3 - Implement Real-time Pricing with Regret-based Learning Games Zibo Zhao, PhD Candidate, Purdue University, West Lafayette, Grissom Hall, 315 N Grant Street, West Lafayette, IN, 47907, United States, zhao438@purdue.edu The situation where price-responsive consumers determine what to do in the near future (such as when to charge their PEVs) forms a dynamic and incomplete-information game, in which the consumers’ collective actions will impact electricity prices, which in turn affect their payoffs. We propose a multi- armed bandit (MAB) game framework in which each consumer plays an MAB problem to minimize the cumulative regret, as opposed to naively responding to day-ahead prices. Numerical results show very fast convergence to a steady-state of the MAB game with much reduced price volatility than the naïve-response case. TD78

404