Quick eVALUATION OF THE INTERVAL STABILITY OF THE LINEAR ASSIGNMENT problem SOLUTIONS
Abstract
An efficient algorithm for evaluating the interval of solutions stability of opened and closed linear assignment problems based on a review of the results of optimization iterations is proposed. Economical one-step transition to the nearest vertex of the polytope of problem one for all the edges of the optimal perfect matching is almost an order of magnitude reduces the computational complexity of evaluating the stability of the current optimal solution.
About the Authors
M. P. Revotjuk
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
M. K. Qaraleh
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
P. M. Batura
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
References
1. David W. Pentico. // European Journal of Operational Research. 2007. № 176 (2). P. 774-793.
2. Bijsterbosch J., Volgenant A. // Annals of Operations Research. 2010. № 181 (1). P. 443-462.
3. Lantao Liu, Dylan A. Shell. // The International Journal of Robotics Research. 2011. № 30 (7). P. 936-953.
4. Ревотюк М.П., Батура П.М., Полоневич А.М. // Докл. БГУИР. 2011. № 1 (55). C. 55-62.
Review
For citations:
Revotjuk M.P., Qaraleh M.K., Batura P.M. Quick eVALUATION OF THE INTERVAL STABILITY OF THE LINEAR ASSIGNMENT problem SOLUTIONS. Doklady BGUIR. 2013;(5):30-36. (In Russ.)
Views: 2302
Email this article 