Geodesic
Comparison of Lagrangian bounds for one class of generalized assignment problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 5, pp. 779-787 
I. S. Litvinchev; S. Rangel. Comparison of Lagrangian bounds for one class of generalized assignment problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 5, pp. 779-787. http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a3/
@article{ZVMMF_2008_48_5_a3,
     author = {I. S. Litvinchev and S. Rangel},
     title = {Comparison of {Lagrangian} bounds for one class of generalized assignment problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {779--787},
     year = {2008},
     volume = {48},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a3/}
}
TY  - JOUR
AU  - I. S. Litvinchev
AU  - S. Rangel
TI  - Comparison of Lagrangian bounds for one class of generalized assignment problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2008
SP  - 779
EP  - 787
VL  - 48
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a3/
LA  - ru
ID  - ZVMMF_2008_48_5_a3
ER  - 
%0 Journal Article
%A I. S. Litvinchev
%A S. Rangel
%T Comparison of Lagrangian bounds for one class of generalized assignment problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2008
%P 779-787
%V 48
%N 5
%U http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_5_a3/
%G ru
%F ZVMMF_2008_48_5_a3

Voir la notice de l'article provenant de la source Math-Net.Ru

Classical and modified Lagrangian bounds for the optimal value of optimization problems with a double decomposable structure are examined. For the class of generalized assignment problems, this property of constraints is used to design a Benders algorithm for solving the modified dual problem. Numerical results are presented that compare the quality of classical and modified bounds.

[1] Lesdon L. S., Optimizatsiya bolshikh sistem, Nauka, M., 1975 | MR

[2] Geoffrion A. M., “Lagrangian relaxation and its uses in integer programming”, Math. Program. Study, 2 (1974), 82–114 | MR | Zbl

[3] Fisher M. L., “An application oriented guide to Lagrangian relaxation”, Interfaces, 15 (1985), 10–21 | DOI

[4] Frangioni A., “About Lagrangian methods in integer optimization”, Ann. Operat. Res., 139 (2005), 163–169 | DOI | MR

[5] Guignard M., “Lagrangian relaxation”, TOP, 11:2 (2003), 151–228 | DOI | MR | Zbl

[6] Guignard M., Rosenwein M. B., “An application-oriented guide for designing Lagrangian dual ascent algorithms”, European J. Operat. Res., 43 (1989), 197–205 | DOI | MR | Zbl

[7] Lamarechal C., “Lagrangian relaxation”, Comput. Combinatorial Optimizat., Springer, Heidelberg, 2001, 115–160 | MR

[8] Shapiro J. F., “A survey of Lagrangian techniques for discrete optimization”, Ann. Discrete Math., 5 (1974), 113–138 | DOI | MR

[9] Korbut A. A., Finkelshtein Yu. Yu., Diskretnoe programmirovanie, Nauka, M., 1969 | MR | Zbl

[10] Pentico D. W., “Assignment problems: A golden anniversary survey”, European J. Operat. Res., 176 (2007), 774–793 | DOI | MR | Zbl

[11] Martin R. K., Large scale linear and integer programming: A unified approach, Kluwer, Boston, 1999

[12] Litvinchev I. S., “Uluchshenie lagranzhevykh otsenok v zadachakh optimizatsii”, Zh. vychisl. matem. i matem. fiz., 47:7 (2007), 1151–1157 | MR

[13] Shor N. Z., Metody minimizatsii nedifferentsiruemykh funktsii i ikh prilozheniya, Nauk. dumka, Kiev, 1979 | MR | Zbl

[14] Izmailov A. F., Solodov M. V., Chislennye metody optimizatsii, Fizmatlit, M., 2003 | MR

[15] Narciso M. G., Lorena L. A., “Lagrangean/surrogate relaxation for the generalized assignment problem”, European J. Operat. Res., 114 (1999), 165–167 | DOI

[16] Yagiura M., Ibaraki T., Glover F., “A path relinking approach with ejection chains for the generalized assignment problem”, European J. Operat. Res., 169 (2006), 548–569 | DOI | MR | Zbl

[17] Jeet V., Kutanoglu E., “Lagrangian relaxation guided problem space search heuristics for generalized assignment problems”, European J. Operat. Res., 182 (2007), 1039–1056 | DOI | Zbl

[18] Fourer R., Gay M. D., Kernighan B. W., AMPL – a modeling language for mathematical programming, Scient. Press, Denvers, Massachusetts, 1993