2. Instructor Information
3. Course Objectives
This course treats combinatorial optimization problems and their mathematical models. Various deterministic optimization problems and their solution approaches are introduced. The problems include Knapsack, Traveling Salesman Problem, various Vehicle Routing Problems, Facility Location, Scheduling, Transportation and Assignment problems. The solution approaches include heuristics, metaheuristics(tabu search, genetic algorithm, simulated annealing, large neighborhood search), branch and bound, branch and cut, column generation and dynamic programming. 3 credit hours
4. Prerequisites & require
5. Grading
Attendance & Participation 10 %
Homework 20 %
Term Project 25 %
Mid Term 20 %
Final Exam 25 %
6. Course Materials
| Title |
Author |
Publisher |
Publication
Year/Edition |
ISBN |
7. Course References
(Recommended)
L.A. Wolsey, Integer Programming, Wiley, 1998
R. L. Rardin, Optimization in Operations Research, Prentice Hall, 1998
8. Course Plan
Discrete Optimization problems
Exact algorithms
Heuristic algorithms
Metaheuristic algorithms
9. Course Operation
Welcome to Discrete Optimization class.
Please read the attached syllabus.
PPT Lecture slides are available from plms. (Note that not all the contents are included. You need to fill them while you take the lectures).
10. How to Teach & Remark
Term project requires development of algorithms and their implementation as a software system for students’ choice of problems. Example problems are Traveling Salesman Problem (TSP), Vehicle Routing Problem with Time Windows (VRPTW), and Bin Packing Problem. Refer to the OR-Library (http://people.brunel.ac.uk/~mastjjb/jeb/info.html) for various problems. This is a group project. Up to 2 students can make a team and individual project is also possible. Each student is encouraged to implement Exact Algorithms (may use CPlex or Gurobi callable library), heuristics, and meta heuristics. Any programming languages such as C++, Python, Java can be used for the project. Further discussion will be provided during the semester. The project report and presentation video (~15 min) must be submitted.
Attendance
Students are expected to attend class. Students are responsible for all material presented in class.
Academic Dishonesty
The exams and homeworks must be done individually by each student.
11. Supports for Students with a Disability
- Taking Course: interpreting services (for hearing impairment), Mobility and preferential seating assistances (for developmental disability), Note taking(for all kinds of disabilities) and etc.
- Taking Exam: Extended exam period (for all kinds of disabilities, if needed), Magnified exam papers (for sight disability), and etc.
- Please contact Center for Students with Disabilities (279-2434) for additional assistance