A Lagrangian bound for many-to-many assignment problems

被引：15

作者：

Litvinchev, Igor ^{[1
]}

Rangel, Socorro ^{[2
]}

Saucedo, Jania ^{[1
]}

机构：

[1] UANL, Dept Mech & Elect Engn, Monterrey, Mexico

[2] Sao Paulo State Univ UNESP, BR-15054000 Sj Do Rio Preto, Brazil

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2010年 / 19卷 / 03期

基金：

巴西圣保罗研究基金会;

关键词：

Lagrangian bounds; Integer programming; Many-to-many-assignment problem; VOLUME ALGORITHM; RELAXATION; DECOMPOSITION; HEURISTICS;

D O I：

10.1007/s10878-008-9196-3

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：241 / 257

页数：17

共 29 条

[1]

[Anonymous], 1990, Knapsack Problems: Algorithms and ComputerImplementations

[2]

[Anonymous], 1979, Annals of Discrete Math

[3]

[Anonymous], 1999, Large scale linear and integer optimization: a unified approach

[4]

[Anonymous], 1993, AMPL, a modeling language for mathematical programming