Informs Annual Meeting 2017

SB74

INFORMS Houston – 2017

SB72

method. With minimal engineering and without heuristic designing, Neural Combinatorial Optimization achieves close to optimal results on 2D Euclidean graphs with up to 100 nodes. Applied to the KnapSack, another NP-hard problem, the same method obtains optimal solutions for instances with up to 200 items. 2 - Learning Combinatorial Optimization Algorithms over Graphs Le Song, Georgia Institute of Technology, 266 Ferst Drive, Atlanta, GA, 30332, United States, lsong@cc.gatech.edu, Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina Significant expertise is required to design good heuristics for hard graph optimization problems. In many applications, it is typically the case that the same optimization model is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristics that exploit the structure of such recurring problems. We propose a unique combination of reinforcement learning and graph embedding to address this challenge, and demonstrate competitive performance for Minimum Vertex Cover, Max Cut, TSP and Set Covering. 3 - Controlling Stochastic VRP Systems by using Deep Reinforcement Learning Mohammadreza Nazari, Lehigh University, Murray H.Goodman Campus, Bethlehem, PA, 18015, United States, mon314@lehigh.edu, Afshin Oroojlooy Jadid, Lawrence V. Snyder, Martin Takac We present a deep learning scheme for the VRP problem with stochastic demands. Demands arrive randomly at different locations, and at each time step a vehicle chooses its next destination according to a policy learned by deep reinforcement learning in order to maximize its reward over a time horizon. This problem has applications in distribution networks and real-time taxi allotment and has been widely studied in the stochastic optimization, but most studies assume that the demand distribution is known. A major complexity arises when the demands are non-stationary or from an unknown distribution. In this talk, we address this issue by using deep recurrent Q-networks. 4 - Financial Evaluation of Large Cap Companies on the Stock Market; Artificial Neural Networks Approach to Stock Picking Alireza Moghimi, New Mexico State University, 1132 E.Mesa Apt.15, Las Cruces, NM, 88001, United States, moghimi@nmsu.edu The current research proposes an Artificial Neural Network based forecasting model to evaluate the relative financial performance of a group of firms. The model employs company’s historical financial data and classifies firms based on their future financial performance. The study attempts to generate portfolios that could outperform the market and shift the distribution of the returns earned by an investor. The model employs the financial statements of the companies on S&P-500 index for 2006 to 2014 period. A portfolio based on the proposed model is compared to several benchmarks by bootstrapping and statistical analysis. The model is significantly outperforming the market.

372A Mechanism Design and Network Pricing Sponsored: Optimization, Network Optimization Sponsored Session Chair: Evdokia Velinova Nikolova, University of Texas at Austin, 400 E Monroe Street, Austin, TX, 78704, United States, nikolova2009@gmail.com 1 - Aversion to Uncertainty and its Implications for Revenue Maximization Emmanouil Pountourakis, University of Texas at Austin, 16 Bristol Street, Unit 3, Cambridge, MA, 02141, United States, malgor21@gmail.com Mechanism design often assumes that buyers are risk neutral, or exhibit risk aversion due to a non-linear utility for money. Yet behavioral studies show that real agents exhibit various risk attitudes, which, cannot be captured by any expected utility model. We adopt a model from prospect theory, where an event which occurs with probability x<1 is worth strictly less than x times the value of the event when it occurs with certainty. We characterize optimal mechanisms in the static setting as menus of binary lotteries and we show that under a reasonable assumption, posted pricing obtains a constant approximation. Third, we show that constant approximation is impossible in dynamic settings. 2 - Pricing: How to Induce Optimal Flows under Strategic Link Operators Thanasis Lianeas, Univeristy of Texas at Austin, Austin, TX, 78704, United States, tlianeas@mail.ntua.gr, Evdokia Velinova Nikolova Our main result is to observe that a slight regulation on the network owners market solves all three issues above. Specifically, if the authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge then: the game among the link operators has a unique strong Nash equilibrium and the users’ game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. We then ask, can we compute great tolls that minimize total users’ payments? We show that this optimization problem reduces to a linear program in the case of single- commodity series-parallel networks. Starting from the same linear program, we obtain multiplicative approximation results for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a surprising bound, which only depends on the topology of the network. 3 - Bifurcation Mechanism Design – From Optimal Flat Taxes to Improved Cancer Treatments Ger Yang, University of Texas at Austin, Austin, TX, United States, geryang@utexas.edu, Georgios Piliouras, David Basanta Small changes to the parameters of a system can lead to abrupt qualitative changes of its behavior, a phenomenon known as bifurcation. Such instabilities are typically considered problematic, however, we show that their power can be leveraged to design novel types of mechanisms. Hysteresis mechanisms use transient changes of system parameters to induce a permanent improvement to its performance via optimal equilibrium selection. Optimal control mechanisms induce convergence to states whose performance is better than even the best equilibrium. We apply these mechanisms in two different settings that illustrate the versatility of bifurcation mechanism design. In the first one we explore how introducing flat taxation can improve social welfare, despite decreasing agent “rationality”, by destabilizing inefficient equilibria. From there we move on to consider a well known game of tumor metabolism and use our approach to derive novel cancer treatment strategies. 372B Using Deep Neural Networks for Solving Combinatorial Optimization Problems Sponsored: Computing Sponsored Session Chair: Mohammadreza Nazari, Lehigh University, Bethlehem, PA, 18015, United States, mon314@lehigh.edu Co-Chair: Afshin OroojlooyJadid, Lehigh University, Bethlehem, PA, 18015, United States, afo214@lehigh.edu 1 - Neural Combinatorial Optimization with Reinforcement Learning Irwan Bello, Google Brain, Mountain View, CA, United States, ibello@google.com We present a framework to tackle combinatorial optimization problems using neural networks and reinforcement learning. We focus on the traveling salesman problem (TSP) and train a recurrent neural network that predicts a distribution over city permutations. Using negative tour length as the reward signal, we optimize the parameters of the recurrent neural network using a policy gradient SB73

SB74

372C Computational Advances in VRPs Sponsored: Computing Sponsored Session

Chair: Ahmed Ghoniem, University of Massachusetts-Amherst, Amherst, MA, 01003, United States, aghoniem@isenberg.umass.edu 1 - Upper and Lower Bounding Procedures for Snow Plow Optimization Joris Kinable, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, jkinable@cs.cmu.edu, Willem-Jan Van Hoeve, Stephen F.Smith Snow plow optimization is a complex process in which routes for a fleet of vehicles have to be determined, while adhering to vehicle operating restrictions, and resource utilization and replenishment constraints. We present upper and lower bounding techniques for a real-world snow plow optimization problem. Feasible routes and schedules are calculated using heuristics and a Constraint Programming approach. To study the quality of our solutions, a bounding procedure is developed based on a Mixed Integer Programming model for Capacitated Arc Routing with Intermediate Replenishment Facilities. Computational experiments are conducted on data from the city of Pittsburgh (USA).

61