Integer Programming and Network Models

H.A. Eiselt; Carl-Louis Sandblom

ISBN 10: 3540671919 / ISBN 13: 9783540671916

Published by Springer, 2000

About this Item

Hardcover, xii + 504 pages, 165 figures, 43 tables, NOT ex-library. Printed in Germany, not an economy edition. Missing front blank endpaper, otherwise interior is VG: clean throughout with unmarked text, free of inscriptions/stamps, firmly bound. Boards show moderate shelfwear, short creases to edges, gently bent and scuffed lower outer corner of front panel; a crease to upper spine edge. Issued without a dust jacket. -- Contents: Introduction: Basic Definitions & Results: - Linear Programming [Fundamental Concepts & Simplex Method; Duality & Postoptimality Analysis; Problems with Special Structures] - Analysis of Algorithms [Algorithms & Time Complexity Functions; Time Complexity Functions Examples; Classes of Problems & Their Relations] - Graph Theory [Basic Definitions & Examples; Representation & Storage of Graphs; Reachability & Connectivity; Graphs with Special Structures] - Dynamic Programming [Basic Ideas; General Algorithm; Various Examples]; Pt1: Integer Programming: 1 Integer Programming Problem & its Properties [Definitions & Basic Concepts; Relaxations of Integer Programming Problems; Polyhedral Combinatorics] 2 Formulations in Logical Variables [Modeling of Discrete Variables & Fixed Charges; Disjunctive Variables; Constraint Selection; Imposing a Sequence on Variables & Constraints; Absolute Values of Functions & Nonconcave Objectives (Problem with Collective & Individual Absolute Values & Nonconcave Objective); Piecewise Linear Functions; Semicontinuous Variables] 3 Applications & Special Structures [Applications (Distribution-Location & Cutting Stock Problem; Examination Timetabling; Forestry Harvesting; Technology Choice; Political Districting; Apportionment Problems; Open Pit Mining; Bin Packing & Assembly Line Planning); Problems with Special Structures (Knapsack Problems; Set Covering, Set Packing & Set Partitioning Problems] 4 Reformulation of Problems [Strong & Weak Formulations; Model Strengthening & Logical Processing (Single & Multiple Constraint Procedures); Aggregation; Disaggregation] 5 Cutting Plane Methods [Dantzig's; Gomory's; For Mixed Integer Programming] 6 Branch & Bound Methods [Basic Principles; Search Strategies (Node & Branch Selection); General Branch & Bound Procedure; Difficult Problems; Integer Programming Duality & Relaxation; Lagrangean Decomposition] 7 Heuristic Algorithms [Neighborhood Search; Simulated Annealing; Tabu Search; Genetic Algorithms; Other Approaches]; Pt2: Network Path Models: 1 Tree Networks [Minimal Spanning Trees; Extensions of Minimal Spanning Tree Problems; Connectivity & Reliability; Steiner Tree Problem] 2 Shortest Path Problems [Problem & its Formulation; Applications of Shortest Paths; Solution Methods (Dijkstra's; Bellman-Ford-Moore & Floyd-Warshall Algorithm); Extensions of the Basic Problem] 3 Traveling Salesman Problems & Extensions [Problem & its Applications; Exact & Heuristic Algorithms; Vehicle Routing Problems] 4 Arc Routing [Euler Graphs & Cycles; Constructing Eulerian Graphs; Rural Postman Problems; Capacitated Arc Routing Problem]; Pt3: Network Flow & Network Design Models: 1 Basic Principles of Network Models [Problem & its Formulation; Transformations of Flow Problems; Duality & Optimality Conditions; Some Fundamental Results] 2 Applications of Network Flow Models [Building Evacuation; Flow Sharing Problems; Worker Allocation Problem; Airline Crew Assignment; Allocation of Representatives to Committees; Computer Program Testing; Distributed Computing; Matrix Balancing & Rounding Problems] 3 Network Flow Algorithms [Maximal Flow Algorithms (Ford & Fulkerson; Karzanov's Preflow Algorithm); Feasible Flow Problems; Cost-Minimal Flow Problems] 4 Multicommodity Network Flows [Model, ist Formulation & Properties; Solution Methods (Price- & Resource Directive Decomposition); Network Design Problems] 5 Networks with Congestion [System- & User-Optimal Network Flows; Solving Flow Assignment Problem; Discrete Route Assignment; Network Design Problems].

Seller Inventory # 005486

Bibliographic Details

• Title: Integer Programming and Network Models
• Publisher: Springer
• Publication Date: 2000
• Language: English
• ISBN 10: 3540671919
• ISBN 13: 9783540671916
• Binding: Hardcover
• Condition: Good

About this title

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.