Uogólniona metoda Bendersa dekompozycji mieszanych, nieliniowych zadań optymalizacji

• Autorzy: Karbowski A.

Warianty tytułu

EN

Generalized Benders method of decomposition of mixed-integer nonlinear optimization problems

• Języki publikacji: PL

Abstrakty

PL

Artykuł przedstawia uogólnioną metodę dekompozycji Bendersa, która jest obecnie jednym z podstawowych podejść do rozwiązywania dużych zadań nieliniowej optymalizacji mieszanej (dyskretno-ciągłej), także w przypadku dość szerokiej klasy zadań z niewypukłymi funkcjami celu oraz ograniczeń. Oprócz klasycznych twierdzeń o rzutowaniu i reprezentacji, podane będzie jednolite sformułowanie zadania mastera z cięciami nieliniowymi i liniowymi. Dla tego ostatniego przypadku wskazane będą najbardziej efektywne oraz łatwe w implementacji algorytmy obliczeniowe z rodziny płaszczyzn tnących.

The paper presents the Generalized Benders Decomposition method, which is now one of the basic approaches to solve big mixed-integer nonlinear optimization problems, also in the case of quite a broad class of problems with nonconvex objectives and constraints functions. Apart from the classical projection and representation theorems, a unified formulation of the master problem with nonlinear and linear cuts will be given. For the latter case the most effective and, at the same time, easy to implement computational algorithms from the cutting plane family will be pointed out.

Słowa kluczowe

PL

optymalizacja; algorytm; dekompozycja; programowanie całkowitoliczbowe

EN

optimization; algorithm; decomposition; integer programming

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2015
• Tom: R. 91, nr 9
• Strony: 226--234
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Karbowski A.

• Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, Instytut Automatyki i Informatyki Stosowanej, ul. Nowowiejska 15/19, 00–665 Warszawa
• NASK (Naukowa i Akademicka Sieć Komputerowa), ul. Wąwozowa 18, 02-796 Warszawa

Bibliografia

• [1] Adams W. P., Sherali H. D.: Mixed-integer bilinear programming problems, Mathematical Programming, 59(3), str. 279– 305, 1993.
• [2] Benders J. F.: Partitioning Procedures for Solving Mixed-Variables Programming Problems, Numerische Mathematik, 4(1), str. 238–252, 1962.
• [3] Bertsekas D.P.: Nonlinear Programming, 2nd Edition, Athena Scientific, 1999.
• [4] Elzinga J., Moore T. G.: A central cutting plane algorithm for the convex programming problem, Mathematical Programming, 8(1), str. 134–145, 1975.
• [5] Cai X., McKinney D.C., Lasdon L.S., Watkins Jr. D.W.: Solving Large Nonconvex Water Resources Management Models Using Generalized Benders Decomposition, Operations Research, 49(2), str. 235–245, 2001.
• [6] Chung K.H., Kim B.H., Hur D.: Distributed implementation of generation scheduling algorithm on interconnected power systems, Energy Conversion and Management, 52(12), str. 3457–3464, 2011.
• [7] Elhedhli S., Goffin J-L., Vial J.-P.: Nondifferentiable optimization: Cutting plane methods, Encyclopedia of Optimization, 2nd Edition (C.A. Floudas and P.M. Pardalos, Eds.), str. 2590–2595, Springer, 2009.
• [8] Floudas C.A.: Nonlinear and Mixed-Integer Optimization, Oxford University Press, 1995.
• [9] Floudas C.A.: Generalized Benders Decomposition GBD, Encyclopedia of Optimization, 2nd Edition (C.A. Floudas and P.M. Pardalos, Eds.), str. 1162–1175, Springer, 2009.
• [10] Geoffrion A. M.: Generalized Benders Decomposition: Journal of Optimization Theory and Applications, 10(4), str. 237–260, 1972.
• [11] Geoffrion A. M., Graves G.W.: Multicommodity Distribution System Design by Benders Decomposition, Management Science, 20(5), str. 822–844, 1974.
• [12] Goffin J-L., Vial J.-P.: Convex nondifferentiable optimization: A survey focused on the analytic center cutting plane method, Optimization Methods and Software, 17(5), str. 805–867, 2002.
• [13] Grothey A., Leyffer S., McKinnon K. I. M.: A Note on Feasibility in Benders Decomposition, Numerical Analysis Report NA/188, Dundee University, 1999.
• [14] Haouari M., Mrad M., Sherali H.D.: Optimum synthesis of discrete capacitated networks with multi-terminal commodity flow requirements, Optimization Letters, 1(4), str. 341–354, 2007.
• [15] Kelley J. E.: The Cutting-Plane Method for Solving Convex Programs, Journal of the Soc. Indust. Appl. Math., 8(4), str. 703–712, 1960.
• [16] Kiwiel K.C.: Methods of Descent for Nondifferentiable Optimization, Springer, 1985.
• [17] Lee J., Leyffer S.: Mixed Integer Nonlinear Programming, Springer, 2012.
• [18] Lemaréchal C.: An extension of Davidon methods to nondifferentiable problems, Mathematical Programming Study 3 (M.L Balinski and P. Wolfe, Eds.), str. 95–109, North-Holland, 1975.
• [19] Li D., Sun X.: Nonlinear Integer Programming, Springer, 2006.
• [20] Li X.: Parallel nonconvex generalized Benders decomposition for natural gas production network planning under uncertainty, Computers and Chemical Engineering, 55(8), str. 97–108, 2013.
• [21] Nemirovski A., Yudin D.: Problem Complexity and Method Efficiency in Optimization, J.Wiley & Sons, 1983.
• [22] Osman H., Demirli K.: A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection, Int. J. Production Economics, 124(1), str. 97–105, 2010.
• [23] Ruszczy´ nski A.: Nonlinear Optimization, Princeton University Press, 2006.
• [24] Shor N.Z.: Minimization methods for non-differentiable functions, Springer, Berlin, 1985.
• [25] Wolfe P: A method of conjugate subgradients for minimizing nondifferentiable functions, Mathematical Programming Study 3 (M.L Balinski and P. Wolfe, Eds.), str. 145–173, North-Holland, 1975.