CORAL Optimization Seminar Series
Lehigh University - Industrial and Systems Engineering
- Fall Sessions 2002
| Title: | Using a Genetic Algorithm Approach to Schedule a Meltshop in the Steel Industry |
|---|
| Author: | Francis J. Vasko, Professor of Mathematics and CIS, Kutztown University |
|---|
| Time: | Thursday 01/30/03 12:00pm - 1:00pm |
|---|
| Place: | Mohler Laboratory 355 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
The scheduling of a meltshop at an integrated steel plant is a very
complex and important logistical industrial problem. This problem
requires the synchronization of several steelmaking furnaces, degassing
facilities, ladle treatment stations, and continuous casters. In this
talk, we discuss how an efficient domain-specific heuristic is combined
with a genetic programming approach in a prototype scheduling model.
Specifically, given preliminary schedules for the continuous casters,
the model determines the allocation, sequencing, and scheduling of
batches of steel at the basic oxygen steelmaking furnaces, the degassing
facilities, and the ladle treatment stations. It also makes the
appropriate schedule modifications at the continuous casters.
Preliminary industrial results will be discussed.
Bio-Sketch:
Francis J. Vasko is a Professor of Mathematics and Computer and
Information Science at Kutztown University of Pennsylvania. Before
coming to Kutztown University in September 1986, he worked for more than
eight years as an employee in the Research Department at Bethlehem Steel
solving a variety of real-world applications in operations research.
His current research focuses on using a large variety and combination of
combinatorial optimization techniques and metaheuristics in order to
more accurately model and solve important real-world applications in
production planning, strategic planning, and resource allocation.
| Title: | A New Framework for Scalable Parallel Tree Search |
|---|
| Author: | Professor Ted Ralphs, Industrial and Systems Engineering, Lehigh University |
|---|
| Time: | Wednesday 09/11/02 12:00pm - 1:00pm |
|---|
| Place: | Mohler Laboratory 451 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
We will describe a new framework, called the Abstract Library for
Parallel Search (ALPS), that can be used to implement a wide variety of
parallel algorithms based on tree search. The framework includes general
parallel search handling, a layer for implementing parallel branch and
bound, and a mechanism for "data-intensive" applications (such as the
branch and cut algorithm for integer programming), in which a large
number of global data objects are needed to describe each search tree
node. We will discuss the motivation for and design of this framework,
as well as present some preliminary computational results on Lehigh's
new parallel computing cluster.
Bio-Sketch:
Dr. Ralphs received his doctorate in Operations Research from Cornell
University in 1995. Following graduation, he spent four years in the
United States Air Force, working primarily as an operations analyst.
His career in the Air Force culminated with a position as the lead
operations analyst for the 422nd Test and Evaluation Squadron, where
he was responsible for the design and analysis of operational tests
involving Air Force aircraft and weapon systems. After leaving the
Air Force, Dr. Ralphs spent a year as a postdoctoral research
associate at Rice University's Keck Center for Discrete Optimization
before joining the faculty of the Industrial and Manufacturing Systems
Engineering Department at Lehigh University in August, 2000.
| Title: | Solving Stochastic Optimization Problems on Computational Grids |
|---|
| Author: | Professor Jeff Linderoth, Industrial and Systems Engineering, Lehigh University |
|---|
| Time: | Thursday 09/19/02 12:00pm - 1:00pm |
|---|
| Place: | Mohler Laboratory 355 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
The Internet can be thought of as a "Computational Grid" -- a large
collection of loosely coupled, heterogeneous, non-dedicated computing
resources. Because of the potential power and low cost of this type
of environment, users of optimization technology have the potential to
solve problems of larger scale and complexity than ever before.
In the first portion of the talk, we will introduce existing software
tools that allow users to harness the power of a Computational Grid.
The second portion of the talk will describe an implementation of a
trust-region, decomposition-based method for solving linear stochastic
programming problems with recourse that is geared for a Grid computing
platform. Computational results are presented that demonstrate the
scale of problems that can be solved using the CPU power that the Grid
has to offer.
Bio-Sketch:
Jeff Linderoth is an Assistant Professor of Industrial and Systems
Engineering at Lehigh University. Dr. Linderoth received his PhD from
the Georgia Institute of Technology in 1998. From 1998-2000, he visited
the Mathematics and Computer Science Division at Argonne National
Laboratory, where he was the Enrico Fermi Scholar. From 2000-2002, Dr.
Linderoth was a Senior Consultant with the optimization-based financial
products firm of Axioma Inc., located in Marietta, Georgia. In 2002,
Dr. Linderoth received the Optimization Group Prize from the Society for
Industrial and Applied Mathematics.
| Title: | Using an Integer Programming Formulation to Solve a Problem in Tournament Ranking |
|---|
| Author: | Professor Garth Isaak, Mathematics, Lehigh University |
|---|
| Time: | Thursday 09/19/02 12:00pm - 1:00pm |
|---|
| Place: | Mohler Laboratory 355 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
As an example of using integer programming problems to yield
theorems in
graph theory and combinatorics we will discuss an integer programming
formulation
for the following problem: If we rank players in a round robin tournament
so as to
minimize the number of inconsistencies (player A beats player B but gets
lower ranking) how large a tournament is needed so that some subgroup of n
of the players is ranked entirely wrong by this procedure. In keeping with
the informal nature
of the seminar we will discuss other problems where showing results about
certain classes of integer programming problems would yield interesting
theorems in discrete mathematics.
Bio-Sketch:
Garth Isaak is an associate professor in the mathematics department at
Lehigh University. He recieved
his PhD in 1990 from RUTCOR (Rutgers Center for Operations Research) and
spent two years
as a John Wesley Young instructor in mathematics and computer science at
Dartmouth before coming
to Lehigh. His research tends to be in theoretical areas of combinatorics
and graph theory.
| Title: | Long-Distance Access Network Design |
|---|
| Author: | Professor Rosemary Berger, Industrial and Systems Engineering, Lehigh University |
|---|
| Co-Author: | Professor S. Raghavan, Robert H. Smith School of Business,
University of Maryland |
|---|
| Time: | Thursday 10/10/02 12:00pm - 1:00pm |
|---|
| Place: | Mohler Laboratory 355 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
Long-distance telephone companies in the United States pay
access fees to
local telephone companies to transport calls that originate and
terminate on their networks.
These charges form the largest portion of the cost of providing
long-distance service.
Recent changes in the structure of access rates, which were mandated by
the FCC,
have created opportunities for long-distance companies to better manage
access costs.
In this talk, a formulation for the long-distance access network design
problem is presented.
The model incorporates both the queueing aspects of an alternate routing
policy and the
discrete optimization aspects of a hub location problem. A three-phase
optimization-based
algorithm is described and computational results are presented.
Bio-Sketch:
Rosemary Berger is an Assistant Professor of Industrial and
Systems Engineering
at Lehigh University. Dr. Berger received her PhD from Northwestern
University in 1997.
From 1997-2002, she worked in the telecommunications industry, first at
U S WEST Advanced
Technologies and most recently at Level 3 Communications. As a
technical staff member,
she applied operations research techniques to solve network engineering
problems and
developed optimization-based decision support tools.
| Title: | An Integer-Programming Approach to the "all_different" Predicate |
|---|
| Author: | Dr. Jon Lee, T.J. Watson Research Center, IBM |
|---|
| Time: | Friday 10/18/02 1:30-2:30pm |
|---|
| Place: | TBA | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
The "all_different " predicate is very useful in formulating many
complicated logistics problems, like scheduling problems. One way of
working with this predicate is through techniques of constraint
programming.
I will describe a subtle linear integer-programming formulation and
cutting-plane method for working with all_different.
Bio-Sketch:
Jon received his B.S. (1981), M.S. (1984) and Ph.D. (1986) degrees in
Operations Research, from Cornell University. He spent 1985-1993 on the
faculty of Yale University and 1993-2000 on the Mathematics Department
faculty of the University of Kentucky. He was a research visitor at the
Center for Operations Research and Econometrics, Universite Catholique de
Louvain, in Belgium, for the academic years 1991-1992 and 1999-2000. Jon
joined IBM in the summer of 2000, where he now manages the Theory of
Computation group.
Jon was Vice-Chair for Integer Programming of the Optimization Section of
INFORMS for 2000 and 2001. Currently, he is an Associate Editor of the
journal Discrete Applied Mathematics, an external member of CORC
(Computational Optimization Research Center) of Columbia University, a
member of the Working Group on Discrete Optimization of the IFIP
(International Federation for Information Processing), and an Adjunct
Professor at the Leonard N. Stern School of Business, New York University.
| Title: | Network Reinforcement |
|---|
| Author: | Dr. Francisco Barahona, T.J. Watson Research Center, IBM |
|---|
| Time: | Friday 10/25/02 1:30-2:30pm |
|---|
| Place: | TBA | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
We give an algorithm for the following problem:
given a graph G=(V,E) with edge-weights and a nonnegative integer k,
find a minimum cost set of edges that contains
k disjoint spanning trees. This also solves the following
reinforcement problem:
given a network, a number k and a set of candidate edges, each of them
with an associated cost, find a minimum cost set of candidate edges
to be added to the network so it contains
k disjoint spanning trees. The number k is seen as a measure of the
invulnerability of a network.
We show that this can be solved with |V| applications
of the minimum cut algorithm of Goldberg & Tarjan. The previously known
algorithm requires solving 2|E| minimum cut problems.
Bio-Sketch:
Degrees: Docteur-Ingenieur (U. de Grenoble, France),
Ingeniero Matematico (U. de Chile).
Present affiliation:
Research Staff at IBM T. J.Watson Research Center, Yorktown Heights, New York.
External member of the Computational Optimization Research
Center at Columbia University.
Former affiliations:
1980-1983, Assistant Professor, Universidad de Chile.
1983-1985, Associate Professor, Universidad de Chile.
1985-1990, Associate Professor, University of Waterloo.
1987-1988, John von Neumann Professor, University of Bonn.
1990, Full Professor, University of Waterloo.
Research areas: Mathematical Programming,
Combinatorial Optimization, Operations Research.
| Title: | Linear Matrix Inequalities in Systems and Control |
|---|
| Author: | Mayuresh Kothare, Lehigh Chemical Engineering |
|---|
| Time: | Thursday 10/31/02 12:00-1:00pm |
|---|
| Place: | Mohler Laboratory 355 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
The last few years have seen the emergence of a new class of optimization problems
which have been variously referred to as Linear Matrix Inequalities (LMIs), semi-definite
programming (SDP) problems and convex problems. These problems have the generic
form of a linear objective function minimization subject to linear matrix inequality
constraints.
The form of the SDP is very general and widely encountered in systems and control theory.
Since the early publication of the classic monograph by Boyd and co-workers in 1994, there
has been an explosive growth in the number of publications that report application of SDP to
various feedback control problems. Some of these problems were previously considered
unsolvable in their original form but have now been shown to be reducible to SDPs and LMIs,
thereby rendering them tractable. The efficiency of recent interior point methods for solving
SDPs, which is directly responsible for the popularity of SDP in control, has also attracted a
great deal of interest in the optimization community.
In this talk, we present an overview of results from our work on the use of LMIs in receding
horizon
optimal control problem and constraint handling anti-windup controller synthesis and analysis.
Bio-Sketch:
Mayuresh V. Kothare is currently a P. C. Rossin and Frank Hook Assistant
Professor of Chemical Engineering at Lehigh University. He received the degree of
Bachelor of Technology (B.Tech.) in Chemical Engineering from the Indian Institute
of Technology, Bombay, in 1991. He was recipient of the Institute
Silver Medal for ranking first in Chemical Engineering at the Indian
Institute of Technology, Bombay, the J. N. Tata Endowment award and
the Sumant Mulgaonkar Memorial award for academic excellence in
chemical engineering. He received his M.S. degree in Chemical
Engineering from the California Institute of Technology in June 1995
and a Ph.D. degree in Chemical Engineering in June 1997 with a minor
in Control and Dynamical Systems. From September 1994 to December
1996, he was a research assistant in the Automatic Control Laboratory
of the Swiss Federal Institute of Technology in Zurich. From
January to June 1997, he was a visiting scholar in the Department of
Chemical Engineering at City College New York. From July 1997 to June
1998, he held a postdoctoral appointment in the Modeling and Advanced
Control group of Mobil Technology Company, a subsidiary of Mobil Oil
Corporation. In July 1998, he joined Lehigh University where he is
currently a P. C. Rossin and Frank Hook Assistant Professor of
Chemical Engineering and Co-Director of the Chemical Process Modeling
and Control Research Center.
Dr. Kothare's interests are in the areas of control of chemical
processes with input and output constraints; and modeling, dynamics
and control of microchemical systems. He has made contributions in the
analysis and synthesis of anti-windup control systems, model
predictive control and application of linear matrix inequalities to
solving receding horizon control problems. He is recipient of the year
2000 Ted Peterson Student Paper Award from the Computing & Systems
Technology Division of the American Institute of Chemical Engineers, the
CAREER award from the National Science Foundation in 2002 and the Alfred
Nobel Robinson from Lehigh University in 2002.
| Title: | Optimal Rooted Graphs and Expected Value |
|---|
| Author: | Professor Gary Gordon, Mathematics, Lafayette College |
|---|
| Co-Authors: | Alison Bailey, Matt Paton and Jenn Scancella (REU Students)
|
|---|
| Time: | Thursday 11/07/02 12:00-1:00pm |
|---|
| Place: | Mohler Laboratory Room 355 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
When G is a rooted graph where each edge may
independently succeed with probability p, we consider the expected number of
vertices in the operational component of G containing the root. This
expected value is a polynomial in p. We'll do some examples and try to
figure out what configurations are optimal, where optimality can be defined
in a few different ways. We give some complexity results for
computing the expected value and get closed form
expressions for some specific classes of graphs.
This is joint work with three students through Lafayette's REU program:
Alison Bailey, Matt Patton and Jenn Scancella.
Bio-Sketch:
Gary Gordon is a professor in the math department at Lafayette College. He
received a bachelors degree from the University of Florida and his Ph.D.
from the University of North Carolina. His mathematical interests include
combinatorics (especially graph theory and combinatorial geometry), geometry
and algebra. His primary research focus concerns the Tutte polynomial and
its application to matroids, antimatroids and greedoids. He taught at
Williams College and worked in industry prior to teaching at Lafayette. He
has spent sabbaticals as a visitor at DIMACS and at North Carolina. He
currently directs Lafayette's REU program for undergraduate research, and he
also directs the LVAIC math problem competition each fall. He has
co-authored several papers with undergraduates, primarily in graph theory.
| Title: | Dynamic Programming Approximations for the Dynamic Fleet Management Problem |
|---|
| Author: | Professor Huseyin Topaloglu, Cornell ORIE |
|---|
| Time: | Thursday 11/14/02 12:00-1:00pm |
|---|
| Place: | Mohler Laboratory Room 355 | |
|---|
| Info: |
email
webpage
presentation
paper
| |
|---|
Abstract:
We consider the dynamic fleet management problem with stochastic demand
arrivals and multiple vehicle types. Common engineering practice for
this problem is to formulate it as a large integer multicommodity flow
problem on a state-time network using the expected values of the future
demand realizations. For moderate sized instances of the problem, this
approach quickly becomes infeasible due to the size of the integer
program involved or becomes a myopic solution scheme because of short
planning horizons.
General stochastic or dynamic programming formulations of the problem
suffer from the large number of possible demand realizations and large
dimensionality of the state vector. The approach we present approximates
the value function in the dynamic programming formulation of the problem
and iteratively updates the approximation using Monte Carlo samples of
the random quantities.
We investigate further partitioning of the dynamic fleet management
problem. Classical stochastic programming approach follows temporal
decomposition. We propose partitioning the problem temporally _and_
geographically. This approach yields much smaller subproblems (with
network structure) and also mimics the informational decomposition in
the real world quite well.
Bio-Sketch:
Prof. Topaloglu received his PhD in Operations Research from Princeton
University in 2001. He spent another year in Princeton University as a
research fellow working on real world transportation problems arising
from the railroad industry before joining the faculty of School of
Operations Research and Industrial Engineering in Cornell in 2002. His
research interests are in the areas of stochastic dynamic programming
applications to operational and strategic problems in transportation and
logistics.