A Lagrangian bound for many-to-many assignment problems

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Processo FAPESP: 07/08678-5

Processo FAPESP: 06/03496-3

A simple procedure to tighten the Lagrangian bounds is proposed. The approach is interpreted in two ways. First, it can be seen as a reformulation of the original problem aimed to split the resulting Lagrangian problem into two subproblems. Second, it can be considered as a search for a tighter estimation of the penalty term arising in the Lagrangian problem. The new bounds are illustrated by a small example and studied numerically for a class of the generalized assignment problems.