# 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:**

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