Creative modeling: Variable and constraint duplicationin primal - dual decomposition methods

In this paper, we discuss modeling with the specific purpose of solving the models withdifferent decomposition techniques. We first briefly describe the basic primal, dual andprimal - dual decomposition techniques, where a master problem is constructed by veryspecific modeling. The main part of the paper contains a discussion of variables and constraintduplication techniques, used to create a structure which can be used in decompositionmethods, i.e. enabling decomposition by modeling. We mainly treat linear mixed integerprogramming problems with several sets of variables andyor constraints. We propose severalways of incorporating variable andyor constraint duplication techniques in cross decomposition.In some cases, the constraints corresponding to the Lagrange multipliers that areneeded as input to the Lagrangian relaxation are not present in the primal subproblem.Despite this, we show how to determine these multipliers optimally. In some combinations,the input to a subproblem is not unique, and we discuss how to handle this non-uniquenessin an advantageous way. An application to the capacitated facility location problem isdescribed. Copyright Kluwer Academic Publishers 1998