## 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