Professor: Dr. Xinhui Zhang
Email: xinhui.zhang@wright.edu
Office: 234 Russ Center
Website: http://www.wright.edu/~xinhui.zhang/
Prerequisite: ISE 470 /HFE 670 Deterministic OR Models or EGR 704 Design Optimization
Course Description: Many problems that arise in industrial and socio-economic systems, such as equipment and manpower scheduling, airline scheduling, vehicle routing, telecommunications network design, VLSI design and testing and supply chain management, can be modeled as integer programs. Generic models that make up the field of combinatorial optimization also fit the integer programming format. The aim of this course is to present the theory and algorithm that have been developed to solve large scale problems. These techniques include branch and bound, cutting planes, Lagrangian relaxation, column generation and heuristic search. To be familiar with these techniques and to identify and exploit a familiar underlying structure is essential in solving these problems successfully. The goal of the course is to explore modeling techniques as well as understanding the algorithm. Applications will be drawn from diverse areas such as process planning, ground and air transportation, media allocation, telecommunication network design and routing, large scale circuit design, timetable and personnel scheduling, manufacturing, economics and finance and public service. A state of the art solver, Xpress, will be used. Students will be required to implement certain algorithms to a problem of their interests. Students with an optimization related research project are encouraged to take this course.
Textbooks
L. A. Wolsey, Integer Programming, John Wiley & Sons, New York, 1998.
Software:
Xpress from DASH Optimization. Web site at www.dashoptimization.com
Recommended Software References:
Applications of Optimization with XpressMP, DASH Optimization, Engle Wood, NY, 2000
Grading – In Class Students:
Homework - 25%
Midterm Exam - 25%
Term Project - 50%
Term Project
Each student will be asked to work on an optimization problem of your own interest. You will be asked to identify a problem, build the mathematical model, code it in Xpress and interpret the result. For in-class student, you will also need to give a 15 ~ 20 minute final presentation in class. Previous student projects include VLSI Testing and Optimization, Wireless Network Reliability Design and Routing, Search and Rescue Mission, Production Planning with Outsourcing and Order Discounts … etc.
Tentative Topics
1. Introduction (Chapter 1, Chapter 7.6)
Models and applications includes but not limited to process planning, manufacturing, transportation, telecommunication network design and routing, personnel scheduling
2. Mathematical Modeling (Handout and Xpress References)
3. Review of Linear Programming (Handout)
Reduce cost, shadow price/dual variable, reduced cost fixing
4. Relaxation and Bound (Chapter 2)
Various Relaxations, Upper and Lower Bounds
5. Branch and Bound (Chapter 7)
LP relaxation, search trees, preprocessing, implementation issues, linear programming based branch and bound, specialized Branch and bound;
6. Traditional Cutting Planes (Chapter 8)
Method of integer forms, primal all integer cuts, dual all-integer cuts
7. Polyhedral Theory (Chapter 9) *
Linear algebra; valid inequalities, branch and cut, the use of cutting planes
8. Lagrangian Relaxation (Chapter 10)
Relation to duality, subgradient methods, implementation, Lagrangian decomposition
9. Column Generation (Chapter 11)
Reformulation, Master and Sub Problems, Approximation, Branching
10. Neighborhood Search Heuristic and Meta-Heuristic (Chapter 12 and Handout)*
Neighborhood Search, GRASP, Simulated Annealing, Genetic Algorithm*
11. Robust/Stochastic Optimization (Handout) *
Uncertainty and modeling issues, stochastic integer program.
* Topics will be covered when time allows
References
General
[1] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, John Wiley & Sons, New York, 1988.
Mathematical Modeling
[2] “Application of Optimization with Xpress,” Dash Optimization, New York, 2000.
[3] H. P. Williams, “Model Building in Mathematical Programming”, 4th Edition, John Wiley & Sons, New York, 1999.
[4] M. W. P. Savelsbergh, "Preprocessing and Probing Techniques for Mixed Integer Programming Problems, ORSA Journal on Computing, Vol. 6, No. 4, pp. 445-454 (1994).
[5] U. H. Suhl and R. Szymanski, "Supernode Processing of Mixed-Integer Models," Working paper, Institut für Wirtschaftsinformatik und Operations Research, Free University of Berlin, Berlin, Germany, 1994.
[6] M. S. Bazaraa and J. J. Goode, "A Survey of Various Tactics for Generating Lagrangian Multipliers in the Context of Lagrangian Duality," European Journal of Operational Research, Vol. 3, pp. 322-338 (1979).
[7] M. L. Fisher, "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, Vol. 27, No. 1, pp. 1-18 (1981).
[8] M. L. Fisher, "An Applications Oriented Guide to Lagrangian Relaxation," Interfaces, Vol. 15, No. 2, pp. 10-21 (1985).
[9] Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Lance (1998), “Branch-and-Price: Column Generation for Solving Huge Integer Programs,” Operations Research, 46(3), 316-329.
[10] M. Desrochers, J. Desrosier, and M. Solomon, "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, Vol. 40, No. 2, pp. 342-354 (1992).
[11] M. W. P. Savelsbergh, "A Branch and Price Algorithm for the General Assignment Problem," Operations Research, 35: 831-841 (1997)
[12] Dept. of Mathematics and Computing Science, Eindoven University of Technology, Eindoven, The Netherlands, 1994.
[13] M. Grötschel and M. W. Padberg, "Polyhedral Theory," in E. L. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Chapter 8, pp. 251-305, John Wiley & Sons, New York, 1984.
[14] W. R. Pulleyblank, "Polyhedral Combinatorics," in G. L. Nemhauser, A. H. G. Rinnooy Kan, and M. J. Todd (Eds.), Handbooks in Operations Research and Management Science, Vol. 1, pp. 371-446, Elsevier Science Publishers, Amsterdam, 1989.
Branch and Cut Techniques
[15] H. Crowder, E. L. Johnson and M. W. Padberg, "Solving Large-Scale Zero-On Linear Programming Problems," Operations Research, Vol. 31, No. 5, pp. 803-834 (1983).
[16] M. Grötschel and M. W. Padberg, "Polyhedral Computations," in E.L. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Chapter 9, pp. 306-360, John Wiley & Sons, New York, 1984.
[17] K. L. Hoffman and M. Padberg, "Solving Airline Crew Scheduling Problems by Branch-and-Cut," Management Science, Vol. 39, No. 6, pp. 657-682 (1993).
[18] M. Padberg and G. Rinaldi, "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems," SIAM Review, Vol. 33, No. 1, pp. 60-100 (1991).
[19] C. Tovey, "Tutorial on Computational Complexity,” Interfaces, Vol. 32, No. 3, pp. 30-61 (2002).
Neighborhood Search Heuristics and Meta-Heuristics
[20] C. R. Reeves, “Modern Heuristic techniques for Combinatorial Problems,” John Wily & Sons, New York, NY, 1993.
Stochastic Optimization
[21] J. Birge, “Introduction to Stochastic Programming,” Springer, New York, 1997.