A stability criterion for optimal solutions of a minimax problem about a partition into an arbitrary number of subsets under varying cardinality of the initial set

E. E. Ivanko

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 18 (2012) no. 4, pp. 180-194

Résumé

A stability criterion is considered for distributions of tasks between a fixed number of workers that are optimal in the minimax sense. A perturbation of the initial data may include not only a variation in the values of the cost function but also an addition or removal of tasks. The stability of a distribution is understood as the possibility to add a new element (remove or replace an existing element) to one of the subsets of the distribution with the optimality of the distribution preserved. An optimality criterion and a sufficient optimality condition are presented, the properties of optimality domains under constraints on the cost function are studied, and algorithms for constructing optimality domains are considered. The difference between optimality domains obtained by means of the criterion and by means of the sufficient condition is exemplified by a number of experiments.

Détail

Mots-clés : optimal solution, distribution, partition
Keywords: discrete optimization, stability.

Bibliographie

[1] Kantorovich L. V., Gorstko A. B., Optimalnye resheniya v ekonomike, Nauka, M., 1972, 229 pp.

[2] Kalyaev I. A. [i dr.], Rekonfiguriruemye multi-konveiernye vychislitelnye struktury, YuNTs RAN, Rostov-na-Donu, 2008, 320 pp.

[3] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, M.–Izhevsk, 2008, 238 pp.

[4] Chentsov P. A., “O nekotorykh algoritmakh raspredeleniya zadanii mezhdu uchastnikami”, Algoritmy i programmnye sredstva parallelnykh vychislenii, Cb. nauch. tr., 6, In-t matematiki i mekhaniki UrO RAN, 2002, 231–241 | MR | Zbl

[5] Eremin I. I., Astafev N. N., Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya, Nauka, M., 1976, 192 pp. | MR | Zbl

[6] Burkard R. E., Dell'Amico M., Martello S., Assignment problems, Society for Industrial and Applied Mathematics, Philadelphia, 2009, 382 pp. | MR

[7] Kuhn H. W., “The Hungarian method for the assignment problem”, Naval Res. Logist. Quart., 2 (1955), 83–97 | DOI | MR | Zbl

[8] Kellerer H., Pferschy U., Pisinger D., Knapsack problems, Springer Verlag, Berlin, 2004, 546 pp. | MR | Zbl

[9] Papadimitriou C., Yannakakis M., “Optimization, approximation and complexity classes”, J. Comput. System Sci., 43:3 (1991), 425–440 | DOI | MR | Zbl

[10] Korf R. E., “A complete anytime algorithm for number partitioning”, Artificial Intelligence, 106:2 (1998), 181–203 | DOI | MR | Zbl

[11] Ivanko E. E., Chentsov A. G., Chentsov P. A., “Ob odnom podkhode k resheniyu zadachi marshrutizatsii peremeschenii s neskolkimi uchastnikami”, Izv. RAN. Teoriya i sistemy upravleniya, 2010, no. 4, 63–71 | MR

[12] Gordeev E. N., Leontev V. K., “Obschii podkhod k issledovaniyu ustoichivosti reshenii v zadachakh diskretnoi optimizatsii”, Zhurn. vychisl. matematiki i mat. fiziki, 36:1 (1996), 66–72 | MR | Zbl

[13] Emelichev V. A., Podkopaev D. P., “O kolichestvennoi mere ustoichivosti vektornoi zadachi tselochislennogo programmirovaniya”, Zhurn. vychisl. matematiki i mat. fiziki, 38:11 (1996), 1801–1805 | MR | Zbl

[14] Devyaterikova M. V., Kolokolov A. A., “Ob ustoichivosti nekotorykh algoritmov tselochislennogo programmirovaniya”, Diskretnyi analiz i issledovanie operatsii, Materialy konf., Novosibirsk, 2002, 206

[15] Cook W. [et al.], “Sensitivity theorems in integer linear programming”, Math. Programming, 34:3 (1986), 251–264 | DOI | MR | Zbl

[16] Chakravarti N., Wagelmans A. P. M., “Calculation of stability radius for combinatorial optimization problems”, Oper. Res. Letters, 23:1 (1998), 1–7 | DOI | MR | Zbl

[17] Ivanko E. E., “Dostatochnye usloviya ustoichivosti optimalnogo marshruta v zadache kommivoyazhera pri dobavlenii novoi vershiny i pri udalenii suschestvuyuschei”, Vestn. Udmurt. un-ta. Matematika. Mekhanika. Kompyuternye nauki, 2010, no. 1, 48–57

[18] Ivanko E. E., “Ustoichivost optimalnykh marshurtov v zadache kommivoyazhera pri dobavlenii i udalenii vershin”, Materialy ros. konf. “Diskretnaya optimizatsiya i issledovanie operatsii” (DOOR-2010), Izd-vo In-ta matematiki, Novosibirsk, 2010, 105

[19] Ivanko E. E., “Kriterii ustoichivosti optimalnogo marshruta v zadache kommivoyazhera pri dobavlenii vershiny”, Vestn. Udmurt. un-ta. Matematika. Mekhanika. Kompyuternye nauki, 2011, no. 1, 58–66

[20] Ivanko E. E., “Kriterii ustoichivosti optimalnykh reshenii pri roste razmernosti raspredelitelnoi zadachi”, Tez. 14-i konf. “Matematicheskoe programmirovanie i prilozheniya”, Inform. byullyuten assotsiatsii mat. programmirovaniya, 12, UrO RAN, Ekaterinburg, 2011, 178