Integer Programming and Network Models

✍ Scribed by Prof. H. A. Eiselt, Prof. C.-L. Sandblom (auth.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2000
• Tongue: English
• Leaves: 500
• Edition: 1
• Category: Library

✦ Synopsis

The purpose of this book is to provide readers with an introduction to the very active field of integer programming and network models. The idea is to cover the main parts of the field without being too detailed or too technical. As a matter of fact, we found it somewhat surprising that most--especially newer---books are strongly algorithmically oriented. In contrast, the main emphasis of this book is on models rather than methods. This focus expresses our view that methods are tools to solve actual problems and not ends in themselves. As such, graduate (and with some omissions, undergraduate) students may find this book helpful in their studies as will practitioners who would like to get acquainted with a field or use this text as a refresher. This premise has resulted in a coverage that omits material that is standard fare in other books, whereas it covers topics that are only infrequently found elsewhere. There are some, yet relatively few, prerequisites for the reader. Most material that is required for the understanding of more than one chapter is presented in one of the four chapters of the introductory part, which reviews the main results in linear programming, the analysis of algorithms, graphs and networks, and dynamic programming, respectively. Readers who are familiar with the issues involved can safely skip that part. The three main parts of the book rely on intuitive reasoning and examples, whenever practical, instead of theorems and proofs.

✦ Table of Contents

Front Matter....Pages I-XII
Front Matter....Pages 1-1
Linear Programming....Pages 3-12
Analysis of Algorithms....Pages 13-33
Graph Theory....Pages 35-64
Dynamic Programming....Pages 65-85
Front Matter....Pages 87-87
The Integer Programming Problem and its Properties....Pages 89-109
Formulations in Logical Variables....Pages 111-128
Applications and Special Structures....Pages 129-160
Reformulation of Problems....Pages 161-185
Cutting Plane Methods....Pages 187-204
Branch and Bound Methods....Pages 205-228
Heuristic Algorithms....Pages 229-258
Front Matter....Pages 259-259
Tree Networks....Pages 261-281
Shortest Path Problems....Pages 283-313
Traveling Salesman Problems and Extensions....Pages 315-341
ARC Routing....Pages 343-357
Front Matter....Pages 359-359
Basic Principles of Network Models....Pages 361-375
Applications of Network Flow Models....Pages 377-397
Network Flow Algorithms....Pages 399-434
Multicommodity Network Flows....Pages 435-455
Networks with Congestion....Pages 457-477
Back Matter....Pages 479-504

✦ Subjects

Operation Research/Decision Theory; Calculus of Variations and Optimal Control; Optimization; Control, Robotics, Mechatronics; Engineering Economics, Organization, Logistics, Marketing