OR642: Combinatorial and Integer Programming

GEORGE MASON UNIVERSITY

Systems Engineering and Operations Research Department

Time:              Wednesdays, 4:30-7:10p.m; Robinson Hall A245

Professor Karla L. Hoffman
Office:             SciTech Building II, Room 119
Phone:             (703)993-1679 or 993-1670 (secy); 993-1521 (fax)
email:              [email protected]
url:                  iris.gmu.edu/~khoffman

Homepage for course:  http://iris.gmu.edu/~khoffman/or642_s05/or642_s05.html

Office hours: Mondays: 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. The problem areas discussed will include planning models such as capital budgeting, facility location and portfolio selection, and design problems such as telecommunication and transportation network design, VLSI circuit design and the design of automated production systems. 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. 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, there will be much supplemental material covered.

Goals for the Course:  By the end course, you should be able to:

–Given an optimization problem, formulate an appropriate integer linear model

–Understand the basic mathematical structure of the model

–Understand the techniques that could be used to solve the model.

–Understand how to use a modeling language and/or commercial solver to solve the model.

–Understand the limitations of “off the shelf” solvers and how to tune their parameters to improve performance.

–Understand how to design a solver for a specific problem class.

 

WebCt:  Lecture notes,  presentations, and assignments will be found on webct.   The url for webct is: webct41.gmu.edu.   This site is password protected, and uses the same identification as your gmu email account.  Thus, userid is your gmu email id, and the password is your email password.

EMAIL:  I will communicate with the class through email, so please make sure that your gmu account is current and working!

Course Outline 

Topic I.     Introduction to discrete optimization.  
                Formulations and modeling.
 
Topic II.    Preprocessing the problem




Topic III.   Linear programming review with emphasis on the dual. 




Topic IV.    Optimality, Relaxation, and Bounds 




Topic V.     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 
Decompositions




Topic VI.    Heuristic Procedures 
Performance measures for classic algorithms
Lp-based algorithms
Tabu Search 
Genetic algorithms 
Simulated Annealing   
Neural Networks 




Topic VII.   Cutting plane approaches
Branch and Cut 
Polyhedral Theory
Facet Identification for structured integer programs
Chvatal-Gomory Cuts
Special-structure cutting planes




Topic VIII.  Column generation procedures




 

Grading:

•15% Homework (assigned weekly,  collected and some portion graded.  Each assignment will count 10 points)

•25% Mid-term  (in class exam;  open book and notes)

•35% Final (Take home exam)

•15% Project  (Can work with one other person, or individually)

•10% Class Participation

 

 

 

 

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 every day that a homework assignment is late.