Аннотация

Седова С.В., Беркович Р.М., Лебедев С.С.
Метод узловых векторов целочисленно-го программирования. 4. Алгоритмы локальной оптимизации. / Препринт # WP/2003/159. - М.: ЦЭМИ РАН, 2003. - 67 с. (Рус.)

Для новой вычислительной процедуры частично целочисленного линейного программиро-вания - метода узловых векторов (МУВ) - описываются алгоритмы локальной оптимизации. Они по-зволяют решать задачи большой размерности и их можно охарактеризовать как "статистически оп-тимальные". Проведенный вычислительный эксперимент продемонстрировал существенное преиму-щество реализации МУВ (AlgМУВ+МВГ, S-Alg, M-Alg) по сравнению с широко известным методом ветвей и границ (МВГ) - американской программой "Cplex".
Работа выполнена при финансовой поддержке Российского фонда фундаментальных иссле-дований, проект №02-01-00532

ISBN5-8211-0273-1

Sedova S.V., Berkovich R.V., Lebedev S.S.
Nodal Vectors Method for Integer Program-ming. 4. The algorithms of Local Optimization. / Working paper # WP/2003/159. - Moscow, CEMI Russian Academy of Sciences, 2003. - 67 p. (Rus.)

For a new computational procedure of mixed integer linear programming - the nodal vectors method (MUV) - some algorithms of local optimization are described. These algorithms permit to solve problems of a big dimension and can be named "statistical optimal". The experiment had demonstrated much performance of the MUV realization (AlgМUV+МВB, S-Alg, M-Alg) over the famous branch-and-bound method (MBB) - American system "Cplex". A new algorithm of the ordered enumeration method for the S-knapsack problem is present. The quasioptimal algorithm for solving some investment projecting with indefinite information is described.
The work was supported by Russian Foundation of Basic Research, project №02-01-00532

ISBN5-8211-0273-1