INFORMS Nashville – 2016
330
2 - Mixed-integer Programming For Detecting Cycles In
Non-reversible Markov Processes
Ambros Gleixner, Zuse Institute Berlin, Takustr. 7, Berlin, 14195,
Germany,
gleixner@zib.de, Isabel Beckenbach, Leon Eifler,
Konstantin Fackeldey, Andreas Grever, Marcus Weber,
Jakob Witzig
Spectral clustering methods are used successfully to identify so-called metastable
sets or dominant cycles of Markov processes. They analyze the spectrum of
matrices based on the transition probabilities between states. However, current
spectral methods have limited applicability for many biological and catalytic
processes with a systematic, but slow cyclic behavior on the timescale of the
simulation. We use mixed-integer programming to develop a new method that is
able to detect the existence and measure the strength of such cyclic processes.
3 - Enhanced Equations For Linearizing Discrete Product For
Generalized Programming Problems
Qi An, North Carolina State University, 2119A Gorman Street,
Raleigh, NC, 27606, United States,
nival.ann@gmail.com,Tiantian Nie, Shu-Cherng Fang
This paper advances ``Equations for Linearizing Discrete Product’’ — a set of
equations that linearize discrete polynomial terms in an effective manner. We
exploit the logarithmic feature and propose an enhancement technique to further
reduce the number of linear constraints for the current ELDP-based
reformulations. We extend the applicability of ELDP to a more general set of
``representable programming problems’’. Computational experiments on both
random problems and literature-reported problems support that the proposed
method indeed increases the computational effectiveness.
4 - A Farm-level Precision Land Management Model Based On
Integer Programming
Qi Li, Iowa State University, 0076 Black Engineering, Ames, IA,
50010, United States,
qili@iastate.edu, Guiping Hu, Zaki Jubery,
Baskar Ganapathysubramanian
A farm level precision farmland management model based on mixed integer
linear programming has been proposed. Optimal decisions are provided for
preseason crop planning and irrigation water allocation. The model captures the
effect of size and shape of decision scale as well as special irrigation patterns. We
illustrate the model by conducting a case study on a farm in California and show
the model is capable of representing the decision making process and flexible to
accommodate various scenarios. The results show that a threefold increase of
annual net profit could be achieved by carefully choosing irrigation and seed
types.
5 - Whistler-Blackcomb Mega Day As An Integer
Programming Problem
John Shane Lyons, PhD Student, Western University-Ivey Business
School, 23 Pine Ridge Drive, London, ON, N5X 3G7, Canada,
jlyons.phd@ivey.caThe Whistler-Blackcomb ski area has recently implemented a system which tracks
use of 25 lifts across both mountains. A web-based application offers skiers a
variety of analytic information pertaining to their skiing activity, and poses a
number of ‘badges’ to be earned. One of these, called Mega Day, requires a skier
to ride all lifts on both mountains, and consequently ski roughly 10,000 vertical
metres. On a particular date of study less than 0.1% of skiers on the mountain
achieved this goal. This presentation describes an integer programming model
developed to identify feasibility and optimal routing for the Mega Day challenge.
TC78
Legends F- Omni
Opt, Network III
Contributed Session
Chair: Oliver Lum, U of Maryland, College Park, 11604 Parkedge Drive,
Rockville, MD, 20852, United States,
oliver@math.umd.edu1 - On The Complexity Of Sparse Maximum Flow Problems
Andrew Romich, Systems Engineer, Sandia National Laboratories,
4617 Gerrilyn Way, Apt 206, Apt. 206, Livermore, CA, 94550,
United States,
aromich@sandia.gov,Cole Smith, Guanghui Lan
We consider several sparsity-inducing restrictions of the standard maximum flow
problem. Each restriction is a unique combination of the number of nodes having
an out-degree greater than one and the inclusion of either a restriction on the
total amount of flow on all arcs or the total number of arcs used in the network.
Assuming an option of initially allowing continuous or integer flow, we analyze a
total of twelve problems.
2 - Mathematical Optimization For Managing Selective Catalytic
Reduction For A Fleet Of Coal-fired Power Plants
Jay Michael Rosenberger, University of Texas-Arlington, Dept of
Industrial Manuf Systems Eng, PO Box 19017, Arlington, TX,
76019, United States,
jrosenbe@uta.edu, Antonio Alejandro Alanis
Selective Catalytic Reduction (SCR) reduces emissions of oxides of nitrogen
(NOx) in coal-fired power plants. With a given set of scheduled outages for a fleet
of power plants, we develop a heuristic multi-commodity flow problem with
schedule elimination constraints, and a knapsack problem with assignment
constraints, to create an SCR management plan, which minimizes the total SCR
operational cost of the entire fleet of power plants and maintains NOx emissions
below a desired target. We present results indicating that our approach provides
an equally optimal solution to that of a schedule generation and optimization
approach in less computational processing time.
3 - A Parametric Linear Programming Approach To A Cluster Ratio
Based Hierarchical Consensus Clustering Algorithm
Victoria Ellison, North Carolina State University, 2152 Burlington
Labs 2500 Stinson Dr., Raleigh, NC, 27695, United States,
vmelliso@ncsu.edu, Yahya Fathi, Amy Langville
The minimum cluster ratio cut is a well studied partition-based clustering method
used to partition a data set into two or more clusters of balanced size. We propose
a natural extension of the minimum cluster ratio cut, which we call the minimum
beta-ratio cut, which lends itself to hierarchical clustering methods. We propose a
divisive hierarchical consensus clustering algorithm which uses the minimum
beta-ratio cut and a heuristic for this algorithm by modifying a BILP formulation
of Median Partition problem and applying a parametric programming algorithm
to it.
4 - A Hybrid Heuristic For The Windy Rural Postman Problem With a
Time-Dependent Zigzag Option
Oliver Lum, U of Maryland, College Park, 11604 Parkedge Drive,
Rockville, MD, 20852, United States,
oliver@math.umd.edu,
Rui Zhang, Bruce L Golden
In some vehicle routing applications, service is required along both sides of the
road. During early morning hours, the vehicle may service both sides of the street
during a single traversal by zigzagging between the two. This scenario is modeled
by the Windy Rural Postman Problem with Time-Dependent Zigzag Options
(WRPPZTW). We present a hybrid heuristic for the WRPPZTW which uses well-
known insertion techniques in concert with a new integer programming
formulation for the WRPPZ. We compare computational performance relative to
an existing exact procedure for a set of small instances and present more
extensive results for a set of larger instances.
5 - The Deviation-flow Continuous Location Problem For A Single
Refueling Station On A Tree Network
Sang Jin Kweon, PhD Candidate, Pennsylvania State University,
310 Leonhard Building, Industrial and Manufacturing
Engineering, University Park, PA, 16802, United States,
svk5333@psu.eduIn this study, we address the continuous version of the single refueling station
location problem on a tree network considering that a given portion of drivers has
the option to deviate from their preplanned paths to be able to refuel their
vehicles. The objective of the problem is to determine the set of optimal station
locations that maximizes the total traffic flow covered (in round trips per time
unit). To achieve this goal, we derive optimality properties regarding deviation
and determine the sets of candidate sites to locate the refueling station. Then, we
develop a polynomial algorithm to determine the set of optimal locations.
TC79
Legends G- Omni
Opt, Stochastic III
Contributed Session
Chair: Md Abdul Quddus, PhD Student, Mississippi State University,
Department of Industrial & Systems Engineering, PO Box 9542,
Starkville, MS, 39762, United States,
mq90@msstate.edu1 - Multi-depot Fleet Dimensioning For Seasonal Stochastic Demand
Marcus V. Poggi, PUC-Rio, Rua M. S. Vicente 225, Rio de Janiero,
22591-900, Brazil,
poggi@inf.puc-rio.br,Fabian Penaranda
Given a predicted demand behavior represented by a generation function over
time and space, distances between clients and the depots, cost to lease one vehicle
for the period, unity cost for traveling a distance for leased and for short time
hired vehicles and a demand allocation rule, find the (heterogeneous) fleet size at
each depot that minimizes the expected operation cost for the period. We propose
a decomposition approach based on Stochastic Dual Dynamic Programming that
allows dealing with the integrality of the sub-problems. Instances based on
CVRPLIB are generated and experimental results are presented.
TC78