Testing of Algorithms for Integer Quasiblock Optimization Problems

The article focuses on the algorithms for solving integer quasiblock optimization problems. For this purpose we analyzed modern decomposition techniques, as well as the advantages of using the local elimination algorithm for large-scale problems. Moreover, we described the special issues in applying parametric optimization and carried out a series of computational experiments for solving large-scale integer linear programming problems by exact, approximate, and heuristic algorithms. The study gives the results obtained for different modifications of the local elimination algorithm. It also describes computational experiments with the local elimination algorithm parallelized by grid technologies. Finally, we provide some examples of the problems that cannot be solved without the paralleling approach

References

[1] Shcherbina O.A. Local algorithms for block-tree problems of discrete programming. USSR Computational Mathematics and Mathematical Physics, 1985, vol. 25, iss. 4, pp. 114–121. DOI: 10.1016/0041-5553(85)90154-5

[2] Lemtyuzhnikova D.V., Sviridenko A.V., Shcherbina O.A. Discrimination algorithm for block-tree diagram in split tasks of discrete optimization. Tavricheskiy vestnik informatiki i matematiki, 2012, no. 1, pp. 44–55 (in Russ.).

[3] Averbakh I.L., Tsurkov V.I. Optimizatsiya v blochnykh zadachakh s tselochislennymi peremennymi [Optimization in block problems with integer variables]. Moscow, Nauka Publ., 1995. 225 p. (in Russ.).

[4] Lubin M., Martin K., Petra C.G., Sandikci B. On parallelizing dual decomposition in stochastic integer programming. Operations Research Letters, 2013, vol. 41, iss. 3, pp. 252–258. DOI: 10.1016/j.orl.2013.02.003

[5] Laesanklang W., Landa-Silva D., Castillo-Salazar J.A. Mixed integer programming with decomposition to solve a workforce scheduling and routing problem. Int. Conf. on Operations Research and Enterprise Systems (ICORES 2015), 2015, pp. 283–293.

[6] Heinz S., Beck J.C. Reconsidering mixed integer programming and MIP-based hybrids for scheduling. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012), 2012, pp. 211–227.

[7] Cire A., Coban E., Hooker J.N. Mixed integer programming vs. logic-based benders decomposition for planning and scheduling. Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2013), 2013, pp. 325–331.

[8] 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, pp. 1101–1115.

[9] Gade D., Kucukyavuz S., Sen S. Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs. Mathematical Programming, 2014, vol. 144, iss. 1-2, pp. 39–64. DOI: 10.1007/s10107-012-0615-y

[10] Ntaimo L. Fenchel decomposition for stochastic mixed-integer programming. Journal of Global Optimization January, 2013, vol. 55, iss. 1, pp. 141–163. DOI: 10.1007/s10898-011-9817-8

[11] 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, pp. 315–333. DOI: 10.1016/j.compchemeng.2013.08.003

[12] Jung C., Pabst D., Ham M., Stehli M., Rothe M. An effective problem decomposition method for scheduling of diffusion processes based on mixed integer linear programming. IEEE Transactions on Semiconductor Manufacturing, 2014, vol. 27, no. 3, pp. 357–363.

[13] Luedtke J. A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Mathematical Programming, 2014, vol. 146, iss. 1-2, pp. 219–244. DOI: 10.1007/s10107-013-0684-6

[14] Guo G., Hackebeil G., Ryan S.M., Watson J.P., Woodruff D.L. Integration of progressive hed-ging and dual decomposition in stochastic integer programs. Operations Research Letters, 2015, vol. 43, iss. 3, pp. 311–316. DOI: 10.1016/j.orl.2015.03.008

[15] 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. 33, pp. 241–246. DOI: 10.1016/B978-0-444-63456-6.50041-7

[16] Mironov A.A., Fedorchuk V.V., Tsurkov V.I. Minimax in transportation models with integral constraints: I. Journal of Computer and Systems Sciences International, 2003, vol. 42, no. 4, pp. 562–574.

[17] Mironov A.A., Fedorchuk V.V., Tsurkov V.I. Minimax in transportation models with integral constraints: II. Journal of Computer and Systems Sciences International, 2005, vol. 44, no. 5, pp. 732–752.

[18] Mironov A.A., Tsurkov V.I. Hereditary minimax matrixes in transportation models. Izvestiya RAN. Teoriya i sistemy upravleniya, 1998, no. 6, pp. 104–121 (in Russ.).

[19] Mironov A.A., Tsurkov V.I. Transport and network problems with the minimax criterion. Computational Mathematics and Mathematical Physics, 1995, vol. 35, no. 1, pp. 15–30.

[20] Sokolov A.A., Tizik A.P., Tsurkov V.I. Iterative method for the transportation problem with additional supply and consumption points and quadratic cost. Journal of Computer and Systems Sciences International, 2013, vol. 52, iss. 4, pp. 588–598. DOI: 10.1134/S106423071304014X

[21] Mironov A.A., Tsurkov V.I. Network models with fixed parameters at the communication nodes. Journal of Computer and Systems Sciences International, 1995, vol. 33, no. 3, pp. 107.

[22] Symphony. Coin-or: website. Available at: https://projects.coin-or.org/SYMPHONY (accessed: 27.03.2017).

[23] Shcherbina O.A. Lokalnye eliminatsionnye algoritmy dlya razrezhennykh zadach diskretnoy optimizatsii. Dis. d-ra fiz. mat. nauk [Local elimination algorithms for sparse problems of discrete optomiztion. Dr. phys.-mat. sci. diss.]. Moscow, 2011. 361 p. (in Russ.).

[24] 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, pp. 229–239.

[25] Local elimination solver. GitHub.com: website. Available at: https://github.com/robionica/les (accessed: 27.03.2017).

[26] Afanasiev A.P., Bychkov I.V., Zaikin O.S., Manzyuk M.O., Posypkin M.A., Semenov A.A. Concept of a multitask grid system with a flexible allocation of idle computational resources of supercomputers. Journal of Computer and Systems Sciences International, 2017, vol. 56, iss. 4, pp. 701–707. DOI: 10.1134/S1064230717040025

[27] Everest: A cloud platform. Available at: http://everest.distcomp.org (accessed: 27.03.2017).

[28] 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, pp. 115–316. DOI: 10.1561/1300000042 Available at: http://www.nowpublishers.com/article/Details/NET-042

[29] 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, 2016, pp. 977–982.

[30] A mathematical programming language. AMPL: website. Available at: https://ampl.com (accessed: 27.03.2017).

[31] Achterberg T. SCIP: Solving constraint integer programs. Mathematical Programming Computation, 2009, vol. 1, iss. 1, pp. 1–41. DOI: 10.1007/s12532-008-0001-1

[32] Voloshinov V.V., Smirnov S.A., Neverov V.S. Integratsiya programmnykh sredstv optimizatsionnogo modelirovaniya v neodnorodnoy vychislitelnoy srede na osnove sistemy AMPLX [Optimization simulation software integration in heterogeneous computing environment based on AMPLX system] (in Russ.). Available at: http://distcomp.ru/~vladimirv/docs/nscf2015-amplx-VoloshinovVV-SmirnovSA-NeverovVS.pdf (accessed: 27.03.2017).

[33] AMPLX. GitLab: website. Available at: https://gitlab.com/ssmir/amplx (accessed: 27.03.2017).