Search

The main purpose of the work was examining various methods of decomposition of a network optimization problem of simultaneous routing and bandwidth allocation based on Lagrangian relaxation. The problem studied is an NP-hard mixed-integer nonlinear optimization problem. Multiple formulations of the optimization problem are proposed for the problem decomposition. The decomposition methods used several problem formulations and different choices of the dualized constraints. A simple gradient coordination algorithm, cutting-plane coordination algorithm, and their more sophisticated variants were used to solve dual problems. The performance of the proposed decomposition methods was compared to the commercial solver CPLEX and a heuristic algorithm. [ABSTRACT FROM AUTHOR]

A cross-layer network optimization problem is considered. It involves network and transport layers, treating both routing and flows as decision variables. Due to the nonconvexity of the capacity constraints, when using Lagrangian relaxation method a duality gap causes numerical instability. It is shown that the rescue preserving separability of the problem may be the application of the augmented Lagrangian method, together with Cohen's Auxiliary Problem Principle. [ABSTRACT FROM AUTHOR]

Abstract: The purpose of the paper is to evaluate the potential of the Cell Broadband Engine Architecture for solving closed-loop optimal control problems. The main part contains the description and pseudo language implementation of two dynamic programming algorithms to solve stochastic discounted and minimax optimal control problems of a Polish Upper Vistula river multi-reservoir water system over the infinite time horizon. OpenMP parallelizing directives were applied to allow for high programmer efficiency as opposed to low level, assembler like Cell programming. In an extensive number of performance tests conducted on different systems this approach proved to be very efficient (reaching 20× speed-up) in comparison with general purpose processors validating the CBEA as an attractive platform for solving optimal control problems. [Copyright &y& Elsevier]

The paper presents the Generalized Benders Decomposition (GBD) method, which is now one of the basic approaches to solve big mixed-integer nonlinear optimization problems. It concentrates on the basic formulation with convex 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 will be pointed out. [ABSTRACT FROM AUTHOR]