Problems of discrete optimization with quasiblock matrices

D.V Lemtyuzhnikova, D.V. Kovkov

Abstract


We consider algorithms for solving integer optimization problems with quasi--block structure. Modern decomposition approaches are analyzed. We study Finkelstein decomposition and it variations for discovering quasi--block structure. Efficiency of local elimination algorithm for large-scale problem is analyzed. Specific details of application of parametric optimization are provided. Dependency of order of solving subproblems on the algorithm performance is studied. We provide results of numerical experiments for solving large--scale linear programming problems by exact, approximate, or heuristic algorithms. Also we present experiments for parallelization of local elimination algorithm using grid computing approach. We discuss some problems which cannot be solved efficiently without parallelization techniques.


Full Text:

PDF (Russian)

References


Shcherbina O. A. Local elimination algorithms for sparse discrete optimization problem: thesis of doctor of phys.-mat. sciences: 05.13.17. –M., 2011. – 361 p.

Lemtyuzhnikova D., Sviridenko A., Shcherbina O. On local elimination algorithms for sparse discrete optimization problems // IV International Conference [Problems of Cybernetics and Informatics (PCI)], (Baku, 12–14 September). – 2012. – P. 1–4. – URL: http://neo.lcc.uma.es/workshops/PPSN2012/papers/p2.pdf.

Cire A., Coban E., Hooker J.N. Mixed integer programming vs. logic– based benders decomposition for planning and scheduling // CPAIOR 2013: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. –– 2013. –– P. 325–331.

Chu Y., You F. Integration of production scheduling and dynamic optimization for multi–product cstrs: Generalized benders decomposition coupled with global mixed–integer fractional programming // Computers & Chemical Engineering. –– 2013. –– Vol. 58. –– P. 315–333.

Network–constrained ac unit commitment under uncertainty: A benders’ decomposition approach / Amin Nasri, S. Jalal Kazempour,

Antonio J. Conejo, Mehrdad Ghandhari // IEEE Transactions on Power Systems. –– 2016. –– Vol. 31, no. 1. –– P. 412–422.

On parallelizing dual decomposition in stochastic integer programming / M. Lubin, Kipp Martin, Cosmin G. Petra, Burhaneddin Sandikci // Operations Research Letters. –– 2013. –– Vol. 41, no. 3. –– P. 252–258.

Park J., Karumanchi S., Iagnemma K. Homotopy–based divide–and–conquer strategy for optimal trajectory planning via mixed-integer programming // IEEE Transactions on Robotics. –– 2015. –– Vol. 31, no. 5. –– P. 1101–1115.

Ntaimo L. Fenchel decomposition for stochastic mixed–integer programming // Journal of Global Optimization. –– January, 2013. – Vol. 55, no. 1. –– P. 141–163.

Mitra S., Garcia-Herreros P., Grossmann I. E. A novel cross–decomposition multi–cut scheme for two–stage stochastic programming // Computer Aided Chemical Engineering. –– 2014. – Vol. 32. – P. 241–246.

Mitra Sumit, Garcia-Herreros Pablo, Grossmann Ignacio E. A cross–decomposition scheme with integrated primal–dual multi–cuts for two–stage stochastic programming investment planning problems // Mathematical Programming. – 2016. – Vol. 157, no. 1. – P. 95–119.

A lagrangian decomposition approach for the pump scheduling problem in water networks / Bissan Ghaddar, Joe Naoum-Sawaya, Akihiro Kishimoto et al. // European Journal of Operational Research. – 2015. – Vol. 241, no. 2. – P. 490–501.

Integration of progressive hedging and dual decomposition in stochastic integer programs / G. Guo, Gabriel Hackebeil, Sarah M. Ryan et al. // Operations Research Letters. – 2015. – Vol. 43, no. 3. – P. 311–316.

Zhang Minjiao, Kuc¸¨ ukyavuz Simge. Finitely convergent decomposition algorithms for two-stage stochastic pure integer programs // SIAM J. Optim. – 2014. – Vol. 24, no. 4. – P. 1933–1951.

Lemtyuzhnikova D. V., Sviridenko A. V., Shcherbina O. A. The allocation algorithm block–tree structures in sparse problems of discrete optimization // Taurida Journal of Computer Science Theory and Mathematics. – 2012. – Vol. 1. – P. 44–55.

Zhuravlev U. I. Selected scientific works. – M.: Magistr, 1998. – 420 p.

Parter S. The use of linear graphs in gauss elimination // SIAM Review. – 1961. – Vol. 3. – P. 119–130.

Amestoy P. R., Davis T. A., Duff I. S. An approximate minimum degree ordering algorithm // SIAM Journal on Matrix Analysis and Applications. – 1996. – Vol. 17, no. 4. – P. 886–905.

George J. A. Nested dissection of a regular finite element mesh //SIAM J. Numer. Anal. – 1973. – Vol. 10. – P. 345–367.

Jegou P., Ndiaye S. N., Terrioux C. Computing and exploiting tree–decompositions for (max–)csp // Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming (CP-2005). – 2005. – P. 777–781.

Rose D. J., Tarjan R., Lueker G. Algorithmic aspects of vertex elimination on graphs // SIAM J. on Computing. – 1976. – Vol. 5. – P. 266–283.

Tarjan R. E. Simple linear–time algorithms to test chordality of graphs, test acyclity of hypergraphs, and selectively reduce acyclic hypergraphs // SIAM J. Comput. – 1984. – Vol. 13. – P. 566–579.

Gorry G. A., Shapiro J. F., Wolsey L. A. Relaxation methods for pure and mixed integer programming problems // Management Science. – 1972. – Vol. 18, no. 5. – P. 229–239.

Golubeva Y., Orlov Y., Posypkin M. A tool for simulating parallel branch-and-bound methods // Open Engineering. – 2016. – Vol. 6, no. 1.

Posypkin M., Khrapov N. Branch and bound method on desktop grid systems // Young Researchers in Electrical and Electronic Engineering (EIConRus). – 2017. – P. 526–528. – URL: http://neo.lcc.uma.es/workshops/PPSN2012/papers/p2.pdf.

Kolpakov R. M., Posypkin M. A. Estimating the computational complexity of one variant of parallel realization of the branch-and-bound method for the knapsack problem // Journal of Computer and Systems Sciences International. – 2011. – Vol. 50, no. 5. – P. 756.

Afanasiev. The concept of multi-tasking grid-system with flexible allocation of computing resources of supercomputers //Izvestiya RS. – 2017. – no. 4. – P. 229–239.

Koutsopoulos I., Papaioannou T. G, Hatzi V. Modeling and optimization of the smart grid ecosystem // Foundations and Trends in Networking. – 2016. – Vol. 10, no. 2–3. – P. 115–316. – URL: http://dx.doi.org/10.1561/1300000042.

Salah A., Hart E. A modified grid diversity operator for discrete optimization and its application to wind farm layout optimization problems // Companion Material Proceedings Genetic and Evolutionary Computation conference, GECCO 2016 (Denver, CO, USA, July 20–24) / Ed. by Tobias Friedrich, Frank Neumann, Andrew M. Sutton. – 2016. – P. 977–982.

Voloshinov V. V., Neverov V. S., Smirnov S. A. The integration of software tools optimization modeling in a heterogeneous computing environment based on the system amplx // E-book of abstracts SKF’2015, Program systems Institute named A.K. Aylamazyan RAS (Moskov, 24–27 November). – 2015. – P. 33. – URL: http://2015.nscf.ru/TesisAll/4 Reshenie zadach optimizatsii/10 494 VoloshinovVV.pdf.


Refbacks

  • There are currently no refbacks.


IT-EDU-2017   Servletsuite

ISSN: 2307-8162