**GEORGE
MASON UNIVERSITY**

Systems
Engineering and Operations Research Department

**Time:** Mondays,
4:30-7:10p.m; David King Hall 2053

**Professor Karla L. Hoffman**

**Office:** SciTech
Building II, Room 119

**Phone:** (703)993-1679
or 993-1670 (secy); 993-1521 (fax)

**email:** khoffman@gmu.edu

**url:** iris.gmu.edu/~khoffman

**Homepage for course: **http://iris.gmu.edu/~khoffman/or642_s04/or642_s04.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). Mr.
Stephen Charbonneau will be presenting some background lectures on how to use
advanced indexing and how to embed VBA into your modeling effort.

· 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, economcis, 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.

**Course Outline **

Topic I. Introduction to discrete optimization.

Formulations and modeling.

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

Topic III. Optimality, Relaxation, and Bounds

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 `

· Decompositions

Topic VI. Heuristic Procedures

`· Performance measures for classic algorithms`

`· Lp-based algorithms`

· New techniques (e.g. Tabu Search, Genetic algorithms, simulated annealing)

Topic VII. Cutting plane approaches

`· Branch and Cut `

`· Polyhedral Theory`

· Facet Identification for structured integer programs

Topic VIII. Column generation procedures

Homework
problems will be assigned at each session. Some or all of the assignments will be collected and
graded.

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