×

zbMATH — the first resource for mathematics

Studying properties of Lagrangian bounds for many-to-many assignment problems. (English. Russian original) Zbl 1308.49023
J. Comput. Syst. Sci. Int. 48, No. 3, 363-369 (2009); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upravl. 2009, No. 3, 34-40 (2009).
Summary: Classical and modified Lagrangian bounds for the optimal value of optimization problems with a double decomposable structure are studied. For the class of many-to-many assignment problems, this property of constraints is used to design a subgradient algorithm for solving the modified dual problem. Numerical results are presented to compare the quality of classical and modified bounds, as well as the properties of the corresponding Lagrangian solutions.

MSC:
49N05 Linear optimal control problems
49N90 Applications of optimal control and differential games
90C46 Optimality conditions and duality in mathematical programming
Software:
AMPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L. Lasdon, Optimization Theory for Large Systems (Dover, New York, 2002) · Zbl 0991.90001
[2] H. Everett, ”Generalized Lagrange Multiplier Method for Solving Problems of Optimal Allocation of Resources,” Oper. Res. 1, 399–417 (1963). · Zbl 0113.14202
[3] M. Held and R. Karp, ”The Travelling Salesman Problem and Minimum Spanning Trees,” Oper. Res. 18, 1138–1162 (1970). · Zbl 0226.90047
[4] A. Geoffrion, ”Lagrangian Relaxation and Its Uses in Integer Programming,” Mathematical Programming Study 2, 82–114 (1974).
[5] J. Shapiro, ”A Survey of Lagrangian Techniques for Discrete Optimization,” Annals of Discrete Mathematics 5, 113–138 (1974). · Zbl 0411.90054
[6] M. Fisher, ”An Application Oriented Guide to Lagrangian Relaxation,” Interfaces 15 (1985).
[7] M. Guignar, ”Lagrangian Relaxation,” TOP 11, 151–228 (2003). · Zbl 1079.90087
[8] A. Frangioni, ”About Lagrangian Methods in Integer Optimization,” Annals of Operations Research 139, 163–169 (2005). · Zbl 1091.90048
[9] A. Freville and S. Hanafi, ”The Multidimensional 0-1 Knapsack Problem–Bounds and Computational Aspects,” Annals of Operations Research 139, 195–227 (2005). · Zbl 1091.90042
[10] I. Litvinchev, ”Refinement of Lagrangian Bounds in Optimization Problems,” Computational Mathematics and Mathematical Physics 47, 1101–1107 (2007).
[11] I. Litvinchev and S. Rangel, ”Comparing Lagrangian Bounds for a Class of the Generalized Assignment Problems,” Computational Mathematics and Mathematical Physics 48, 739–746 (2008). · Zbl 1164.49322
[12] R. Martin, Large Scale Linear and Integer Programming: A Unified Approach. Boston: Kluwer, 1999.
[13] D. Pentico, ”Assignment Problems: A Golden Anniversary Survey,” Eur. J. Operations Research 176, 774–793 (2007). · Zbl 1103.90060
[14] S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implemen-Tations (Wiley, New York, 1990). · Zbl 0708.68002
[15] R. Fourer, M. Gay, and B. Kernighan, AMPL, A Modeling Language for Mathematical Programming (Scientific Press, Massachusetts, 1993).
[16] L. Lorena and M. Narciso, ”Relaxation Heuristics for Generalized Assignment Problem,” Eur. J. Operations Research 91, 600–610 (1996). · Zbl 0924.90119
[17] M. Narciso and L. Lorena, ”Lagrangean/Surrogate Relaxation for Generalized Assignment Problems,” Eur. J. Operations Research 114, 165–177 (1999). · Zbl 0946.90035
[18] V. Jeet and E. Kutanoglu, ”Lagrangian Relaxation Guided Problem Space Search Heuristics for Generalized Assignment Problems,” Eur. J. Operations Research 182, 1039–1056 (2007). · Zbl 1121.90085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.