

Integer
Programming


SyllabusInteger Programming Class


Required
Texts 
Integer Programming by Laurence A. Wolsey, John Wiley and Sons, 1998 

Integer Programming Presentation
Handouts, Spring
2003, by Paul A. Jensen 

Operations
Research Models and Methods, Paul A.
Jensen and Jonathan F. Bard, John Wiley Inc., 2003 
Optional
Text 
Integer and Combinatorial
Optimization, by Laurence A. Wolsey, George L.
Nemhauser, John Wiley Inc., 1999 
Computer
Programs 
Access to Microsoft Excel
version 97 or later for Windows or Mac OS. The Solver
AddIn will be used. 
Syllabus 
Many practical
problems have variables that are inherently discrete, and
approximate solutions assuming continuous variables are
not acceptable. Integer programming is the branch
of mathematical programming that deals with the solution
of such problems. We consider in this course the
modeling of practical problems with integer variables,
the theory
associated with finding integer solutions, and the computational
procedures necessary to implement solution algorithms. 
Exams 
There are three exams including
the final exam. All exams have equal weight in the exam
average. 
Class
Contribution 
The class contribution may
be one of the following.
 Find two articles
from the recent literature related to IP. Turn
in two page abstracts of the articles.
 Write at least two
new homework type problems with worked solutions.
Turn in problems and solutions.
 Make some modification
of the Excel addins that relate to modeling or solving
IP problems. Turn in a description of the modifications
and user instructions if appropriate.

Schedule
Meeting

Date

Subject

Wolsey

J/B

Notes

HW

1


Introduction to Class
IP Modeling



1


2


Special Case Problems

Ch.
1

7.57.8

2




Holiday





3


Optimality, Relaxation, and Bounds (W)

Ch.
2



HW
1

4


Total Modularity



3


5


Well Solved Problems (W)

Ch.
3



HW
2

6


Network Models





7


Matching and Assignments (W)

Ch.
4



HW
3

8


Greedy Algorithms


8.1

4


9


Dynamic Programming (W)

Ch.
5



HW
4

10


Review





11


Review




HW
5

12


Exam 1





13


Complexity and Problem Reductions (W)

Ch.
6




14


Finding a Solution by Enumeration


8.2

5


15


Branch and Bound (W)

Ch.
7

8.3

6

HW
6



3/103/12: Spring Break





16


Traveling
Salesman Problem 


7

HW
7

17


Pure 01 Programming



8


18


Branch and Bound for MIP



9

HW
8

19


Lagrangian
Relaxation 


10


20


Review 



HW
9

21


Review





22


Exam 2





23


Cutting Plane Algorithms (W)

Ch.
8

8.4



24


Cutting Plane Algorithm



1213


25


Strong Valid Inequalities (W)

Ch.
9

8.5


HW
10

26


Benders'
Method 


11


27


Heuristic Algorithms (W)

Ch.
12



HW
11

28


From Theory to Solutions (W)

Ch.
13




29


Review 






Final Exam 





