Advances in Optimization and Approximation

✍ Scribed by Ding-Zhu Du, Jie Sun (eds.)

• Publisher: Springer US;Springer;Kluwer
• Year: 1994
• Tongue: English
• Leaves: 402
• Series: Nonconvex Optimization and Its Applications 1
• Edition: Softcover reprint of the original 1st ed. 1994
• Category: Library

✦ Synopsis

1. The Algorithm ...59 3. Convergence Analysis ..., ...60 4. Complexity Analysis ...63 5. Conclusions ...67 References ...67 A Simple Proof for a Result of Ollerenshaw on Steiner Trees ...68 Xiufeng Du, Ding-Zhu Du, Biao Gao, and Lixue Qii 1. Introduction ...68 2. In the Euclidean Plane ...69 3. In the Rectilinear Plane ...70 4. Discussion ...-...71 References ...71 Optimization Algorithms for the Satisfiability (SAT) Problem ...72 Jun Gu 1. Introduction ...72 2. A Classification of SAT Algorithms ...7:3 3. Preliminaries ...IV 4. Complete Algorithms and Incomplete Algorithms ...81 5. Optimization: An Iterative Refinement Process ...86 6. Local Search Algorithms for SAT ...89 7. Global Optimization Algorithms for SAT Problem ...106 8. Applications ...137 9. Future Work ...140 10. Conclusions ...141 References ...143 Ergodic Convergence in Proximal Point Algorithms with Bregman Functions ...155 Osman Guier 1. Introduction ...: ...155 2. Convergence for Function Minimization ...158 3. Convergence for Arbitrary Maximal Monotone Operators ...161 References ...163 Adding and Deleting Constraints in the Logarithmic Barrier Method for LP ...166 D. den Hertog, C. Roos, and T. Terlaky 1. Introduction ...16(5 2. The Logarithmic Darrier Method ...lG8 CONTENTS IX 3. The Effects of Shifting, Adding and Deleting Constraints ...171 4. The Build-Up and Down Algorithm ...177 ...5. Complexity Analysis ...180 References ...184 A Projection Method for Solving Infinite Systems of Linear Inequalities ...186 Hui Hu 1. Introduction ...186 2. The Projection Method ...186 3. Convergence Rate ...189 4. Infinite Systems of Convex Inequalities ...191 5. Application ...193 References

✦ Table of Contents

Front Matter....Pages i-xiii
Scheduling Multiprocessor Flow Shops....Pages 1-8
The K -Walk Polyhedron....Pages 9-29
Two Geometric Optimization Problems....Pages 30-57
A Scaled Gradient Projection Algorithm for Linear Complementarity Problems....Pages 58-67
A Simple Proof for a Result of Ollerenshaw on Steiner Trees....Pages 68-71
Optimization Algorithms for the Satisfiability (SAT) Problem....Pages 72-154
Ergodic Convergence in Proximal Point Algorithms with Bregman Functions....Pages 155-165
Adding and Deleting Constraints in the Logarithmic Barrier Method for LP....Pages 166-185
A Projection Method for Solving Infinite Systems of Linear Inequalities....Pages 186-194
Optimization Problems in Molecular Biology....Pages 195-216
A Dual Affine Scaling Based Algorithm for Solving Linear Semi-Infinite Programming Problems....Pages 217-234
A Genuine Quadratically Convergent Polynomial Interior Point Algorithm for Linear Programming....Pages 235-246
A Modified Barrier Function Method for Linear Programming....Pages 247-255
A New Facet Class and a Polyhedral Method for the Three-Index Assignment Problem....Pages 256-274
A Finite Simplex-Active-Set Method for Monotropic Piecewise Quadratic Programming....Pages 275-292
A New Approach in the Optimization of Exponential Queues....Pages 293-312
The Euclidean Facilities Location Problem....Pages 313-331
Optimal Design of Large-Scale Opencut Coal Mine System....Pages 332-346
On the Strictly Complementary Slackness Relation in Linear Programming....Pages 347-361
Analytical Properties of the Central Trajectory in Interior Point Methods....Pages 362-375
The Approximation of Fixed Points of Robust Mappings....Pages 376-389

✦ Subjects

Computational complexity;Discrete Mathematics in Computer Science;Information theory;Mathematical optimization;Mathematics;Operations Research/Decision Theory;Optimization;Theory of Computation