Artykuł przedstawia uogólniona˛metode˛ dekompozycji Bendersa, która jest obecnie jednym z podstawowych podejs´c´ do rozwia˛zywania duz˙ych zadan´ nieliniowej optymalizacji mieszanej (dyskretno-cia˛głej), takz˙e w przypadku dos´c´ szerokiej klasy zadan´ z niewypukłymi funkcjami celu oraz ogranicze´ n. Oprócz klasycznych twierdze´n o rzutowaniu i reprezentacji, podane b˛edzie jednolite sformułowanie zadania mastera z ci ˛eciami nieliniowymi i liniowymi. Dla tego ostatniego przypadku wskazane be˛da˛ najbardziej efektywne oraz łatwe w implementacji algorytmy obliczeniowe z rodziny płaszczyzn tna˛cych. Abstract. 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. (Generalized Benders method of decomposition of mixed-integer nonlinear optimization problems) Słowa kluczowe: optymalizacja, algorytmy mieszane, dekompozycja, zadania niewypukłe, zadania biliniowe, programowanie całkowitoliczbowe Keywords: optimization, mixed-integer algorithms, decomposition, nonconvex problems, bilinear problems, integer programming Wprowadzenie Na pocza˛tku lat 60-tych XX w. holenderski matematyk Jacques F. Benders rozpatrywał zadania o postaci [2]: (1) max x,v cT x + f(v) przy ograniczeniach (dalej b˛edzie u˙zywany skrót "p.o.") (2) Ax + F(v) ≤ b, b ∈ Rm (3) x ∈ X ⊆ Rn, v ∈ V ⊆ Rq Nazywał je zadaniami programowania z mieszanymi zmiennymi (ang. mixed-variables programming). W zadaniach tych zarówno wskaz[...]

  Kluczowe dla in˙zynierii ruchu zadanie przydziału dost˛epnego pasma do strumieni ruchu mo˙zna sformułowac ´ w kategoriach maksymalizacji uz˙ytecznos´ci, be˛da˛cej rosna˛ca˛ funkcja˛ przepływnos´ci. Nie powinno sie˛ go rozpatrywa ´c w oderwaniu od zagadnienia wyznaczenia optymalnego routingu, gdyz˙ wybór s´ciez˙ek determinuje obcia˛z˙enie poszczególnych ła˛czy, a wraz z ich przepustowos´cia˛definiuje ograniczenia w zadaniu optymalizacji. Problem jednoczesnego wyznaczania optymalnego routingu i alokacji pasma nale˙zy niestety do klasy zada´n NP-trudnych. W niniejszym artykule pokazano, z˙e moz˙liwe jest rozwia˛zanie zadan´ o niewielkiej wymiarowo´sci przy u˙zyciu efektywnych solwerów nieliniowego programowania mieszanego. Zaproponowano te˙z sposób otrzymywania w czasie wielomianowym dopuszczalnych, suboptymalnych rozwia˛zan´ , który jest moz˙liwy do zastosowania w wi˛ekszych zadaniach. Abstract: The key problem of the network traffic engineering is an allocation of the available bandwidth to the traffic flows. It can be formulated in terms of maximizing the total utility, being a concave function of the allocation vector in the presence of constraints defined by the throughput of network links. This problem is coupled through the constraints with a routing problem, because the choice of paths determines the load on links. The problem of joint calculation of the optimal routing and bandwidth allocation is unfortunately NP-hard. The paper presents a mixed integer nonlinear programming formulation of the problem and demonstrates, that for small examples it can be solved in a reasonable time. The proposition of the heuristic method for obtaining suboptimal, feasible solution in polynomial time is then presented. Słowa kluczowe: in˙zynieria ruchu, maksymalizacja u˙zyteczno ´sci, optymalizacja sieciowa, programowanie nieliniowe mieszane Keywords: mixed integer nonlinear programming, network optimization, traffic engineering, utili[...]