Bregman Proximal Relaxation of Large-Scale 0–1 Problems

被引：0

作者：

Krzysztof C. Kiwiel

P.O. Lindberg

Andreas Nõu

机构：

[1] Systems Research Institute,

[2] Linköping University,undefined

[3] Royal Institute of Technology,undefined

来源：

Computational Optimization and Applications | 2000年 / 15卷

关键词：

convex programming; proximal methods; Bregman functions; B-functions; dual ascent; Lagrangian relaxation; set covering problems;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We apply a recent extension of the Bregman proximal method for convex programming to LP relaxations of 0–1 problems. We allow inexact subproblem solutions obtained via dual ascent, increasing their accuracy successively to retain global convergence. Our framework is applied to relaxations of large-scale set covering problems that arise in airline crew scheduling. Approximate relaxed solutions are used to construct primal feasible solutions via a randomized heuristic. Encouraging preliminary experience is reported.

引用

页码：33 / 44

页数：11

共 49 条

[1]

Balas E.(1996)A dynamic subgradient-based branch-and-bound procedure for set covering Operations Research 44 875-890

[2]

Carrera M.C.(1980)Set covering algorithms using cutting planes, heuristics and subgradient optimization: A computational study Mathematical Programming Study 12 37-60

[3]

Balas E.(1997)Legendre functions and the method of random Bregman projections Journal of Convex Analysis 4 27-67

[4]

Ho A.(1987)An algorithm for set covering problems European Journal of Operations Research 31 85-93

[5]

Bauschke H.H.(1990)A Lagrangian heuristic for set covering problems Naval Research Logistics Quarterly 37 151-164

[6]

Borwein J.M.(1992)Enhancing an algorithm for set covering problems European Journal of Operations Research 58 293-300

[7]

Beasley J.E.(1981)Disaggregation and resource allocation using convex knapsack problems with bounded variables Management Science 27 431-441

[8]

Beasley J.E.(1997)Enlargement of monotone operators with applications to variational inequalities Set-Valued Analysis 5 159-180

[9]

Beasley J.E.(1992)Proximal minimization algorithm with Journal of Optimization Theory and Applications 73 451-464

[10]

Jörnsten K.(1998)-functions Mathematical Programming 81 215-228

← 1 2 3 4 5 →