|
|
|
|
Integer
Programming
|
|
Syllabus-Integer 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
Add-In 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 add-ins 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.5-7.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/10-3/12: Spring Break
|
|
|
|
|
16
|
|
Traveling
Salesman Problem |
|
|
7
|
HW
7
|
|
17
|
|
Pure 0-1 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
|
|
|
12-13
|
|
|
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 |
|
|
|
|
|
|
