Bregman proximal relaxation of large-scale 0-1 problems
2000 (English)In: Computational optimization and applications, ISSN 0926-6003, Vol. 15, no 1, 33-44 p.Article in journal (Refereed) Published
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.
convex programming; proximal methods; Bregman functions; B-functions; dual ascent; Lagrangian relaxation; set covering problems
IdentifiersURN: urn:nbn:se:liu:diva-53573DOI: 10.1023/A:1008770914218OAI: oai:DiVA.org:liu-53573DiVA: diva2:289371