Bregman proximal relaxation of large-scale 0-1 problems

被引：7

作者：

Kiwiel, KC

Lindberg, PO

Nou, A

机构：

[1] Polish Acad Sci, Syst Res Inst, PL-01447 Warsaw, Poland

[2] Linkoping Univ, SE-58183 Linkoping, Sweden

[3] Royal Inst Technol, SE-10044 Stockholm, Sweden

来源：

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS | 2000年 / 15卷 / 01期

关键词：

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

D O I：

10.1023/A:1008770914218

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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

页数：12

共 36 条

[1]

BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886

[2] A dynamic subgradient-based branch-and-bound procedure for set covering [J].