Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.68
Sviridenko A.V., Shcherbina O.A.

BLOCK LOCAL ELIMINATION ALGORITHMS FOR SOLVING SPARSE DISCRETE OPTIMIZATION PROBLEMS

Abstract. Block local elimination algorithms for solving sparse discrete optimization problems are considered. The numerical example is provided. The benchmarking is done in order to define real computational capabilities of block elimination algorithms combined with SYMPHONY solver. The analysis of the results shows that for sufficiently large number of blocks and rather small size of separators between the blocks for staircase integer linear programming problem, the local elimination algorithms in combination with a solver for solving subproblems in blocks allow a much faster solution of such problems than the solver itself used to solve the whole problem. The capabilities of the postoptimal analysis (warm starting) are also considered for solving packages of integer linear programming problems for the corresponding blocks.

Keywords: discrete optimization, local elimination algorithms, decomposition, computing experiment.



FULL TEXT

Свириденко Александр Васильевич,
соискатель Таврического национального университета им. В.И. Вернадского, Симферополь,
e-mail: oleks.sviridenko@gmail.com.

Щербина Олег Александрович,
доктор физ.-мат. наук, профессор Таврического национального университета им. В.И. Вернадского, Симферополь,
e-mail: oleg.shcherbina@univie.ac.at.

© 2017 Kibernetika.org. All rights reserved.