OR642: Combinatorial and Integer Optimization

GEORGE MASON UNIVERSITY

Systems Engineering and Operations Research Department

Spring, 2008

Time: Wednesdays, 4:30-7:10p.m; Innovation Hall 137
Office: SciTech Building II, Room 122
Phone: (703)993-1679 or 993-1670 (secy); 993-1521 (fax)
email: khoffman@gmu.edu
url: iris.gmu.edu/~khoffman

Office hours: Wednesdays: 2:00-3:30p.m. and by appointment

Text: Wolsey, L. Integer Programming Wiley, Interscience, 1998.

Software: You will be expected to use a modeling language to complete your project. You will be required to use the MPL modeling language (unless other arrangements are made with Dr. Hoffman).

· MPL (Maximal Software) available by downloading from the internet lab and they will download for you. (www.maximal-usa.com)

Course Description: This course is designed to introduce discrete optimization models and to provide the mathematical foundations of integer and combinatorial optimization models along with the algorithms that can be used to solve such problems. The course will stress the explosion of new results in integer and combinatorial optimization Some problem areas discussed are planning models such as capital budgeting, facility location and portfolio selection, design problems such as telecommunication and transportation network design, VLSI circuit design and the design of automated production systems, and real-time operational models such as real-time dispatching and scheduling, made-to-order production models, and real-time satellite scheduling and maneuvering. Examples from statistics, economics, politics and mathematics will also be presented. Polyhedral theory necessary to understand the new techniques will be covered in some detail, as will column-generation approaches. A tentative outline of the topics is provided below. This outline can change based on time limitations and the interests of the students. Although the text required will be used as much as possible, much of the material will be presented through readings, course notes and power-point presentations.

Course Outline

Topic I. Introduction to Discrete and Integer optimization. 




 Formulations and modeling.




Topic II. Linear programming review with emphasis on the use of the dual simplex method and barrier methods (since  these were not covered in the Intro to OR course). 




Topic III. Optimality, Relaxation, and Bounds 
 Definitions, Proofs of Optimality and General View of the Problem




Topic IV. Approaches to solving integer programming problems 




· Total enumeration, 
· Implicit enumeration,
· Bounding algorithms 
· Tree search




Topic V. Relaxation and Decomposition techniques 




· Lagrangian relaxations 
· Linear-programming relaxations 
· Dantzig-Wolfe and Benders Decompositions




Topic VI. Heuristic Procedures 




· Performance measures for classic algorithms
· lp-based algorithms
· New techniques (e.g. Tabu Search, Evolutionary algorithms, simulated annealing, Swarm Technology, Neural Nets) 




Topic VII. Cutting plane approaches




· Branch and Cut 
· Polyhedral Theory
· Facet Identification for structured integer programs




Topic VIII. Column generation procedures
 Dantzig Wolfe and Benders in Deta
 
Topic IX. Real-time applications of Integer Optimization and why these problems are different




 

Homework problems will be assigned at each session. Some or all of the assignments will be collected and graded. Each graded assignment will be worth 10 points. I will drop the lowest grade and then average the remainder of the assignments. Then, multiply the result by 10, so that the maximum grade one could get on homework is 100.

It is likely that the mid-term will be in-class and the final will be a take-home exam. In class exams will be open book and open notes. There will also be one project that will require the formulation and solution of a collection of integer programming problems. The project can be done jointly with one other student, or individually.

The midterm will count for 25% of the grade, the take-home final will count for 35% of the grade, homework assignments will be averaged and count for 20% of the grade and the project will count for 20%,

Fundamental Rules:

(1) Make-up exams will only be given for extreme situations, and only if I am contacted before the exam is given and full arrangements are established. Full adherence to this policy is the responsibility of the student.

(2) The exam dates above are tentative, and it is the student's responsibility to keep abreast of changes.

(3) Homework will be assigned each class, and usually collected. All work must be clearly written. Illegible work will not be accepted.

(4) There is a penalty of 10% of the total grade for each day homework is late. Homework can be delivered via class, email, fax, or under my door. 9:00am on the day after the class is the due date for all homework assignments.