For *these syllabus you will need to download Acrobate Reader (for MAC) or Acrobate Reader (for PC) to view
Find below selected syllabus for the classes. These syllabus will change from semester to semester but the general outine will remain similar.
Industrial Engineering |
Statistics and Probability |
Optimization |
|
|
|
PREREQUISITES: ME 366M or equivalent (Operations Research Methods); an understanding of linear algebra; some acquaintance with Fortran or C; a working knowledge of at least one computer programming language.
TEXTS Required: Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, Belmont, MA, 1997.
Recommended: Linus Schrage, Linear, Integer, and Quadratic Programming with LINDO ,
The Scientific Press, South San Francisco, 1984.
OBJECTIVE: To develop a thorough and complete understanding of linear programming in order to be able to undertake more advanced work in optimization. This will be achieved by a detailed presentation of theory, a discussion of applications, and the development of related software.
GRADING: Homework - 8%
Programs - 7%
First Exam - 20% (Thurs. Oct. 2)
Second Exam - 25% (Tue. Nov. 4)
Final Exam - 40% (Wed. Dec. 10, 9-12 PM)
NOTE: Homework that is one class late will be penalized 10%; it will not be accepted after that date. All students must take the exams when scheduled. There will be NO make-up exams and there will be NO incompletes in the course; every student will get a grade.
Homework and midterm exam solutions will be posted outside my office. If you want to copy them, please do so within one week of posting. After that time, you will have to borrow a copy from one of your classmates. Final exams will be kept until the end of January. They will be discarded on February 1.
COURSE SYLLABUS (tentative)
| CHAPTER | TOPIC | PROBLEMS |
| 1.2, 1.5 | Problem Formulation, Review of Linear Algebra | 1.11, 1.14, 1.15, 1.16, 1.17 |
| 1.3 | Piecewise Linear Problems | 1.3a 1.4, 1.5, 1.8 |
| 1.1, 3.1-3.3, 3.5 | The Simplex Method | 3.2, 3.4, 3.12, 3.17, 3.20c |
| 2, 3.6, 4.8-4.9 | Interpretation of the Simplex Method | 2.2, 2.6(a)b, 2.10, 2.17, 2.22, 4.41, 4.42, 4.44 |
| 4 | Duality | 4.1, 4.4, 4.7, 4.9, 4.19 |
| 3.3 | Revised Simplex Method | 3.6, 3.17d, 3.21e, 3.23f |
| 3.3, 3.7 | Efficient Procedures for Computing Inverse | Handout |
| 5.1-5.4 | Sensitivity Analysis | 5.1, 5.2, 5.6, 5.8 |
| 5.5 | Parametric Programming | 5.12, 5.14 |
| 3.4, 4.5 | Degeneracy | |
| Notes | Bounded Variables | 3.25 |
| 9 | Interior Point Methods | 9.11, 9.12 (optional), 9.15 |
| 6.4 | Decomposition Techniques |
a Note that f(x) = max{1‚x,0,2x‚4}.
b Make us of the fact that L is in standard form and that a BFS must have n active constraints.
c Part (b) should be "second" row of tableau.
d Use revised simplex method.
e Use revised simplex method for part (a).
f For part (a) us reasoning not algebra. What do you know about the nonbasic variables in each case?
COMPUTER ASSIGNMENTS
During the semester you will be asked to write a number of computer programs implementing some of the methods discussed in class. These programs can be written in any language and run on any machine you choose, circumstances permitting. The codes should be well-documented with comments so someone reviewing them can understand the logic even if he or she is not familiar with the language. In addition, input and output should be well thought out. Interactive codes are fine if the user is not overburdened with input requests. Output should be tabularized and easy to read. Often you will be asked to provide the solution to a sample problem.
Most assignments will have to be done on a UNIX workstation because they involve commercial packages. Therefore, it is necessary to get a UT computer account as well as an account for the ME workstation RS/6000 laboratory on the third floor of ETC. See Sue Ponder for ME accounts.
A number of the assignments will require you to solve problems using OSL, an optimization library of subroutines written in Fortran by IBM, that is installed on one of the workstations in the ME laboratory. OSL can be called from a C program but I think it is easier to call it from a Fortran a program. As an alternative, you can use CPLEX which is written in C. This package can be accessed from the UT Computation Center AIX systems, including "Nutmeg" and the other "spice" machines. The accounting code for these machines is ADS. For more information, see:
http://www.utexas.edu/cc/math/CPLEX/
In general, each assignment you turn in should include:
1) Name, date, class, title of assignment.
2) Well-documented code.
3) Input files if not an interactive problem; if interactive, provide a printout of the session.
4) Statement of model. If solving an LP, for example, provide the model in algebraic form and the data.
5) Results in tabularized, or other easy to read form.
Assignments:
1) Matrix Generation and Solving Simultaneous Equations
Part 1. Write a random matrix generator for an n€m matrix A = (aij) that has a prespecified density. Input should include n, m, a general lower bound (L) for each element, an upper bound (U) for each element (that is, L < aij < U), and density factor r, where 0 < r < 1. Note that if r = 0.4, this means that there is a 0.4 probability that any element aij will not be zero or that on average, 4 out of 10 elements will be nonzero. For each element in the A matrix, you should first sample from a continuous uniform distribution between 0 and 1 to determine whether or not the element should be set to zero. If the result indicates that it should be nonzero, you should draw a second random number between 0 and 1 and then scale it between L and U. Finally, provide a subroutine that checks to see if any row or column has all zeroes. If so, discard the matrix and start again.
Part 2. Write a program to solve an m€m system of simultaneous equations (Bx = b). Use a Gauss-Jordan approach to finding the inverse of a nonsingular square matrix (e.g., see page 49 in Bazaraa et al. (1990) or the algorithm in Murty (1983) on page 104, ß3.3.2, that finds
B‚1). Test you program by using the code that you developed in Part 1 to generate a 10€10 random matrix with r = 0.6, L= ‚10, and U = 30. The right-hand-side vector b should have a density of 0.8, and each component bi should be randomly distributed between 0 and 50. Provide results for one sample problem. Determine the computational complexity of your matrix inversion routine.
Due: September 18
2) Using IMSL routines (see http://www.utexas.edu/cc/software/math.html)
Use the IMSL routines on the UT computer system to solve the same set of simultaneous equations that you solved in Assignment 1. Obtain solutions four different ways: (1) with the LU factorization routines (LFTRG and LFSRG), (2) (optional) with the Cholesky factors (CHFAC and LFSDS) (requires a symmetric matrix), (3) with the routine that solves Bx=b directly (LSLRG), and (4) by first finding an inverse of a square matrix (LINRG) and then computing the product of a matrix and a vector (MURRV).
Due: September 25
3) Working with compressed matrices
Randomly generate two matrices, A and B, both having 0.6 density. Make A 7ð€10 and B 10€8. Using three vectors, rewrite each matrix in compressed column form. In this representation the components of the first vector are the number of nonzero elements in each column of the original matrix. The length of this vector is equal to the number of columns of the original matrix. The components of the second vector are the row indices of the nonzero elements of the respective columns; the components of the third vector are the nonzero column elements themselves. The second and third vectors are of length equal to the number of nonzero elements in the original matrix.
Write a routine that takes as input any two matrices in compressed form, multiplies them together to produce a third matrix, C, and then stores C in compressed form. The routine should be efficient in the sense that only nonzero elements are multiplied together.
Due: October 9
4) Using a commercial LP code
Part 1. Use OSL on a workstation to solve the same set of simultaneous equations that you solved in Assignment 1.
Part 2. Also, solve a 10€20 LP. Use your random matrix generator with the same parameters from Assignment 1 to generate the LP. Each constraint should have 0.7 chance of being <, and a 0.3 chance of being >.
Due: October 16
5) More to come.
General References
1) M. S. Bazaraa, J. J. Jarvis and H. D. Sherali, Linear Programming and Network Flows, Second Edition, John Wiley & Sons, New York, 1990.
2) A. Brooke, D. Kendrick, and A. Meeraus, GAMS: A User's Guide, The Scientific Press, South San Francisco, 1988.
3) Saul Gass, Linear Programming, Fourth Edition, McGraw Hill, New York, 1975.
4) G. Hadley, Linear Algebra, Addison-Wesley, Reading, MA, 1973.
5) Katta F. Murty, Linear Programming, John Wiley & Sons, New York, 1983.
6) G. Strand, Linear Algebra and its Applications, Third Edition, Harcourt Brace Jovanovich, San Diego, CA, 1988.
7) Robert J. Vanderbei, Linear Programming: Foundations and Extensions, Kluwer Academic Press, Boston, 1996.
Reference List for Interior Point Methods
1) J. N. Hooker, "Karmarkar's Linear Programming Algorithm," Interfaces, Vol. 16, No. 4, pp. 75-90 (1986).
2) R. E. Marsten, R. Subramanian, M. Saltzman, I. Lustig, and D. Shanno, "Interior Point methods for Linear Programming: Just Call Newton, Lagrange, and Fiacco and McCormick," Interfaces, Vol. 20, No. 4, pp. 105-116 (1990).
3) K. A. McShane, C. L. Monma, and D. Shanno, "An Implementation of a Primal-Dual Interior Point Method for Linear Programming," ORSA Journal on Computing, Vol. 1 No. 2, pp. 70-83 (1989).
4) I. C. Chow, C. L. Monma, and D. F. Shanno, "Further Development of a Primal-Dual Interior Point Method," ORSA Journal on Computing, Vol. 2 No. 4, pp. 304-311 (1990).
5) I. J. Lustig, R. E. Marsten and D. F Shanno, "Computational Experience with a Primal-Dual Interior Point Method," Linear Algebra and its Applications, Vol. 152, pp. 191-222 (1991).
6) R. E. Marsten, M. J. Saltzman, D. F. Shanno, G. S. Pierce, and J. F. Ballintijn, "Implementation of a Dual Affine Interior Point Algorithm for Linear Programming," ORSA Journal on Computing, Vol. 1 No. 4, pp. 287-297 (1989).
7) S. Mehrotra, "Implementations of Affine Scaling Methods: Approximate Solutions of Systems of Linear Equations Using Preconditioned Conjugate Gradient Methods," Technical Report 89-04, Dept. of Industrial Engineering and Management Science, Northwestern University, Evanston, IL (1989).
8) I. Adler, N. Karmarker, M. G. Resende and G. Veiga, "Data Structures and Programming Techniques for the Implementation of Karmarkar's Algorithm," ORSA Journal on Computing, Vol. 1 No. 2, pp. 84-106 (1989).
PREREQUISITES: Graduate standing and familiarity with computers.
TEXTS Required: A. Shtub, J. F. Bard, S. Globerson, Project Management: Engineering, Technology, and Implementation, Prentice Hall, Englewood Cliffs, NJ, 1994.
OBJECTIVE: The project is the framework in which virtually all new products and systems are designed, developed, tested, and implemented. For complex systems, the challenge is to organize, coordinate, and control vastly different types of resources so that risk and conflict are minimized, and budgets and schedules are maintained. Projects may involve dozens of firms and thousands of people who need to be managed. They need to know what has to be done, who is to do it, when it should be done, how it will be done, and what resources will be used. Proper planning is the first step in communicating these intentions. The purpose of this course is to convey the methods and tools that have been developed over the last few decades to carry out these functions. In so doing, we will consider the evaluation of competing alternatives, the organization of a project, the scheduling of tasks and resources, and the role of management over time.
GRADING: Homework - 10%
Team Project - 20%
First Exam - 20% (Thursday, Feb. 23)
Second Exam - 20% (Tuesday, April 4)
Final Exam - 30% (Saturday, May 13, 2‚ 5 PM)POLICIES: All students must take the exams when scheduled, including the final --‚‚ no exceptions. There will be NO make-up exams and there will be NO incompletes in the course; every student will get a grade. Furthermore, there will be no extra assignments for those wishing to improve their overall grade.
All University of Texas procedures regarding academic dishonesty will be followed exactly as prescribed.
COURSE SYLLABUS
| 1 | Introduction: course outline | 1-5, 1-6, 1-8, 1-14, 1-17 |
| 2.1-2.6 | Engineering economics | 2-1, 2-5, 2-7, 2-10, 2-12, 2-14, 2-18, 2-19, 2-21 |
| 2.7 | Utility theory | 2-24, 2-26, 2-27, 2-29, 2-32 |
| 3.1-3.5 | Simple evaluation techniques | 3-1, 3-5, 3-7, 3-9, 3-11 |
| 3.7 | Decision trees | 3-16, 3-17, 3-19, 3-22 |
| 4.1-4.3 | Multiattribute utility theory | 4-1a, 4-5, 4-7, 4-8, 4-10 |
| 4.4 | Analytic hierarchy process | 4-1b, 4-2b, 4-6, 4-9 |
| 5.1-5.3 | Organizational structures | 5-3, 5-5, 5-7, 5-12 |
| 5.4 | Work breakdown structure | |
| 6.2 | Concurrent engineering | 6-6, 6-7, 6-13, 6-14(a, b, or c) |
| 6.3-6.5 | Risk/configuration management | |
| 6.7 | Total quality management | |
| 7.1-7.3 | Duration of project activity | 7-2, 7-4, 7-5, 7-6 |
| 7.4-7.11 | CPM/PERT scheduling | 7-14, 7-15, 7-19, 7-20 |
| 8 | Budgeting techniques | |
| 9 | Resource management | |
| 10 | Life-cycle costing | |
| 11 | Project control | |
| 12.1-12.4 | Issues in R&D management | |
| 12.5 | Parallel funding | |
| 12.6 | Managing the R&D portfolio | |
| 14 | Project termination |
TEAM PROJECT
To gain a better understanding of the concepts and techniques presented in the course, and to learn how to implement these techniques using a software package, teams of 2 -3 students will be formed to work on the thermal transfer plant case study included at the end of each chapter. Alternatively, a team may define its own project by the second week of class and perform a similar analysis.
As indicated in the text, not all the information required for each assignment is given. Before proceeding, it may be necessary for the group to research a particular topic and to make some logical assumptions. Accordingly, there is no "correct solution" to compare recommendations and conclusions. Each assignment should be judged with respect to the availability of information and the force of the underlying assumptions.
This course is an outgrowth of Dr. Barnes' research efforts over the last four or five years into AI based direct search methods for the solution of very difficult combinatorial problems. These methods have been conclusively shown to be superior to the classical methods of the past. During this time, while working with Fred Glover, Manuel Laguna, and with his graduate students, Dr. Barnes has become a recognized leader in this area.
The course will include such topics as reactive and adaptive tabu search methods, simulated annealing, genetic algorithms, and greedy randomized adaptive search methods (GRASP). Emphasis will be placed on the underlying theoretical context of these methods and the similarities between them as well as their distinguishing characteristics. Most of the course material will be drawn from current archival literature, including several of Dr. Barnes' papers dealing with production scheduling applications, general and flexible job shop scheduling problems and generalized vehicle routing problems.
Homework #1
Numerical Search Methods
Numerical search overheads
Dichotomous Search Code
Greedy Randomized Adaptive Search Procedure Overheads
An Overview of Grasp Methodology and Applications (article)
A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem (article)
A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.(article)
New Heuristics for the Flow Line Problem with Setup Costs .(article)
Code Listing associated with above article (grasp.c)
Simulated Annealing Overheads
Simulated Annealing: A Tool for OR (article)
A Survey of Simulated Annealing Research Problems (article)
Jobshop Scheduling by Simulated Annealing Overheads
Job Shop Scheduling by Simulated Annealing (article)
SA Metaheuristics for the VRPTW overheads
SA Metaheuristics for the Vehicle Routing Problem with Time Windows (article)
SA (ADA) Code Description
Example Graphs for ADA
sat1.c, sa.h, sa.c code
sat2.c code and data
Genetic Algorithms overheads
A Gentle Introduction to Genetic Algorithms (article)
Genetic Local Search Algorithms for the Traveling Salesman Problem (article)
GAC - c code genetic algorithms
Tabu Search Overheads
Tabu Search Tutorial (article)
Tabu Search Part I (article)
Tabu Search Part II (article)
Tabu Search Applied to the Quadratic Asssignment Problem (article)
Simulated Annealing and Tabu Search in the long Run: A Comparison on QAP Tasks (article)
An Overview of Tabu Search Approaches to Production Scheduling Problems (article)
Tabu search methods for a single machine scheduling problem (article)
Intelligent scheduling with Tabu Search: An application to . . . (article)
TS Code for scheduling jobs with linear delay penalties and sequence dependent set up costs
Solving the Multiple-Machine Weighted Flow Time Problem using TS (article)
TS Code for scheduling jobs on parallel processors to minimize delay penalties
Solving the Job Shop Scheduling Problem with Tabu Search (article)
TS Code for the Job Shop Scheduling Problem with Tabu Search
New Tabu search Results for the Job Shop Scheduling Problem
The Reactive Tabu Search (article)
Solving the traveling-salesman problem with time windows using tabu search
Overheads for above article
A note on Hashing Functions and Tabu Search Algorithms
A Hierarchical Classification Scheme for the General Vehicle Routing problem
Solving the Vehicle Routing Problem with Time Windows using Reactive TS
RTS code for the VRPTW