2016 INFORMS Annual Meeting Program

125 / 561

INFORMS Nashville – 2016
125
2 - Network Level Traffic Management Through Selective
Ramp Metering
Dening Peng, Arizona State University,
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,
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, 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,
1 - Decomposition By Decision Diagrams
Andre Augusto Cire, University of Toronto - Scarborough,
, 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,
, Tuomas W Sandholm, Optimized Markets,
Inc., Pittsburgh, PA, United States,
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 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,
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,
1 - Computational Experimentation With Cutting Planes For
Convex-transformable Functions
Carlos Nohra, Carnegie Mellon University, Department of
Chemical Engineering, 5000 Forbes Avenue, Pittsburgh, PA,
15213, United States,
Nikolaos Sahinidis
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,
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,
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.
MA13