Sample Syllabus for a Semester Course on
Integer Programming and Network Flows

using Optimization in Operations Research
by Ronald L. Rardin, Prentice Hall, 1998

Audience

This course is intended as an advanced undergraduate or beginning graduate course in integer programming and network flows for students in engineering, management and mathematics.

Background

This course assumes elementary background in multivariate differential calculus and in linear algebra, plus familiarity with vector/matrix notation and arithmetic. Most students will also have had an introductory course in deterministic operations research that includes at least formulation of mathematical programs plus the simplex method and duality for linear programming. Still, self study of Chapter 2, Sections 5.1-5.3 and Sections 7.3-7.5 can serve as an adequate substitute.

Topics

Schedule (less one week of examinations)

Week Topics Reading
1 Class Organization
Nature of Discrete Optimization
Lumpy LPs and Fixed Charges
Section 2.5
Section 11.1
2 Knapsack, Capital Budgeting, Set Packing/Covering/Partitioning
Assignment and Matching Models
TSP and Routing Models		 Sections 11.2-11.3
Section 11.4
Section 11.5
3 Facilities Location and Network Design
Processor Scheduling
Solving by Total Enumeration		 Section 11.6
Section 11.7
Section 12.1
4 Elementary Relaxations
Strengthening LP Relaxations
Lagrangian Relaxations		 Section 12.2
Section 12.3
Supplement 1
5 LP-Based Branch and Bound Section 12.4
6 Valid Inequalities
Elements of Polyhedral Combinatorics
Branch and Cut		 Section 12.5
Supplement 2
7 Improving Heuristics for Discrete Optimization
Tabu, Simulated Annealing, Genetic Algorithms
Constructive Heuristics for Discrete Optimization		 Section 12.6
Section 12.7
Section 12.8
8 Shortest Path Models
Dynamic Programming Approach and Bellman-Ford
All to All and Floyd-Warshall		 Section 9.1
Section 9.2-9.3
Section 9.4
9 Nonnegative Costs and Dijkstra
Longest Paths and CPM
Discrete Dynamic Programming		 Section 9.5
Sections 9.6-9.7
Section 9.8
10 Minimum Cost Network Flows
Cycle Direction-Based Search
Integer Optimal Flows and Total Unimodularity		 Section 10.1
Sections 10.2-10.3
Section 10.4
11 Transportation and Assignment Models
Multicommodity and Gain/Loss Flows
Maximum Flows and Minimum Cuts		 Section 10.5
Section 10.9
Section 10.6
12 Maximum Flow Algorithms
Cycle Canceling Algorithms for Min Cost Flow		 Supplement 3
Section 10.8
13 Network Simplex Algorithm
Minimum Spanning Trees		 Section 10.7
Supplement 4
14 Elements of Computational Complexity Theory Supplement 5

Supplements

Although the text provides foundations and intuitions for nearly all topics of this course, instructors will need to add rigor where the level of the course requires formal proofs. Also, the following supplemental notes are suggested:
  1. Lagrangian Relaxation: Extensions to the book's treatment of Lagrangian relaxation including subgradient search for optimal Lagrange multipliers.
  2. Polyhedral Combinatorics: Extensions to the book's treatment of valid inequalities and Branch and Cut with elements of polyhedral combinatorics such as the convex hull of integer solutions, facet inducing inequalities, and separation.
  3. Maximum Flow/Minimum Cut: Extensions to the book's treatment of maximum flow problems with the idea of a cut set, the Ford-Fulkerson algorithm, and equality of maximum flow and minimum cut.
  4. Minimum Spanning Trees: The minimum spanning tree problem on an undirected graph and greedy algorithms for solving it.
  5. Computational Complexity Theory Elements of computational complexity theory including measuring performance by order of computation, the polynomial-time definition of efficient, classes P, NP, and NP-Complete, and reduction proofs of NP-completeness.

Computer Support

The course can be effectively conducted using only standard class optimization software such as GAMS, AMPL, or LINGO. It is strongly recommended that students use such software to solve all assigned formulations that have numbers.

Back to Optimization in Operations Research mainpage