A practical algorithm for computing a subadditive dual function for set partitioning

Diego Klabjan*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Recently, a new algorithm for computing an optimal subadditive dual function to an integer program has been proposed. In this paper we show how to apply the algorithm to the set partitioning problem. We give several enhancements to the algorithm and we report computational experiments. The results show that it is tractable to obtain an optimal subadditive function for small and medium size problems. To the best of our knowledge this is the first work that reports computational experiments on computing an optimal subadditive dual function.

Original languageEnglish (US)
Pages (from-to)347-368
Number of pages22
JournalComputational Optimization and Applications
Volume29
Issue number3
DOIs
StatePublished - Dec 1 2004

Keywords

  • Duality
  • Integer programming

ASJC Scopus subject areas

  • Applied Mathematics
  • Control and Optimization
  • Management Science and Operations Research
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A practical algorithm for computing a subadditive dual function for set partitioning'. Together they form a unique fingerprint.

Cite this