|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Christofides N. (ed.), Mingozzi A. (ed.), Toth P. (ed.) — Combinatorial Optimization |
|
|
|
| Предметный указатель |
 -Optimality 16
Abelian semi-group 40
Accuracy 9
Additive semi-group 25
Algorithm, efficient 108—111
Algorithm, greedy 109
Alternating subgraph 182
Arbitrage 409—419
Arbitrage on straight rates 410
Arbitrage on swop rates 411
Arbitrage, interest 411
Arbitrage, shortest path models for 417
Arborescence see “Directed spanning tree”
Assignment problem 136—140
Augmenting sequence 110
Augmenting subgraph 182
Baker and Su algorithm for scheduling 374—375
Balanced matrix 159
Benders’ partitioning method 21
Benichou partitioning strategy 9
Bin packing 119
Binary encoding 116
Bitroid 110
Bivalent programs 93—106
Bivalent programs, solving of 101—104
Bottleneck machine 372
Bounded knapsack problem 275—276
Bounding function 74—78
Branch and bound 1—20 28 53 133 243—277
Branching 13—14
Breadth-first branch and bound 243
Canonical form 178
Capital budgeting 239
Cargo-loading problem 239
Change-making problem 277
Chord 162
Chordless cycle 158
Christofides’ heuristic 145—146
Chromatic number 113—116 213
Chvatal’s operation 33
CLIQUE 157 159—162 165 170 177 201 213
Clique, covering problem 151 157
Clique, number 213
Clique, problem 112—116
Codes for mixed integer programming 17
Colouring function 213
Column generation 90 152
Comb inequalities 143
Complementarity theory 21
Complementarity theory, conditions 48
complexity 107—129 285
Complexity, norm 108
Composite inequalities 178
Computational geometry 111
Concave function 73
Constraints, contradictory 8
Constraints, facial 58 59 63
Constraints, tightening 63
Convex function 73
Convex span 59—61
Core knapsack problem 267—270
Crew scheduling 153 389—408
Critical cutset 161—163
Critical edge 161 169
Critical machine 386
Cuts 58
Cutset 161
Cutset, arc 132
Cutting planes 21—72 152 171—174 178—179
Cutting planes, methods for travelling salesman 142—143
Cutting planes, strengthening of 26
Cutting planes, weakening of 26 39 48 50 55 58
Cutting stock problem 239
Dantzig upper bound 239—240
Decomposable set 181
Degeneracy 7
Degree of infeasibility 11
Depth-first branch and bound 243
Directed spanning tree 134—136
Disjunctive arcs 381
Disjunctive graph 381
Disjunctive methods 47—71
Disjunctive normal form 171
Disjunctive programming 171
Disjunctive rule theorem 60
Dominance criteria 261
Dynamic programming 238—239 274—277
Edge covering problem 151 155
Edge matching problem 151 155 156
Efficiency of an algorithm 285
Elementary inequalities 178
Enumeration tree 3—5 10—12
Eulerian subgraph 120
Expected case norm 108
Face 59
Facets 58 167 172—174
Facets of the set packing polytope 158—170
Facets, producing graph 164—168 177
Fathoming 3—5 15—16
Fathoming, premature 16
Finiteness 9
Flows in graphs with gains 41
Foreign exchange 409
Game, two-person 61—62
Generalized lagrangian method 238
Gomory’s fractional row cut 32
Gradient 73
Graph colouring 122 211—235
Graph colouring as a set covering problem 214
Graph colouring, algorithms, colour sequential methods 223—224
Graph colouring, algorithms, dichotomous search methods 221—223
Graph colouring, algorithms, multiple method 228—233
Graph colouring, algorithms, vertex sequential methods 217—221
Graph colouring, formulations 214—216
| Graph colouring, problems; size reduction 216—217
Greedy solution of the knapsack problem 260 262 269
Group knapsack problem 6
Group problem 25 30—31 39 65
Hamiltonian circuit 131 113—116 131—149 397
Heuristics 107—129
Heuristics for travelling salesman 143—146
Heuristics, approximation methods 118
Heuristics, constructive methods 118
Heuristics, decomposition methods 118
Heuristics, deterministic evaluation of 118—122
Heuristics, direct search 15
Heuristics, inductive methods 118
Heuristics, probabilistic evaluation of 122—126
Homomorphisms 40
Hypergraph 158
Implicit enumeration 3 152 238 274—277
Improper face 176
Independence number 160 213
Independent set 213
Integer form 7
Intersection theorem (for binary integer programs) 59
Intersection theorem (for graph colouring) 228—229
Jackson’s rule for scheduling 372
Job-shop scheduling problem (general) 380—383
Knapsack problem 113—116 186 237—279 340
Knapsack problem, algorithms for, (dynamic programming) 250—257
Knapsack problem, algorithms for, (implicit enumeration) 243—250
Knapsack problem, dominance criteria for 261
Knapsack problem, large size 266—274
Knapsack problem, reduction procedure for 257—260
Knapsack problem, unbounded 274—275
Knapsack problem, upper bound for 239—243
Knapsack problem, value independent 276
Knapsack problem, zero-one 238—276
Lagrangean multipliers 131—149
Lateness of jobs on one machine 371—388
LIFO strategy 14
Linear combination of constraints 22—23 35
Linear inequalities systems 74
Linear programming polytope 181—182
Lin’s r-optimal heuristic 145
Loading problem 339—369
Loading problem, computational results for 349 367
Loading problem, dominance for 344 366
Loading problem, dynamic 354—369
Loading problem, feasibility test for 360—363
Loading problem, formulation of dynamic 357—358
Loading problem, formulation of static 344—345
Loading problem, lower bounds for 346 363—366
Loading problem, minimal sets for 344
Loading problem, sensitivity for 350—353
Loading problem, static 343—354
Loading problem, weak maximal sets for 356
Loading problem, weak minimal sets for 356
Location theory 281—314
m-Centre problem 281—314
m-Centre problem on tree networks 283
m-Centre problem, absolute 281
m-Centre problem, classification scheme for 283
m-Centre problem, complexity of 285—287
m-Centre problem, computational results for 304—307
m-Centre problem, extensions of 307—313
m-Centre problem, inverse 283
m-Centre problem, relaxation algorithm for 287—307
Machine scheduling 371—388
Matching problem 110 113—116 140
Matroid 109—110
Maximal r-colourable subset 224
McMahon and Florian algorithm for scheduling 375—378
Median 282
Mid-point property 287
Minimal inequalities 39
Minimax criterion 282
Minisum criterion 282
Mixed integer linear program 1 29
Modular arithmitic 22—25 33 35
Monoid 25
Monoid, finite 31
Monoid, infinite 31
Monoid, mapping of 40
Monoidal cut strengthening 51—52
Multipliers 48 50 66
n-Paths 140—142
Nearest insertion rule for travelling salesman 144
Nearest neighbour rule for travelling salesman 144
Network flow problem 110
Node covering problem 151 155
Node packing problem 151 155 157
Node packing problem, polytope 160
Nonsingular submatrix 159
Normal hypergraph 159
NP-complete problem 112—116 286 374
NP-complete problem, strong 116
NP-hard problem 112—116
Odd anti-hole 160 161 165
Odd hole 160 161 165
Order relations 93—105
Partitioning 8 9
Partitioning problem 113—116
Path-tree 113—116
Penality 6
Penality, down 7
Penality, up 7
Perfect graph 158 159 160
Perfect matching 155
Perfect matrix 159 160
Polynomial bounded algorithm 108
Precedence constraints 371
Priorities 9
Projection method 14
Pseudo costs 9 12—13
Pseudo-polynomial algorithms 116
r-Colourable 213
|
|
|
| Реклама |
|
|
|
|
|
О проекте