56:272 Integer Programming & Network Flows Fall Semester 2003

The screens used in presentation of the lectures are available for downloading:

They are available in PDF format (*.pdf), either full size (one or two cards per page) or half size (8 cards per page), from this web page. They may be viewed &/or printed by Adobe Acrobat Reader. (The arrows & buttons which appear are usually not effective when viewed as a PDF file.)

To view PDF-formatted files, FREE from Adobe.

List of Topics IP&NF Overview, (1).pdf, (2).pdf, or (8).pdf A preview of some of the graph & network problems to be studied in this course. Graphs & Networks Info (1).pdf, (2).pdf, or (8).pdf Basic notation & definitions of graphs & networks "Three Jealous Husbands" puzzle (1).pdf, (2).pdf, or (8).pdf Example of graph model "Milkman" Problem (1).pdf, (4).pdf Example of graph model Trees Spanning trees (1).pdf, (2).pdf, or (8).pdf Finding least-cost tree which includes all nodes of network Search trees (1).pdf, (2).pdf, or (8).pdf Using a tree structure to organize a combinatorial search Decision trees (1).pdf, (2).pdf, or (8).pdf Shortest Route Problem (1).pdf, (2).pdf, or (8).pdf Maximum Flow Problem (1).pdf, (2).pdf, or (8).pdf Given a source & destination, and capacities of links in a network, find the maximum quantity which can flow over one or more paths from source to destination. Project Management via Networks (1).pdf, (2).pdf, or (8).pdf Two network models: AOA (activity on arrow) and AON (activity on node) Critical Path Method (1).pdf, (2).pdf, or (8).pdf Minimum completion time = longest path from start to finish Crashing (1).pdf, (2).pdf, or (8).pdf Allocating resources to reduce activity durations to meet a deadline PERT (1).pdf, (2).pdf, or (8).pdf Activity durations are random variables, and the probability distribution of the project completion time is desired. Complexity of algorithms (1).pdf, (2).pdf, or (8).pdf Transportation Problem (1).pdf, (2).pdf, or (8).pdf Assignment Problem Linear assignment problem (1).pdf, (2).pdf, or (8).pdf That is, the "classical" assignment problem Airline crew assignment (1).pdf, (2).pdf, or (8).pdf Example of linear assignment model Generalized assignment problem. (1).pdf, (2).pdf, or (8).pdf Each "machine" has given time available and may be assigned more than a single job. Quadratic assignment problem (1).pdf, (2).pdf, or (8).pdf Assign facilities to locations, with the costs including components which depend upon pairs of assignments. Relaxations (1).pdf or (4).pdf Lagrangian dual of ILP is LP relaxation! (1).pdf or (4).pdf If Lagrangian multipliers are used to relax all constraints of an integer LP, the resulting Lagrangian dual is equivalent to the LP relaxation. Lagrangian Relaxation & Duality (1).pdf, (2).pdf, or (8).pdf (see also Generalized assignment problem & Set covering problems) Minimum Cost Network Flows Model (1).pdf, (2).pdf, or (8).pdf (Special case of linear programming) Simplex algorithm (1).pdf, (2).pdf, or (8).pdf (Specialized version of simplex method for networks) Dynamic Programming (1).pdf, (2).pdf, or (8).pdf Deterministic (Transitions between stages are 100% predictable) Prototype DP model (1).pdf, (2).pdf or (8).pdf Powerplant capacity planning (1).pdf, (2).pdf or (8).pdf Redundancy/Reliability (1).pdf, (2).pdf or (8).pdf Political redistricting (1).pdf, (2).pdf or (8).pdf Optimal batchsize (1).pdf, (2).pdf or (8).pdf Nim (game of matches) (1).pdf, (2).pdf or (8).pdf Production planning (1).pdf, (2).pdf or (8).pdf Stochastic (Transitions between stages are governed by probability distributions) DP Casino (1).pdf, (2).pdf or (8).pdf (Maximizing the probability of an event) DP Production (1).pdf, (2).pdf or (8).pdf (Minimizing costs summed over stages) DP Stochastic Replacement (1).pdf, (2).pdf or (8).pdf Machine Replacement (1).pdf, (2).pdf or (8).pdf Integer LP Models ILP Models Intro (1).pdf, (2).pdf, or (8).pdf ILP Models Part I (1).pdf, (2).pdf, or (8).pdf ILP Models Part II (1).pdf, (2).pdf, or (8).pdf Notes on formulation of optimization problems (M.S. Daskin) (6)pdf Knapsack Problem (1).pdf, (2).pdf, or (8).pdf Knapsack BB (1).pdf, (2).pdf, or (8).pdf (Branch-&-Bound algorithm) Knapsack DP (1).pdf, (2).pdf, or (8).pdf (Dynamic programming algorithm) Trim Problem (1).pdf, (2).pdf, or (8).pdf (Knapsack subproblems to generate cutting patterns) Integer Programming Algorithms Balas' Algorithm (1).pdf, (2).pdf or (8).pdf (Implicit enumeration algorithm for 0/1 problems) Benders Decomposition Method (1).pdf, (2).pdf or (8).pdf (Method for mixed-integer LP) See "Capacitated Plant Location" in the Location section below for an example application. Applications other than in integer programming include "Stochastic Linear Programming with Recourse" (1).pdf, (2).pdf or (8).pdf "Stochastic Transportation Problem" (1).pdf, (2).pdf or (8).pdf See "Stochastic LP solved by Benders' Decomposition" (1).pdf, (2).pdf or (8).pdf and "Cross Decomposition" (a hybrid of Benders' decomposition and Lagrangian Relaxation) (1).pdf, (2).pdf or (8).pdf Cutting Plane Methods (1).pdf, (2).pdf or (8).pdf Location Problems (1).pdf, (2).pdf, or (8).pdf Location w/o calculus (1).pdf, (2).pdf, or (8).pdf Webers Problem (location in the plane) (1).pdf, (2).pdf, or (8).pdf Location of multiple facilities in the plane (1).pdf, (2).pdf, or (8).pdf Median problem in a network (1).pdf, (2).pdf, or (8).pdf (Minimizing sum of cost of supplying customers) Center problem in a network (1).pdf, (2).pdf, or (8).pdf (Minimizing maximum distance to customers) Simple (uncapacitated) plant location (1).pdf, (2).pdf , or (8).pdf Capacitated plant location via Benders' method (1).pdf, (2).pdf or (8).pdf Routing Problems "Chinese" Postman Problem (edge-covering) (Routing a vehicle over every street in a network) Part 1: Undirected (1).pdf, (2).pdf, or (8).pdf Part 2: Directed (1).pdf, (2).pdf, or (8).pdf Travelling Salesman Problem (TSP) (node-covering) (Routing a vehicle to visit every node in a network) Introduction to the TSP (1).pdf, (2).pdf , or (8).pdf Applications of the TSP (1).pdf, (2).pdf , or (8).pdf Math Programming Models (1).pdf, (2).pdf , or (8).pdf TSP B&B (branch-&-bound) (1).pdf, (2).pdf , or (8).pdf B&B for Asymetric TSP (1).pdf, (2).pdf , or (8).pdf TSP Heuristics (1).pdf, (2).pdf , or (8).pdf Farthest Insertion Method (1).pdf, (2).pdf , or (8).pdf Nearest Insertion Method (1).pdf, (2).pdf , or (8).pdf Nearest Neighbor Method (1).pdf, (2).pdf , or (8).pdf Simulated Annealing (1).pdf, (2).pdf , or (8).pdf Vertex Penalty Method (1).pdf, (2).pdf , or (8).pdf (An application of Lagrangian relaxation) Exchange Methods (1).pdf, (2).pdf , or (8).pdf (Methods for improving an existing suboptimal solution) Spacefilling curve (1).pdf, (2).pdf , or (8).pdf Example for 30-node problem (1).pdf Set Covering Problem Introduction (1).pdf, (2).pdf , or (8).pdf Lagrangian relaxation (1).pdf, (2).pdf , or (8).pdf Eliminating sets (1).pdf, (2).pdf , or (8).pdf Subgradient method (1).pdf, (2).pdf , or (8).pdf Dual ascent (1).pdf, (2).pdf , or (8).pdf Computational experience (1).pdf, (2).pdf , or (8).pdf Cyclic Staffing Problems (1).pdf, (2).pdf , or (8).pdf Assembly Line Balancing (1).pdf, (2).pdf , or (8).pdf Math programming model (1).pdf, (2).pdf , or (8).pdf Heuristic methods Kilbridge & Wester (1).pdf, (2).pdf , or (8).pdf Ranked positional weight method (1).pdf, (2).pdf , or (8).pdf Reversed ranked positional weight method (1).pdf, (2).pdf , or (8).pdf COMSOAL (1).pdf, (2).pdf , or (8).pdf Genetic algorithm (1).pdf, (2).pdf , or (8).pdf Flowshop Problem (1)pdf, (2).pdf, or (8).pdf Disjoint Path (1)pdf, (2).pdf, or (8).pdf APL Introduction (1)pdf, (2).pdf, or (8).pdf to IP&NF home page. http://asrl.ecn.uiowa.edu/dbricker/ipnf_stacks.html dennis-bricker@uiowa.edu Last modified: 17 September 2003