2016 INFORMS Annual Meeting Program

MA13

INFORMS Nashville – 2016

2 - Network Level Traffic Management Through Selective Ramp Metering Dening Peng, Arizona State University, Dening.Peng@asu.edu, Pitu B. Mirchandani The vast literature on ramp metering has mostly focused on strategies for local traffic controls on an isolated freeway segment or freeway system, without considering integrated network-wide traffic diversions. The research presented investigates the coordinated ramp metering problem with the consideration of network-wide traffic diversions caused by ramp capacity changes from ramp metering. A nonlinear programming optimization model is developed to determine the optimal ramp metering rates for the entire traffic network and the corresponding user equilibrium traffic flow pattern. A gradient-based search algorithm is developed to solve the model efficiently. 3 - A New Methodology For Sewer Systems Design Daniel Duque, Universidad de los Andes, d.duque25@uniandes.edu.co, Andres L Medaglia The sewer network design problem consists of determining both the layout and the hydraulic design of the sewer system. In this work, we propose an iterative framework to design minimum-cost sewer networks. The layout selection is modeled as a variant of the Network Design Problem. Once the layout is defined, the hydraulic design is modeled as a Shortest Path Problem, in which the underlying graph resembles the diameter and slope of each pipe. Both procedures are solved iteratively to improve the objective function until a termination criterion is met. Our methodology compares favorably against traditional hydraulic-based techniques and commercial software. 4 - Dynamic Maximum Flow With Geographic Conflict Considerations Navid Matin Moghaddam, Arizona State University, Tempe, AZ, United States, nmatinmo@asu.edu, Jorge A. Sefair We study the problem of finding the maximum number of agents traveling between two known nodes in a network within a specified time horizon. Paths used by agents must not be conflicting, meaning that no two agents can be closer to each other than a given distance at any time. For this purpose, we need to find not only the path for each agent but also a schedule to traverse the network. Typical examples of this problem include the transportation of hazardous materials and transportation operations under geographic failures. Here, we present an exact solution method to solve this problem. MA12 104B-MCC Integrated Methods and Decomposition Approaches Sponsored: Optimization, Integer and Discrete Optimization Sponsored Session Chair: Joris Kinable, Carnegie Mellon University, Pittsburgh, PA, United States, jkinable@cs.cmu.edu 1 - Decomposition By Decision Diagrams Andre Augusto Cire, University of Toronto - Scarborough, acire@utsc.utoronto.ca, David Bergman Decision diagrams (DDs) have recently been applied to a variety of optimization problems, often closing long-standing instances from classical benchmarks. This success is primarily driven by a DD’s ability to capture combinatorial structure. We exploit this characteristic and propose a novel solution method which decomposes a problem into highly-structured portions, where the solutions of each portion can be compactly represented using a DD. The DDs are then connected using mathematical programming, which represents a reformulation of the original problem. Preliminary results suggest that this new approach can improve upon both standard integer programming models and a single DD approach. 2 - Scalable Segment Abstraction Method For Advertising Campaign Admission And Inventory Allocation Optimization Tuomas W Sandholm, Carnegie Mellon University, sandholm@cs.cmu.edu, Tuomas W Sandholm, Optimized Markets, Inc., Pittsburgh, PA, United States, sandholm@cs.cmu.edu, Fei Peng Publishers enable advertisers to create increasingly targeted campaigns. This dramatically increases the publisher’s complexity when optimizing campaign admission and inventory allocation to campaigns. We develop an optimal anytime algorithm for abstracting audience segments into coarser segments that are not too numerous for optimization. Compared to Walsh et al. [AAAI-10], it yields 45x to 142x speedup and significant improvement in quality. This stems from a quadratic-time (as opposed to doubly exponential or heuristic) algorithm for finding an optimal split of an abstract segment, a better scoring function for evaluating splits, and splitting time lossily like other attributes.

3 - A Branch-and-Check Approach To Solve A Wind Turbine Maintenance Scheduling Problem Louis-Martin Rousseau, Professor, Ecole Polythechnique

de Montreal, Montréal, QC, Canada, louis-martin.rousseau@polymtl.ca Louis-Martin Rousseau Froger, Michel Gendreau, Jorge E. Mendoza, Éric Pinson

The problem consist in finding a maintenance planning that maximizes the production of wind turbines while taking into account wind predictions, multiple task execution modes, and task technician assignment constraints. We introduce an exact method to solve this challenging problem. We first propose new integer linear programming formulations of this problem. Then, on this basis, we build up a Benders- based branch-and-cut approach making use of Benders cuts as well as problem-specific cuts. The results suggest that our method significantly outperforms the direct resolution of integer linear programming models and a previously developed hybrid metaheuristic approach. 4 - Branch And Price And Check For Vehicle Routing With Location Constraints Pascal Van Hentenryck, University of Michigan, pvanhent@umich.edu This paper considers a vehicle routing problem with pickup and delivery, time windows and location constraints. Locations can become congested if insufficient resources are available, upon which vehicles must wait until a resource becomes available before proceeding. This talk presents a branch-and-price-and-check model that uses a branch-and-price to solve the core vehicle routing problem and a constraint programming subproblem to check the feasibility of the location resource constraints. Combinatorial nogood cuts are added to the master problem when resource constraints are violated. Experimental results show the benefits of the approach. MA13 104C-MCC Nonconvex Optimization: Theory and Algorithms Sponsored: Optimization, Global Optimization Sponsored Session Chair: Evrim Dalkiran, Wayne State University, 4815 Fourth St, Detroit, MI, 48202, United States, evrimd@wayne.edu 1 - Computational Experimentation With Cutting Planes For Convex-transformable Functions Factorable relaxations of global optimization problems can be strengthened via the use of functional transformations. In this work, we consider a new method to strengthen factorable relaxations which exploits convex-transformability of intermediate expressions. We integrate recently developed relaxations into the software BARON and study their effect on the convergence of the branch-and- reduce algorithm. Our implementation relies on the generation of cutting planes corresponding to supporting hyperplanes of convex relaxations of convex- transformable functions. We present extensive computational results on problems from a collection of publicly available test sets. 2 - RLT And McCormick Relaxations For Polynomial Programming Problems Evrim Dalkiran, Wayne State University, evrimd@wayne.edu A polynomial programming problem can be equivalently formulated as a quadratically constrained quadratic program (QCQP) by introducing new variables that represent nonlinear monomials. In this talk, we discuss strength and tractability of the standard Reformulation-Linearization Technique (RLT) and J-set relaxations constructed for the original and quadrified formulations, and identify the superior relaxation depending on the problem characteristics. Extensive computational results are provided to demonstrate the effectiveness of the relaxations using problems from the literature and randomly generated test instances. 3 - Polyhedral Results For Combinatorially-constrained Network Flows Jean-Philippe P. Richard, University of Florida, richard@ise.ufl.edu Danial Davarnia Various problems that arise in railroad operations can be formulated as network flow problems with additional combinatorial constraints. In this talk, we describe two such requirements, and present mip formulations for them. We then show that valid inequalities can be derived for these combinatorial constraints in the space of original variables, limiting the need to introduce auxiliary binary variables. We report computational results that show that relaxation bounds obtained with these cutting planes are stronger, and faster to derive than those generated by commercial mip solvers on the problem natural mip formulations. Carlos Nohra, Carnegie Mellon University, Department of Chemical Engineering, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, cnohrakh@andrew.cmu.edu Nikolaos Sahinidis

125