Informs 2015

381 / 552

INFORMS Philadelphia – 2015
379
4 - An Effective Approach to the Determination of Proper Equilibrium
Chuangyin Dang, Professor, City University of Hong Kong, Dept.
of SEEM, 83 Tat Chee Avenue, Kowloon, Hong Kong - PRC,
, Yin Chen
As a powerful refinement of Nash equilibrium, proper equilibrium plays an
important role in the development of game theory. This paper aims to develop an
effective smooth path-following method for computing proper equilibria. By
appropriately incorporating barrier terms into payoff functions, we construct a
smooth path to a proper equilibrium through closely approximating some Nash
equilibrium of a perturbed game. Extensive numerical results further confirm the
effectiveness of the method.
WA17
17-Franklin 7, Marriott
Network Analysis II
Sponsor: Optimization/Network Optimization
Sponsored Session
Chair: Bahar Cavdar, Middle East Technical University, Ankara, Turkey,
1 - A Network-Based Approach to Bushfire Fuel Management
Dmytro Matsypura, The University of Sydney,
Rm 478 Merewether Building H04, Sydney, Australia,
Oleg Prokopyev
Bushfires represent a real and continuing problem that can have a major impact
on people, wildlife and the environment. One way to reduce the severity of their
effect is through fuel management. We propose a general methodology to address
the problem of optimal resource allocation for bushfire fuel management subject
to landscape connectivity and stochastic fuel regeneration.
2 - Empty Repositioning under Demand Uncertainty in Large-scale
Transportation Networks
Ilke Bakir, PhD Student, Georgia Institute of Technology, H.
Milton Stewart School, 765 Ferst Dr NW, Atlanta, GA, 30332-
0205, United States of America, ,
Alan Erera, Martin Savelsbergh
We consider a transportation network where loaded demand quantities are
uncertain, and only estimates are known. We introduce different methods of
solving the repositioning problem on relatively sparse networks to satisfy as much
demand as possible, using loaded demand estimates. We first experiment with
various sharing group policies (hub/spoke structures for empty repositioning),
and then introduce a robust optimization approach to further improve demand
satisfaction.
3 - A Robust Framework for Event Prediction in Partially
Unobserved Networks
Aaron Schecter, Northwestern University, 2240 Campus Drive,
1-459, Evanston, IL, 60208, United States of America,
, Noshir Contractor
Longitudinal social network analysis is typically framed as a series of decisions by
rational actors. However, individuals only have access to partial information
about the whole network. As a result, behaviors are functions of both observed
local ties as well as perceived second order relationships. We propose a statistical
model for the prediction of dyadic link events under this assumption of network
uncertainty; our technique draws from robust optimization and simulation
principles.
4 - A Tabu Search with Time-based Preprocessing for Vehicle
Routing Problem with Time Windows
Bahar Cavdar, Middle East Technical University, Ankara, Turkey,
Joel Sokol
Recent applications of Vehicle Routing Problem (VRP) such as online grocery
shopping require finding solutions in a short time with little knowledge of the
instance in advance. Current solution methods put more emphasis on the
solution quality rather than the computation time. In this talk, we present a new
heuristic for VRP with time windows. We combine a tabu search approach with a
preprocessing of the instance using arc-based waiting time information to speed
up the computation.
WA18
18-Franklin 8, Marriott
Optimization Combinatorial I
Contributed Session
Chair: Burcin Cakir Erdener, Dr., Baskent University, Eskisehir Yolu 20
km. Baglica Kampusu, Muhendislik Fak. Etimesgut, Ankara, 06800,
Turkey,
1 - Dynamic-programming-based Inequalities for the Multi-
dimensional Unbounded Knapsack Problem
Xueqi He, University of Florida, 3800 SW 34th St. Apt. P138,
Gainesville, FL, 32608, United States of America,
We present a new branch-and-cut approach for solving the multi-dimensional
unbounded knapsack problem, where valid inequalities are generated for an
integer programming formulation based on intermediate solutions of an
equivalent dynamic programming formulation. These inequalities tighten the
initial LP relaxation, and therefore improve the computational efficiency.
2 - An Exact Algorithm for Biobjective Mixed Integer Linear
Programming Problems
Gazi Bilal Yildiz, Res. Assist., Erciyes University, Engineering
Faculty, Industrial Engineering, Kayseri, 38039, Turkey,
, Banu Soylu
In this study, we develop an algorithm to generate all Pareto line segments of
BOMILPs. Our algorithm starts with the solution of an individual objective
function and then sequentially generates all line segments of the Pareto frontier.
At each iteration of the algorithm, one line segment of the Pareto frontier is
detected. If there is no new Pareto line segment available, the algorithm ends. We
provide a numerical example and present the performance of the algorithm over
several test problems.
3 - Virtual Mixed Integer Nonlinear Programming Model for Integrated
Electricity Distribution System
Burcin Cakir Erdener, Dr., Baskent University, Eskisehir Yolu 20
km. Baglica Kampusu, Muhendislik Fak. Etimesgut, Ankara,
06800, Turkey, , Berna Dengiz,
Zulal Gungor, Imdat Kara
An electricity network design problem with distributed generation, which is called
the Integrated Electricity Distribution System (IEDS) design problem is
considered. The design procedure aims at the minimization of total system design
cost while ensuring the optimum location and routing decisions for several
system elements. To solve IEDS,a mixed-integer nonlinear-programming model is
proposed. A new network transformation approach called virtual node
duplicating is introduced within the model.
WA19
19-Franklin 9, Marriott
Computational Optimization for Applied Problems II
Sponsor: Computing Society
Sponsored Session
Chair: Hans Mittelmann, Arizona State University, Box 871804, Tempe,
United States of America,
1 - Scip-jack -A Solver for the Steiner Tree Problem and Variants with
Parallelization Extensions
Stephen Maher, Zuse Institute Berlin, Takustr. 7, Berlin, BE,
14195, Germany, Gerald Gamrath, Thorsten Koch,
Daniel Rehfeldt, Yuji Shinano
The Steiner tree problem in graphs (STP) arises in practical applications as one of
many variants. A relationship exists between the different STP variants,
suggesting the potential for a generic solver. However, problem specific solutions
approaches are commonly observed. SCIP-Jack is a general purpose solver to
solve both the STP and many of its variants. Transformations are employed that
permit STPs to be solved using a MIP-framework. The result is a massively parallel
general STP solver.
2 - Compact MIP Formulation of the Selective Delivery and
Pickup Problem
Yuanyuan Dong, Southern Methodist University, 3101 Dyer
Street, Dallas, TX, 75205, United States of America,
, Eli Olinick
We present a compact MIP for the selective delivery and pickup problem with the
objective of maximizing profit by accepting unscheduled deliveries during the
time-limited trip. The MIP is inspired by a novel formulation of multicommodity
flow that significantly reduces the size of the constraint matrix and the LP upper
bound compared to a model based on the classical approach. This in turn leads to
faster solution times when using commercial MIP codes, as we demonstrate in an
empirical study.
WA19