Integer Programming and Network Models

by Eiselt, Horst A.; Sandblom, Carl-Louis; Spielberg, K. (CON); Richards, R. (CON); Smith, B. T. (CON); Laporte, G. (CON)

• ISBN13: 9783540671916
• ISBN10: 3540671919
• Format: Hardcover
• Copyright: 2000-09-01
• Publisher: Springer Verlag

Summary

The book presents a unified treatment of integer programming and network models with topics ranging from exact and heuristic algorithms to network flows, traveling salesman tours, and traffic assignment problems. While the emphasis of the book is on models and applications, the most important methods and algorithms are described in detail and illustrated by numerical examples. The formulations and the discussion of a large variety of models provides insight into their structures that allows the user to better evaluate the solutions to the problems.

Table of Contents

Introduction: Basic Definitions and Results	1	(2)
Linear Programming	3	(10)
Fundamental Concepts and the Simplex Method	3	(5)
Duality and Postoptimality Analysis	8	(3)
Problems with Special Structures	11	(2)
Analysis of Algorithms	13	(22)
Algorithms and Time Complexity Functions	13	(6)
Examples of Time Complexity Functions	19	(7)
Classes of Problems and Their Relations	26	(9)
Graph Theory	35	(30)
Basic Definitions and Examples	35	(8)
Representation and Storage of Graphs	43	(8)
Reachability and Connectivity	51	(6)
Graphs with Special Structures	57	(8)
Dynamic Programming	65	(22)
Basic Ideas	65	(3)
A General Algorithm	68	(5)
Various Examples	73	(14)
Part I: Integer Programming	87	(172)
The Integer Programming Problem and its Properties	89	(22)
Definitions and Basic Concepts	89	(11)
Relaxations of Integer Programming Problems	100	(3)
Polyhedral Combinatorics	103	(8)
Formulations in Logical Variables	111	(18)
The Modeling of Discrete Variables	111	(2)
The Modeling of Fixed Charges	113	(1)
Disjunctive Variables	114	(1)
Constraint Selection	114	(2)
Imposing a Sequence on Variables	116	(1)
Imposing a Sequence on Constraints	116	(2)
Absolute Values of Functions and Nonconcave Objectives	118	(4)
A Problem with Collective Absolute Values	118	(1)
A Problem with Individual Absolute Values	119	(2)
A Problem with a Nonconcave Objective	121	(1)
Piecewise Linear Functions	122	(6)
Semicontinuous Variables	128	(1)
Applications and Special Structures	129	(32)
Applications	129	(22)
A Distribution-Location Problem	129	(4)
A Cutting Stock Problem	133	(2)
Examination Timetabling	135	(2)
Forestry Harvesting	137	(3)
Technology Choice	140	(2)
Political Districting	142	(2)
Apportionment Problems	144	(2)
Open Pit Mining	146	(3)
Bin Packing and Assembly Line Planning	149	(2)
Problems with Special Structures	151	(10)
Knapsack Problems	151	(4)
Set Covering, Set Packing, and Set Partitioning Problems	155	(6)
Reformulation of Problems	161	(26)
Strong and Weak Formulations	161	(5)
Model Strengthening and Logical Processing	166	(11)
Single Constraint Procedures	167	(4)
Multiple Constraint Procedures	171	(6)
Aggregation	177	(8)
Disaggregation	185	(2)
Cutting Plane Methods	187	(18)
Dantzig's Cutting Plane Method	188	(4)
Gomory's Cutting Plane Methods	192	(7)
Cutting Plane Methods for Mixed Integer Programming	199	(6)
Branch and Bound Methods	205	(24)
Basic Principles	205	(5)
Search Strategies	210	(7)
Node Selection	215	(2)
Branch Selection	217	(1)
A General Branch and Bound Procedure	217	(2)
Difficult Problems	219	(3)
Integer Programming Duality and Relaxation	222	(2)
Lagrangean Decomposition	224	(5)
Heuristic Algorithms	229	(30)
Neighborhood Search	230	(6)
Simulated Annealing	236	(7)
Tabu Search	243	(6)
Genetic Algorithms	249	(7)
Other Approaches	256	(3)
Part II: Network Path Models	259	(100)
Tree Networks	261	(22)
Minimal Spanning Trees	261	(8)
Definitions and Examples	261	(3)
Solution Techniques	264	(5)
Extensions of Minimal Spanning Tree Problems	269	(4)
Node-Constrained Minimal Spanning Trees	269	(1)
Edge-Constrained Minimal Spanning Trees	270	(2)
Alternative Objective Functions	272	(1)
Connectivity and Reliability	273	(3)
The Steiner Tree Problem	276	(7)
Shortest Path Problems	283	(32)
The Problem and its Formulation	283	(1)
Applications of Shortest Paths	284	(7)
Most Reliable Paths	285	(1)
Equipment Replacement	286	(3)
Functional Approximation	289	(1)
Matrix Chain Multiplications	290	(1)
Solution Methods	291	(12)
Dijkstra's Method	292	(3)
The Bellman-Ford-Moore Algorithm	295	(3)
The Floyd-Warshall Algorithm	298	(5)
Extensions of the Basic Problem	303	(12)
The k-Shortest Paths Problem	303	(6)
The Minimum Cost-to-Time Ratio Problem	309	(2)
The Resource-Constrained Shortest Path Problems	311	(4)
Traveling Salesman Problems and Extensions	315	(28)
The Problem and its Applications	315	(7)
Applications	316	(3)
Integer Linear Programming Formulations	319	(3)
Exact Algorithms	322	(7)
Heuristic Algorithms	329	(4)
Vehicle Routing Problems	333	(10)
Arc Routing	343	(16)
Euler Graphs and Cycles	344	(5)
Constructing Eulerian Graphs	349	(3)
Rural Postman Problems	352	(4)
The Capacitated Arc Routing Problem	356	(3)
Part III: Network Flow and Network Design Models	359	(120)
Basic Principles of Network Models	361	(16)
The Problem and its Formulation	361	(3)
Transformations of Flow Problems	364	(3)
Duality and Optimality Conditions	367	(3)
Some Fundamental Results	370	(7)
Applications of Network Flow Models	377	(22)
Building Evacuation	377	(2)
Flow Sharing Problems	379	(3)
A Worker Allocation Problem	382	(2)
Airline Crew Assignment	384	(2)
Allocation of Representatives to Committees	386	(3)
Computer Program Testing	389	(2)
Distributed Computing	391	(2)
Matrix Balancing Problems	393	(2)
Matrix Rounding Problems	395	(4)
Network Flow Algorithms	399	(36)
Maximal Flow Algorithms	399	(13)
The Method of Ford and Fulkerson	399	(7)
Karzanov's Preflow Algorithm	406	(6)
Feasible Flow Problems	412	(4)
Cost-Minimal Flow Problems	416	(19)
An Augmenting Path Construction Algorithm	416	(3)
The Primal Improvement Algorithms of Klein	419	(3)
The Primal-Dual Out-of Kilter Algorithm	422	(7)
The Network Simplex Method	429	(6)
Multicommodity Network Flows	435	(22)
The Model, ist Formulation and Properties	435	(5)
Solution Methods	440	(12)
Price-Directive Decomposition	441	(6)
Resource Directive Decomposition	447	(5)
Network Design Problems	452	(5)
Networks with Congestion	457	(22)
System-Optimal and User-Optimal Network Flows	458	(4)
Solving Flow Assignment Problem	462	(5)
Discrete Route Assignment	467	(3)
Network Design Problems	470	(9)
Continuous Network Design	471	(3)
Discrete Network Design	474	(2)
Combined Routing and Discrete Link-Size Determination	476	(3)
References	479	(22)
Subject Index	501