A new Lagrangian relaxation approach to the generalized assignment problem (Q1088908)

We present a new Lagrangian relaxation approach to the generalized assignment problem (GAP). The new approach is based on a reformulation of GAP into an equivalent problem, which is then relaxed by traditional Lagrangian relaxation techniques. The reformulation is created by introducing a set of auxiliary variables and a number of coupling constraints. By relaxing the coupling constraints we get subproblems where both types of constraint structures present in the GAP are active. The lower bound from the Lagrangian dual of this approach is shown to be at least as strong as that from the best of the traditional Lagrangian relaxation approaches. An important feature is also the possibility of generating upper bounds quite easily. The new approach has been tested on 10 problems of size \(m=4\), \(n=25\), i.e. 100 0/1-variables, and the results have been compared with the traditional approaches.