liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Bregman proximal relaxation of large-scale 0-1 problems
Systems Research Institute, Newelska.
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
Royal Institute of Technology, Stockholm.
2000 (English)In: Computational optimization and applications, ISSN 0926-6003, Vol. 15, no 1, 33-44 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2000. Vol. 15, no 1, 33-44 p.
Keyword [en]
convex programming; proximal methods; Bregman functions; B-functions; dual ascent; Lagrangian relaxation; set covering problems
National Category
URN: urn:nbn:se:liu:diva-53573DOI: 10.1023/A:1008770914218OAI: diva2:289371
Available from: 2010-01-25 Created: 2010-01-25 Last updated: 2010-01-25

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Olov Lindberg, Per
By organisation
Optimization The Institute of Technology
In the same journal
Computational optimization and applications

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 302 hits
ReferencesLink to record
Permanent link

Direct link