Creative modeling: Variable and constraint duplication in primal–dual decomposition methods

In this paper, we discuss modeling with the specific purpose of solving the models with different decomposition techniques. We first briefly describe the basic primal, dual and primal–dual decomposition techniques, where a master problem is constructed by very specific modeling. The main part of the paper contains a discussion of variables and constraint duplication techniques, used to create a structure which can be used in decomposition methods, i.e. enabling decomposition by modeling. We mainly treat linear mixed integer programming problems with several sets of variables and/or constraints. We propose several ways of incorporating variable and/or constraint duplication techniques in cross decomposition. In some cases, the constraints corresponding to the Lagrange multipliers that are needed 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-uniqueness in an advantageous way. An application to the capacitated facility location problem is described.