Geodesic
Refinement of Lagrangian bounds in optimization problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 7, pp. 1151-1157 
I. S. Litvinchev. Refinement of Lagrangian bounds in optimization problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 7, pp. 1151-1157. http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_7_a2/
@article{ZVMMF_2007_47_7_a2,
     author = {I. S. Litvinchev},
     title = {Refinement of {Lagrangian} bounds in optimization problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1151--1157},
     year = {2007},
     volume = {47},
     number = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_7_a2/}
}
TY  - JOUR
AU  - I. S. Litvinchev
TI  - Refinement of Lagrangian bounds in optimization problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2007
SP  - 1151
EP  - 1157
VL  - 47
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_7_a2/
LA  - ru
ID  - ZVMMF_2007_47_7_a2
ER  - 
%0 Journal Article
%A I. S. Litvinchev
%T Refinement of Lagrangian bounds in optimization problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2007
%P 1151-1157
%V 47
%N 7
%U http://geodesic.mathdoc.fr/item/ZVMMF_2007_47_7_a2/
%G ru
%F ZVMMF_2007_47_7_a2

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

Lagrangian constraint relaxation and the corresponding bounds for the optimal value of an original optimization problem are examined. Techniques for the refinement of the classical Lagrangian bounds are investigated in the case where the complementary slackness conditions are not fulfilled because either the original formulation is nonconvex or the Lagrange multipliers are nonoptimal. Examples are given of integer and convex problems for which the modified bounds improve the classical Lagrangian bounds.

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

[2] Everett H., “Generalized Lagrange multiplier method for solving problems of optimal allocation of resources”, Operat. Res., 11 (1963), 399–417 | DOI | MR | Zbl

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

[4] Geoffrion A. M., McBride R., “Lagrangian relaxation applied to capacitated facility location problems”, AHE Trans., 10 (1978), 40–47

[5] Guignard M., Kim S., “Lagrangian decomposition: A model yielding stronger Lagrangian bounds”, Math. Programming, 39 (1987), 215–228 | DOI | MR | Zbl

[6] Held M., Karp R., “The travelling salesman problem and minimum spanning trees”, Operat. Res., 18 (1970), 1138–1162 | DOI | MR | Zbl

[7] Beasly J. E., “Lagrangean relaxation”, Modern Heuristic Techn. Combinatorial Problems, Blackwell Scient. Publ., 1993, 243–303

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

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

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

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

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

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

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

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

[16] Freville A., Hanafi S., “The multidimensional 0-1 knapsack problem – bounds and computational aspects”, Ann. Operat. Res., 139 (2005), 195–227 | DOI | MR | Zbl

[17] T. Terlaky (ed.), Interior point methods of mathematical programming, Kluwer, Dordrecht, 1996 | MR