Lagrangian heuristic for a class of the generalized assignment problems

被引：10

作者：

Litvinchev, Igor ^{[1
]}

Mata, Miguel ^{[2
]}

Rangel, Socorro ^{[3
]}

Saucedo, Jania ^{[2
]}

机构：

[1] Russian Acad Sci, Dorodnicyn Comp Ctr, Moscow, Russia

[2] UANL Nuevo Leon State Univ, Fac Mech & Elect Engn, Nuevo Leon, Mexico

[3] UNESP Sao Paulo State Univ, Dept Comp Sci & Stat, Sao Paulo, Brazil

来源：

COMPUTERS & MATHEMATICS WITH APPLICATIONS | 2010年 / 60卷 / 04期

关键词：

Lagrangian heuristic; Integer programming; Many-to-many assignment problem; RELAXATION;

D O I：

10.1016/j.camwa.2010.03.070

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A Lagrangian based heuristic is proposed for many-to-many assignment problems taking into account capacity limits for task and agents. A modified Lagrangian bound studied earlier by the authors is presented and a greedy heuristic is then applied to get a feasible Lagrangian-based solution. The latter is also used to speed up the subgradient scheme to solve the modified Lagrangian dual problem. A numerical study is presented to demonstrate the efficiency of the proposed approach. (C) 2010 Elsevier Ltd. All rights reserved.

引用

页码：1115 / 1123

页数：9

共 50 条

[41] Generalized Nonlinear Lagrangian Formulation for Bounded Integer Programming [J].

Yifan Xu ;

Chunli Liu ;

Duan Li .

Journal of Global Optimization, 2005, 33 :257-272

[42] Generalized nonlinear Lagrangian formulation for bounded integer programming [J].

Xu, YF ;

Liu, CL ;

Li, D .

JOURNAL OF GLOBAL OPTIMIZATION, 2005, 33 (02) :257-272

[43] Differential Evolution Algorithms for the Generalized Assignment Problem [J].

Tasgetiren, M. Fatih ;

Suganthan, P. N. ;

Chua, Tay Jin ;

Al-Hajri, Abdullah .

2009 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-5, 2009, :2606-+

[44] Lagrangian Bounds and a Heuristic for the Two-Stage Capacitated Facility Location Problem [J].

Litvinchev, Igor ;

Ozuna, Edith L. .

INTERNATIONAL JOURNAL OF ENERGY OPTIMIZATION AND ENGINEERING, 2012, 1 (01) :59-71

[45] A LAGRANGIAN HEURISTIC FOR THE CAPACITATED PLANT LOCATION PROBLEM WITH SINGLE-SOURCE CONSTRAINTS [J].

SRIDHARAN, R .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 66 (03) :305-312

[46] Modeling and Lagrangian Relaxation Based Heuristic for Scheduling Oil Wells in Oilfield Production [J].

Lang Jin ;

Tang Lixin .

2013 32ND CHINESE CONTROL CONFERENCE (CCC), 2013, :2554-2559

[47] Combining heuristic and exact approaches for solving the routing and spectrum assignment problem [J].

Dao Thanh Hai ;

Morvan, Michel ;

Gravey, Philippe .

IET OPTOELECTRONICS, 2018, 12 (02) :65-72

[48] Assignment problems: A golden anniversary survey [J].

Pentico, David W. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 176 (02) :774-793

[49] Dynamic Sparsification for Quadratic Assignment Problems [J].

John, Maximilian ;

Karrenbauer, Andreas .

MATHEMATICAL OPTIMIZATION THEORY AND OPERATIONS RESEARCH, 2019, 11548 :232-246

[50] Social classroom seating assignment problems [J].

Hill, Alessandro ;

Hom, David ;

Peuker, Steffen ;

Mourtos, Ioannis .

NETWORKS, 2024, :166-188

← 1 2 3 4 5 →