Dual bounding procedures lead to convergent Branch-and-Bound algorithms

被引：0
作者：
Dür M. [1 ]
机构：
[1] Department of Statistics, Vienna University of Economics and Business Administration, 1090 Vienna
来源：
Mathematical Programming | 2001年 / 91卷 / 1期
关键词：
Convergence of Branch-and-Bound algorithm; Nonconvex duality;
D O I：
10.1007/s101070100236
中图分类号：
学科分类号：
摘要：
Branch-and-Bound methods with dual bounding procedures have recently been used to solve several continuous global optimization problems. We improve results on their convergence theory and give a condition that enables us to detect infeasible partition sets from the dual optimal value.
引用
收藏
页码：117 / 125
页数：8
相关论文
共 12 条
[1]  
Aubin J., Ekeland I., Estimates of the Duality Gap in Nonconvex Optimization, Math. Oper. Res., 1, pp. 225-245, (1976)
[2]  
Ben-Tal A., Eiger G., Gershovitz V., Global Minimization by Reducing the Duality Gap, Math. Program., 63, pp. 193-212, (1994)
[3]  
Dur M., Horst R., Lagrange-Duality and Partitioning Techniques in Nonconvex Global Optimization, J. Optim. Theory Appl., 95, pp. 347-369, (1997)
[4]  
Dur M., Horst R., Thoai N.V., Solving Sum-of-Ratios Fractional Programs Using Efficient Points, Optimization, 1, 8, pp. 1-20, (2000)
[5]  
Geoffrion A.M., Duality in Nonlinear Programming: A simplified Applications-Oriented Development, SIAM Rev., 13, pp. 1-37, (1971)
[6]  
Held M., Karp R.M., The traveling salesman problem and minimum spanning trees, Oper. Res., 18, pp. 1138-1162, (1970)
[7]  
Horst R., A Note on the Duality Gap in Nonconvex Optimization and a Very Simple Procedure for Bid Evaluation Type Problems, European J. Oper. Res., 5, pp. 205-209, (1980)
[8]  
Horst R., Tuy H., Global Optimization: Deterministic Approaches, (1996)
[9]  
Nemhauser G., Wolsey L.A., Integer and Combinatorial Optimization, (1988)
[10]  
Pappalardo M., On the Duality Gap in Nonconvex Optimization, Math. Oper. Res., 11, pp. 30-35, (1986)
12