Potential function methods for approximately solving linear programming problems : theory and practice / Daniel Bienstock.

Format:

Book

Author/Creator:

Bienstock, Daniel.

Contributor:

Anne and Joseph Trachtman Memorial Book Fund.

Series:

International series in operations research & management science

Language:

English

Subjects (All):

Linear programming.

Algorithms.

Physical Description:

xix, 110 pages : illustrations ; 25 cm.

Place of Publication:

Boston : Kluwer Academic Publishers, [2002]

Contents:

1 Early Algorithms 1

1 The Flow Deviation Method 3

1.1 Convergence Analysis 5

1.2 Analysis of the Flow Deviation method 8

1.3 Historical Perspective 11

2 The Shahrokhi and Matula Algorithm 13

2.1 The algorithm proper 19

2.2 Cut metrics and minimum congestion 22

2.2.1 Cut metrics and capacitated network design 23

2. The Exponential Potential Function - Key Ideas 27

0.2.2 Handling more general problems 27

0.2.3 Handling large width 28

0.2.4 Leveraging block-angular structure 30

1 A basic algorithm for min-max LPs 30

1.1 The first stage 31

1.2 The second stage 32

1.3 Computing [lambda]* to absolute tolerance 33

2 Round-robin and randomized schemes for block-angular problems 39

2.1 Basic deterministic approach 41

2.2 Randomized approaches 43

2.3 What is best 44

3 Optimization and more general feasibility systems 44

4 Width, revisited 47

5 Alternative potential functions 48

6 A philosophical point: why these algorithms are useful 48

3. Recent Developments 51

1 Oblivious rounding 51

1.1 Concurrent flows 54

1.1.1 The oracle 55

1.1.2 The deterministic algorithm 57

1.1.3 Handling general capacities 59

1.1.4 Comparison with the exponential potential function method 62

2 Lower bounds for Frank-Wolfe methods 62

2.1 Lower bounds under the oracle model 64

3 The algorithms of Garg-Konemann and Fleischer 66

3.1 The Luby-Nisan algorithm and related work 67

4 Lagrangian Relaxation, Non-Differentiable Optimization and Penalty Methods 69

4.0.1 Bundle and cutting-plane methods 70

4.0.2 Penalty methods 70

4.0.3 The Volume algorithm 71

4. Computational Experiments 73

0.1 Remarks on previous work 74

0.2 Outline of a generic implementation 76

1 Basic Issues 78

1.1 Choosing a block 78

1.2 Choosing [tau] 79

1.3 Choosing [mu] 80

1.4 Choosing [alpha] 81

2 Improving Lagrangian Relaxations 83

3 Restricted Linear Programs 86

4 Tightening formulations 88

5 Computational tests 89

5.1 Network Design Models 90

5.2 Minimum-cost multicommodity flow problems 91

5.3 Maximum concurrent flow problems 93

5.4 More sophisticated network design models 94

5.5 Empirical trade-off between time and accuracy 97

5.6 Hitting the sweet spot 98

6 Future work 101

Appendix Frequently Asked Questions 103.

Notes:

Includes bibliographical references (pages [107]-110) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Anne and Joseph Trachtman Memorial Book Fund.

ISBN:

1402071736

OCLC:

50028532