Books
in black and white
Main menu
Share a book About us Home
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

Combinatorial Optimization - Cristofides N.

Combinatorial Optimization

Author: Cristofides N.
Publishers: Wiley publishing
Year of publication: 2012
Number of pages: 212
Read: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
Download: сombinatorialoptimi2012.pdf

Combinatorial Optimization
Edited by
Nicos Christofides Imperial College of Science and Technology, London
Aristide Mingozzi SOGESTA, Urbino, Italy
Paolo Toth University of Bologna, Italy
and
Claudio Sandi IBM Scientific Centre, Pisa, Italy
A Wiley-Interscience Publication
JOHN WILEY & SONS Chichester New York Brisbane Toronto
Contents
Preface
1 Branch and Bound Methods for Integer Programming . . 1
R. S. Garfinkel
2 The Theory of Cutting-Planes..................................... 21
R. Jeroslow
3 Subgradient Optimization......................................... 73
C. Sandi
4 A Partial Order in the Solution Space of Bivalent Programs 94
P. L. Hammer and S. Nguyen
5 The Complexity of Combinatorial Optimization Algorithms
and the Challenge of Heuristics ......................... 107
F. Maffioli
6 The Travelling Salesman Problem.................................................................................... 131
N. Christofides
7 Set Partitioning A Survey ............................................. 151
E. Balas and M. W. Padberg
8 The Graph-Colouring Problem ........................................... 211
S. M. Korman
9 The 0-1 Knapsack Problem .............................................. 237
S. Martello and P. Toth
10 Complexity and Efficiency in Minimax Network Location . . 281
G. Y. Handler
11 The Vehicle Routing Problem..................................... 315
N. Christofides, A. Mingozzi, and P. Toth
12 Loading Problems ...................................................... 339
N. Christofides, A. Mingozzi, and P. Toth
13 Minimizing Maximum Lateness on One Machine: Algorithms
and Applications................................................. 371
B. Lageweg, J. K. Lenstra, and A. H. G. Rinnooy Kan
viii
Contents
14 The Crew Scheduling Problem: A Travelling Salesman Approach ................................................................. 389
F. Giannessi and B. Nicoletti
15 Graph Theoretic Approaches to Foreign Exchange Operations 409
N. Christofides, R. D. Hewins, and G. R. Salkin
Index.......................................................................... 421
Preface
‘Combinatorial Optimization’ is a term that has emerged in recent years to describe those areas of mathematical programming that are concerned with the solution of optimization problems having a pronounced combinatorial or discrete structure. The title is used as a unifying term covering Integer Programming, Graph Theory, parts of Dynamic Programming, etc., and the areas covered are of increasing importance because of the large number of practical problems that can be formulated and solved as combinatorial optimization problems.
The chapters of this book are derived from lectures given at the Summer School in Combinatorial Optimization, held in Urbino, Italy from 30th May to 11th June, 1977. The chapters are of three types. Chapters 1 to 5 describe methodologies and results of general applicability to combinatorial optimization. Chapters 6 to 10 describe some of the best-known pure combinatorial problems and which often form the central core of larger and more complex practical problems. Chapters 11 to 15 are also concerned with problems with structure but are less ‘pure’ and are closer abstractions of problems as they appear in reality.
Chapter 1 introduces the concepts of branch and bound as the most important technique for the solution of combinatorial optimization problems.
Chapter 2 discusses the general theory of cutting planes and how these can be used to solve integer programming problems.
Chapter 3 describes an iterative technique—known as subgradient optimization—for the optimization of continuous but not everywhere differentiable functions. This technique is extremely useful, when used in conjunction with lagrangian relaxation, for deriving bounds to be used in branch and bound algorithms.
Chapter 4 derives some order relations in the solution space of linear 0-1 programs which can be used to obtain information on problem infeasibility, and the fixing of variables. A resulting algorithm and its computational performance are investigated.
Chapter 5 is an introduction to the field of computational complexity and the role that heuristic methods can play in solving hard combinatorial problems.
Preface
Chapter 6 gives a unified treatment of the travelling salesman problem— probably the most celebrated combinatorial optimization problem—from the viewpoint of lagrangian relaxation.
Chapter 7 is an extensive survey of the set partitioning problem: a mathematical model that is applicable to a very large number of practical situations. Theoretical, algorithmic, and application aspects are discussed.
Chapter 8 surveys the graph colouring problem and its applications to timetabling from the algorithmic point of view.
Chapter 9 deals with the 0-1 knapsack problem—the simplest of the integer programming problems. Algorithms for the solution of this problem are described and tested computationally.
< 1 > 2 3 4 5 6 7 .. 156 >> Next