A new subadditive approach to integer programming

Diego Klabjan*

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

8 Scopus citations

Abstract

The linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory was developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We report computational results for set partitioning instances. To the best of our knowledge these are the first computational experiments on computing the optimal subadditive dual function.

Original languageEnglish (US)
Pages (from-to)384-400
Number of pages17
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2337 LNCS
StatePublished - Dec 1 2002
Event9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002 - Cambridge, MA, United States
Duration: May 27 2002May 29 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A new subadditive approach to integer programming'. Together they form a unique fingerprint.

Cite this