IP&NF Home Page


56:272 Fall Semester 1998

The web site for 56:272 Integer Programming & Network Flows has been moved here.

In this course, combinatorial optimization problems are studied, using both integer programming and graph theoretic approaches.

Emphasis is on models and computational algorithms.

A course in optimization, such as 56:171 Introduction to O.R., is a prerequisite. (In particular, students should be familiar with the simplex method for linear programming!)

Topics

Integer Programming Models

Implicit enumeration (branch-&-bound) algorithms

Cutting plane algorithms for integer programming

Lagrangian & surrogate relaxation

Benders' decomposition procedure

Graphs, di-graphs, & networks

Shortest route & maximum flow problems

Transportation & assignment problems

Generalized & quadratic assignment problems

Minimum-cost network flow algorithms

Location problems in the plane & in networks

Routing (traveling salesman & Chinese postman) problems

Assembly-line balancing

Flowshop & Jobshop scheduling

Complexity of algorithms (NP-completeness)

Recent heuristic strategies:
genetic algorithms, simulated annealing, tabu search, etc.)

Go back to Dennis Bricker's home page.

http://www.icaen.uiowa.edu/~ie272

dennis-bricker@uiowa.edu

Last modified: 28 August 1998