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 language | English |
---|---|
Pages (from-to) | 107-117 |
Number of pages | 11 |
Journal | Discrete Applied Mathematics |
Volume | 18 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jan 1987 |
Keywords
- 0-1 LP's
- Discrete optimization
- Knapsack problem
- Lagrangean duality