Main navigation | Main content
2002-2003 Program: Optimization
Daniel Bienstock (Department of Industrial Engineering and Operations Research, Columbia University) dano@ieor.columbia.edu http://www.ieor.columbia.edu/~dano
Large-Scale Linear Programming Presentation Slides
Linear Programming is the central tool of Mathematical Programming. Linear programming models are flexible enough to adequately describe many realistic problems arising in modern industrial settings, while at the same time taking advantage of the considerable expertise on computational linear algebra that has been developed during the last fifty years. As a result, linear programming models are abundantly used in logistics, transportation, finance and many other practical applications.
Linear Programming has undergone profound changes during the last twenty years, resulting in codes that are thousands (and sometimes, millions) of times faster than what was available just fifteen years ago. Yet difficult challenges persist, in the form of large-scale linear programming problems arising in routing, network design, chip design and other settings. In fact, large problem instances render even the best of codes nearly unusable.
In this lecture we will survey fundamentals of Linear Programming theory, with special emphasis on recent developments, and in particular, on techniques geared to handling very large instances.
E. Andrew Boyd (Senior Vice President, Science and Research and Chief Scientist, PROS Revenue Management) aboyd@prosrm.com http://www.prosrm.com
Revenue Management and Dynamic Pricing Slides: html pdf
Revenue management has been employed with tremendous success in the airline industry to manage ticket prices. Hailed by Bob Austrian of Banc of America Securities as ?one of the most exciting inevitibilities ahead? whose implications for profitability ? cannot be stressed enough,? many industries have adopted or are in the process of adopting revenue management and dynamic pricing.| This tutorial presentation will provide an introduction to the practice of revenue management and dynamic pricing while introducing the mathematical concepts that drive the underlying value proposition. Modeling and computational challenges will highlighted.
John R. Birge (Dean McCormick School of Engineering and Applied Science, Northwestern University) jrbirge@northwestern.edu
Stochastic Optimization Slides: pdf
Supply chain and logistics problems inevitably involve the consideration of random quantities such as uncertain demands, supplies, travel times,costs, and prices. This tutorial will present some fundamental stochastic optimization models to include such random events. The models will include decisions for network design, capacity, vehicle flows, and contract terms. We will then present a general framework for these stochastic optimization problems, their basic properties, algorithms, and solutions. The discussion will focus on discrete-time models but will also introduce continuous-time models and real-option approaches to deal with financial issues in supply chains and logistics.
Robert Fourer (Northwestern University) 4er@iems.nwu.edu
AMPL Hands-on Session Slides: html pdf ppt
Modeling languages describe optimization problems to computer systems in the symbolic terms familiar to people, rather than in the obscure input forms convenient to optimizing algorithms. In typical use, a symbolic model and specific data are automatically translated to a problem instance and submitted a solver; subsequent results are automatically retrieved and translated back to forms convenient for inspection and analysis. A single modeling language can be interfaced to many solvers, providing access to techniques for a range of linear, nonlinear, and discrete problems, and encouraging comparisons between alternative algorithms for individual problem types.
This session will provide an introduction to AMPL, one of the more widely used optimization modeling languages, through a series of simple linear and integer programming models. Participants will have a chance to experiment with AMPL models and to ask how a modeling language might be applied to problems of special interest to them.
Gregory Glockner, Ph.D. (Optimization Product Manager, ILOG, Inc., Mountain View, CA) gglockner@ilog.com
Discovering Combinatorial Optimization with the ILOG Optimization Suite Slides: html pdf powerpoint
ILOG is the world leader in optimization technology, supplying the world's most powerful and comprehensive components for developing optimization applications. With core algorithms from mathematical programming and constraint programming, the ILOG Optimization Suite is highly effective at solving industrial and research problems in constraint satisfaction and optimization. The ILOG Optimization Suite powers the leading software for supply chain management and logistics optimization.
In this tutorial, we will use a rapid development system to explore basic combinatorial optimization problems. The sample problems will illustrate powerful techniques like constraint propagation and iterative optimization, which are invaluable to solving real-world optimization applications in supply chain and logistics. The tutorial will emphasize hands-on examples and their relationship to larger applications.
Jon Lee (IBM T.J. Watson Research Center) jonlee@us.ibm.com
Service Parts Logistics
Large spare-parts inventory and distribution logistics operations involve over 10K part numbers, with annual volume in the several M. In recent years, market forces have changed the way these services are sold and delivered. These changes are being made to address the needs to improve customer satisfaction and to drive down costs associated with service delivery. For example, the IBM/ITS North American maintenance organization focused on specific areas in order for IBM to drive down costs and improve the customer experience. Specifically, (i) a value-based pricing scheme tied to service levels, and (ii) a call screening process enabling remote diagnosis of problems. These changes led to challenging logistics requirements involving the deployment of labor and parts in order to satisfy contracted service levels while containing inventory and transportation costs.
The Optimization Center of the Mathematical Sciences Department at IBM Research and IBM's ITS/SPS organization, in collaboration with the Lehigh University Department of Industrial and Manufacturing Engineering have been developing a next generation logistics system designed for flexible and optimal control of spare parts inventories. IBM has migrated to a Parts Procurement Time (PPT) performance measure, which monitors whether the frequency at which parts are delivered to a customer location within a contractually determined time interval aggregated across machine service groups and geographies meet acceptable thresholds. I will describe the optimization model and algorithms that are currently being successfully deployed which have led to increased service, and reduced transportation costs, and dramatically reduced inventory costs.
Andrew J. Miller amiller@engr.wisc.edu (University of Wisconsin)
Integer Programming Slides: t410g1us.htm t410g1us.pdf hyg2gny9.htm hyg2gny9.pdf IP_IMA.ppt IP_IMA_2.ppt
This tutorial is about the theory and algorithms for solving mixed-integer programming problems. We will focus on the recent LP-based methodologies of branch-and-cut and branch-and-price, which are the techniques that make it possible to solve large-scale problems, but we will discuss briefly other heuristic methods as well.
Martin W.P. Savelsbergh (School of Industrial and Systems Engineering, Georgia Institute of Technology) mwps@isye.gatech.edu
Vehicle Routing & Scheduling Slides: VRP_part1.pdf VRP_part2.pdf
This tutorial is about models and algorithms for solving vehicle routing and scheduling problems. We will cover heuristic as well as optimization techniques. We will demonstrate the use of these techniques in two practical applications: vendor managed inventory resupply and linehaul scheduling.
Martin Skutella (Current Affiliation: Sloan School of Management, Room E40-123, Massachusetts Institute of Technology, 50 Memorial Drive, Cambridge, MA 02142-1347, skutella@mit.edu Permanent address in Berlin: Technische Univ. Berlin, Fak. II - Mathematik und Naturwissenschaften, Institut f. Mathematik, Sekr. MA 6-1, Str. des 17. Juni 136, 10623 Berlin, Germany, phone: +49+30-314-25747 fax: +49+30-314-25191 skutella@math.tu-berlin.de)
Flows Over Time Slides: pdf
The intention of the tutorial is to give an introduction into the area of "flows over time" or "dynamic flows." Flows over time have been introduced about forty years ago by Ford and Fulkerson and have many real-world applications such as, for example, traffic control, evacuation plans, production systems, communication networks, and financial flows. Flows over time are modelled in networks with capacities and transit times on the arcs. The transit time of an arc specifies the amount of time it takes for flow to travel from the tail to the head of that arc. In contrast to the classical case of static flows, a flow over time specifies a flow rate entering an arc for each point in time and the capacity of an arc limits the rate of flow into the arc at each point in time. The topics covered range from the classical results of Ford and Fulkerson on maximal s-t-flows over time to very recent approximation results for flows over time with multiple commodities and costs.
IMA Tutorial: Supply Chain and Logistics Optimization September 9-13, 2002
Connect With Us: |