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 Ch. 1 7.1-7.4 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 BB Supl. 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

Operations Research Models and Methods
Internet
by Paul A. Jensen