Constructive dual methods for discrete programming

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

This paper gives a general theory for constructive dual methods in discrete programming. These techniques are concerned with the reduction of the feasibility set in order to obtain a dual problem which is easy to solved and has no duality gap. If a particular dual problem fails to solved the primal problem, then a stronger dual problem is constructed and the analysis continued. The relaxation approximation is made progressively tighter until, in a finite number of iterations, an optimal solution is reached. The theory presented generalises both the 'convergent duality theory' of Shapiro [10] and 'the bound improving sequence algorithm (BISA)' of Barcia [4]. An improved BISA, requiring only the solution of knapsack problems, is presented. For the case of 0-1 LP's computational experience is reported, both for problems presented in the literature as well as for randomly generated ones.

Original languageEnglish
Pages (from-to)107-117
Number of pages11
JournalDiscrete Applied Mathematics
Volume18
Issue number2
DOIs
Publication statusPublished - 1 Jan 1987

Keywords

  • 0-1 LP's
  • Discrete optimization
  • Knapsack problem
  • Lagrangean duality

Fingerprint

Dive into the research topics of 'Constructive dual methods for discrete programming'. Together they form a unique fingerprint.

Cite this