Constructive dual methods for discrete programming

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.