Decomposition algorithm for linear programming problems without a block structure in the Everest computing environment

V.V. Voloshinov

Abstract


The article describes decomposition method for solving linear programming problems in a general case when it is impossible or difficult to reveal the block structure (of the constraint matrix) used by the classic Danzig-Wulf or Benders decomposition algorithms. Instead, an arbitrary partition of the constraint matrix into a number of submatrices corresponding to groups of rows is used. As in the Danzig-Wolfe algorithm, one searches a maximum of a concave function (on dual variables) by a subgradient method. Iterative routine of solving the original problem includes the phases of solving sets of independent subproblems of a smaller dimension than the original one. Number of submatrices (and subproblems) depends on the dimension of the original problem and the computational power of the distributed environment, where parallel solving of above independent subproblems is done. In concrete term, it is proposed to use the optimization services deployed on the Everest platform, everest.distcomp.org. Programming of the algorithm and data exchange with solvers connected to Everest, may be done by AMPLX system based on algebraic optimization modeling language AMPL, ampl.com. Also, instead of the commercial translator AMPL, it is possible to use the Python interpreter and the freely available Pyomo package, pyomo.org, which provides interaction with AMPL-compatible solvers. The software implementation of the algorithm by Everest platform, allows to hope to get a noticeable acceleration when solving large-scale problems.

Full Text:

PDF (Russian)

References


Ljesdon L.S, Optimizacija bol'shih sistem. M.: Nauka, 1975.

Minu M. Matematicheskoe programmirovanie. Teorija i algoritmy: Per. s fr. A. I. Shterna. M.: Nauka, 1990.

Sukhoroslov O., Volkov S., Afanasiev A. “A Web-Based Platform for Publication and Distributed Execution of Computing Applications”, in Parallel and Distributed Computing (ISPDC), 14th International Symposium, IEEE, 2015, pp. 175-184.

Smirnov S., Voloshinov V., Sukhosroslov O. “Distributed Optimization on the Base of AMPL Modeling Language and Everest Platform” in Procedia Computer Science, vol. 101, 2016, pp. 313–322.

Robert Fourer, David M. Gay, Brian W. Kernighan. AMPL: A mathematical programming language. Thomson/Brooks/Cole, 2003

Hart, William E., Carl D. Laird, Jean-Paul Watson, David L. Woodruff, Gabriel A. Hackebeil, Bethany L. Nicholson, John D. Siirola. Pyomo – Optimization Modeling in Python. 2nd Edition. Vol. 67. Springer, 2017

Afanas'ev A.P., Voloshinov V.V., Sokolov A.V. «Obratnye zadachi modelirovanija na osnove reguljarizacii i raspredelennyh vychislenij v srede Everest». V sbornike: Analitika i upravlenie dannymi v oblastjah s intensivnym ispol'zovaniem dannyh Sbornik nauchnyh trudov XIX Mezhdunarodnoj konferencii DAMDID / RCDL'2017. Pod red. L.A. Kalinichenko, Ja. Manolopulos, N.A. Skvorcova, V.A. Suhomlina. 2017. S. 132-140.

Averbah I.L., Curkov V.I. Optimizacija v blochnyh zadachah s celochislennymi ogranichenijami. M.: Nauka, 1995

Guignard M., Kim S. Lagrangean decomposition: A model yielding stronger lagrangean bounds, in Mathematical Programming, vol. 39, iss. 2, 1987, pp. 215-228

Glover F., Klingman D. Layering strategies for creating exploitable structure in linear and integer programs, in Mathematical Programming, vol. 40, iss. 1-3, 1988, pp. 165-181

Murtaf B. Sovremennoe linejnoe programmirovanie. M.: Mir, 1984.


Refbacks

  • There are currently no refbacks.


Abava   FRUCT 2019

ISSN: 2307-8162