𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Lagrangian-based heuristic for large-scale set covering problems

✍ Scribed by Sebastián Ceria; Paolo Nobili; Antonio Sassano

Publisher
Springer-Verlag
Year
1998
Tongue
English
Weight
976 KB
Volume
81
Category
Article
ISSN
0025-5610

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An efficient heuristic for large set cov
An efficient heuristic for large set covering problems
✍ Francis J. Vasko 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 477 KB

## Abstract A heuristic solution procedure for set covering is presented that works well for large, relatively dense problems. In addition, a confidence interval is established about the unknown global optimum. Results are presented for 30 large randomly generated problems.

Simple Lagrangian heuristic for the set
Simple Lagrangian heuristic for the set covering problem
✍ Salim Haddadi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 353 KB

In this paper a simple Lagrangian heuristic is proposed for the set covering problem. It is based on simple and classica1 ideas: Lagrangian duality, greedy heuristic for the set covering problem, subgradient optimization and redundant covers. The main interesting point of the paper lies in the fact

A combined Lagrangian, linear programmin
A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems
✍ A. Atamtürk; G. L. Nemhauser; M. W. P. Savelsbergh 📂 Article 📅 1996 🏛 Springer US 🌐 English ⚖ 685 KB

Given a finite ground set, a set of subsets, and costs on the subsets, the set partitioning problem is to find a minimum cost partition of the ground set. Many combinatorial optimization problems can be formulated as set partitioning problems. We present an approximation algorithm that produces high