POSITIVE FILTERED P_N METHOD FOR LINEAR TRANSPORT EQUATIONS AND THE ASSOCIATED OPTIMIZATION ALGORITHM

We propose a positive, accurate moment closure for linear kinetic transport equations based on a filtered spherical harmonic (FP_N) expansion in the angular variable. The FP_N moment equations are accurate approximations to linear kinetic equations, but they are known to suffer from the occurrence of unphysical, negative particle concentrations. The new positive filtered P_N (FP_N+) closure is developed to address this issue. The FP_N+ closure approximates the kinetic distribution by a spherical harmonic expansion that is non-negative on a finite, predetermined set of quadrature points. With an appropriate numerical PDE solver, the FP_N+ closure generates particle concentrations that are guaranteed to be non-negative. Under an additional, mild regularity assumption, we prove that as the moment order tends to infinity, the FP_N+ approximation converges, in the L2 sense, at the same rate as the FP_N approximation; numerical tests suggest that this assumption may not be necessary. By numerical experiments on the challenging line source benchmark problem, we confirm that the FP_N+ method indeed produces accurate and non-negative solutions. To apply the FP_N+ closure on problems at large temporal-spatial scales, we develop a positive asymptotic preserving (AP) numerical PDE solver. We prove that the propose AP scheme maintains stability and accuracy with standard mesh sizes at large temporal-spatial scales, while, for generic numerical schemes, excessive refinements on temporal-spatial meshes are required. We also show that the proposed scheme preserves positivity of the particle concentration, under some time step restriction. Numerical results confirm that the proposed AP scheme is capable for solving linear transport equations at large temporal-spatial scales, for which a generic scheme could fail. Constrained optimization problems are involved in the formulation of the FP_N+ closure to enforce non-negativity of the FP_N+ approximation on the set of quadrature points. These optimization problems can be written as strictly convex quadratic programs (CQPs) with a large number of inequality constraints. To efficiently solve the CQPs, we propose a constraint-reduced variant of a Mehrotra-predictor-corrector algorithm, with a novel constraint selection rule. We prove that, under appropriate assumptions, the proposed optimization algorithm converges globally to the solution at a locally q-quadratic rate. We test the algorithm on randomly generated problems, and the numerical results indicate that the combination of the proposed algorithm and the constraint selection rule outperforms other compared constraint-reduced algorithms, especially for problems with many more inequality constraints than variables.

Formulations and Metaheuristics for combinatorial optimization problems

Combinatorial optimization problems have been strongly addressed throughout history. Their study involves highly applied problems that must be solved in reasonable times. This doctoral Thesis addresses three Operations Research problems: the first deals with the Traveling Salesman Problem with Pickups and Delivery with Handling cost, which was approached with two metaheuristics based on Iterated Local Search; the results show that the proposed methods are faster and obtain good results respect to the metaheuristics from the literature. The second problem corresponds to the Quadratic Multiple Knapsack Problem, and polynomial formulations and relaxations are presented for new instances of the problem; in addition, a metaheuristic and a matheuristic are proposed that are competitive with state of the art algorithms. Finally, an Open-Pit Mining problem is approached. This problem is solved with a parallel genetic algorithm that allows excavations using truncated cones. Each of these problems was computationally tested with difficult instances from the literature, obtaining good quality results in reasonable computational times, and making significant contributions to the state of the art techniques of Operations Research.

Models and algorithms for real-world optimization problems

This thesis deals with efficient solution of optimization problems of practical interest. The first part of the thesis deals with bin packing problems. The bin packing problem (BPP) is one of the oldest and most fundamental combinatorial optimiza- tion problems. The bin packing problem and its generalizations arise often in real-world ap- plications, from manufacturing industry, logistics and transportation of goods, and scheduling. After an introductory chapter, I will present two applications of two of the most natural extensions of the bin packing: Chapter 2 will be dedicated to an application of bin packing in two dimension to a problem of scheduling a set of computational tasks on a computer cluster, while Chapter 3 deals with the generalization of BPP in three dimensions that arise frequently in logistic and transportation, often com- plemented with additional constraints on the placement of items and characteristics of the solution, like, for example, guarantees on the stability of the items, to avoid potential damage to the transported goods, on the distribution of the total weight of the bins, and on compatibility with loading and unloading operations. The second part of the thesis, and in particular Chapter 4 considers the Trans- mission Expansion Problem (TEP), where an electrical transmission grid must be expanded so as to satisfy future energy demand at the minimum cost, while main- taining some guarantees of robustness to potential line failures. These problems are gaining importance in a world where a shift towards renewable energy can impose a significant geographical reallocation of generation capacities, resulting in the ne- cessity of expanding current power transmission grids.

A Multilevel Gradient Method for Optimization Problems

I problemi di ottimizzazione di dimensione finita di larga scala spesso derivano dalla discretizzazione di problemi di dimensione infinita. È perciò possibile descrivere il problema di ottimizzazione su più livelli discreti. Lavorando su un livello più basso di quello del problema considerato, si possono calcolare soluzioni approssimate che saranno poi punti di partenza per il problema di ottimizzazione al livello più fine. I metodi multilivello, già ampiamente presenti in letteratura a partire dagli anni Novanta, sfruttano tale caratteristica dei problemi di ottimizzazione per migliorare le prestazioni dei metodi di ottimizzazione standard. L’obiettivo di questa tesi è quello di implementare una variante multilivello del metodo del gradiente (MGM) e di testarlo su due diversi campi: la risoluzione delle Equazioni alle Derivate Parziali la ricostruzione di immagini. In questo elaborato viene illustrata la teoria dello schema multilivello e presentato l’algoritmo di MGM utilizzato nei nostri esperimenti. Sono poi discusse le modalità di utilizzo di MGM per i due problemi sopra presentati. Per il problema PDE, i risultati ottenuti mostrano un ottimo comportamento di MGM rispetto alla implementazione classica ad un livello. I risultati ottenuti per il problema di ricostruzione di immagini, al contrario delle PDEs, evidenziano come MGM sia efficace solo in determinate condizioni.

A filter algorithm: comparison with NLP solvers

The purpose of this work is to present an algorithm to solve nonlinear constrained optimization problems, using the filter method with the inexact restoration (IR) approach. In the IR approach two independent phases are performed in each iteration—the feasibility and the optimality phases. The first one directs the iterative process into the feasible region, i.e. finds one point with less constraints violation. The optimality phase starts from this point and its goal is to optimize the objective function into the satisfied constraints space. To evaluate the solution approximations in each iteration a scheme based on the filter method is used in both phases of the algorithm. This method replaces the merit functions that are based on penalty schemes, avoiding the related difficulties such as the penalty parameter estimation and the non-differentiability of some of them. The filter method is implemented in the context of the line search globalization technique. A set of more than two hundred AMPL test problems is solved. The algorithm developed is compared with LOQO and NPSOL software packages.

A filter inexact-restoration method for nonlinear programming

A new iterative algorithm based on the inexact-restoration (IR) approach combined with the filter strategy to solve nonlinear constrained optimization problems is presented. The high level algorithm is suggested by Gonzaga et al. (SIAM J. Optim. 14:646–669, 2003) but not yet implement—the internal algorithms are not proposed. The filter, a new concept introduced by Fletcher and Leyffer (Math. Program. Ser. A 91:239–269, 2002), replaces the merit function avoiding the penalty parameter estimation and the difficulties related to the nondifferentiability. In the IR approach two independent phases are performed in each iteration, the feasibility and the optimality phases. The line search filter is combined with the first one phase to generate a “more feasible” point, and then it is used in the optimality phase to reach an “optimal” point. Numerical experiences with a collection of AMPL problems and a performance comparison with IPOPT are provided.

Practical algorithms for a family of waterfilling solutions

Many engineering problems that can be formulatedas constrained optimization problems result in solutionsgiven by a waterfilling structure; the classical example is thecapacity-achieving solution for a frequency-selective channel.For simple waterfilling solutions with a single waterlevel and asingle constraint (typically, a power constraint), some algorithmshave been proposed in the literature to compute the solutionsnumerically. However, some other optimization problems result insignificantly more complicated waterfilling solutions that includemultiple waterlevels and multiple constraints. For such cases, itmay still be possible to obtain practical algorithms to evaluate thesolutions numerically but only after a painstaking inspection ofthe specific waterfilling structure. In addition, a unified view ofthe different types of waterfilling solutions and the correspondingpractical algorithms is missing.The purpose of this paper is twofold. On the one hand, itoverviews the waterfilling results existing in the literature from aunified viewpoint. On the other hand, it bridges the gap betweena wide family of waterfilling solutions and their efficient implementationin practice; to be more precise, it provides a practicalalgorithm to evaluate numerically a general waterfilling solution,which includes the currently existing waterfilling solutions andothers that may possibly appear in future problems.

Efficient solutions to factored MDPs with imprecise transition probabilities

When modeling real-world decision-theoretic planning problems in the Markov Decision Process (MDP) framework, it is often impossible to obtain a completely accurate estimate of transition probabilities. For example, natural uncertainty arises in the transition specification due to elicitation of MOP transition models from an expert or estimation from data, or non-stationary transition distributions arising from insufficient state knowledge. In the interest of obtaining the most robust policy under transition uncertainty, the Markov Decision Process with Imprecise Transition Probabilities (MDP-IPs) has been introduced to model such scenarios. Unfortunately, while various solution algorithms exist for MDP-IPs, they often require external calls to optimization routines and thus can be extremely time-consuming in practice. To address this deficiency, we introduce the factored MDP-IP and propose efficient dynamic programming methods to exploit its structure. Noting that the key computational bottleneck in the solution of factored MDP-IPs is the need to repeatedly solve nonlinear constrained optimization problems, we show how to target approximation techniques to drastically reduce the computational overhead of the nonlinear solver while producing bounded, approximately optimal solutions. Our results show up to two orders of magnitude speedup in comparison to traditional ""flat"" dynamic programming approaches and up to an order of magnitude speedup over the extension of factored MDP approximate value iteration techniques to MDP-IPs while producing the lowest error of any approximation algorithm evaluated. (C) 2011 Elsevier B.V. All rights reserved.

Uma abordagem usando redes neurais artificiais para resolução de problemas de otimização restrita

Sistemas baseados em redes neurais artificiais fornecem altas taxas de computação devido ao uso de um número massivo de elementos processadores simples. Redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver uma rica classe de problemas de otimização. Este artigo apresenta uma nova abordagem para resolver problemas de otimização restrita utilizando redes neurais artificiais. Mais especificamente, uma rede de Hopfield modificada é desenvolvida cujos parâmetros internos são calculados usando a técnica de subespaço válido de soluções. A partir da obtenção destes parâmetros a rede tende a convergir aos pontos de equilíbrio que representam as possíveis soluções para o problema. Exemplos de simulação são apresentados para justificar a validade da abordagem proposta.

Multiarea optimal power flow using multiobjective evolutionary algorithm

In this work the multiarea optimal power flow (OPF) problem is decoupled into areas creating a set of regional OPF subproblems. The objective is to solve the optimal dispatch of active and reactive power for a determined area, without interfering in the neighboring areas. The regional OPF subproblems are modeled as a large-scale nonlinear constrained optimization problem, with both continuous and discrete variables. Constraints violated are handled as objective functions of the problem. In this way the original problem is converted to a multiobjective optimization problem, and a specifically-designed multiobjective evolutionary algorithm is proposed for solving the regional OPF subproblems. The proposed approach has been examined and tested on the RTS-96 and IEEE 354-bus test systems. Good quality suboptimal solutions were obtained, proving the effectiveness and robustness of the proposed approach. ©2009 IEEE.

Algoritmo genético especializado na resolução de problemas com variáveis contínuas e altamente restritos

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Packing a trunk : a physically based approach with full motional freedom

Geometric packing problems may be formulated mathematically as constrained optimization problems. But finding a good solution is a challenging task. The more complicated the geometry of the container or the objects to be packed, the more complex the non-penetration constraints become. In this work we propose the use of a physics engine that simulates a system of colliding rigid bodies. It is a tool to resolve interpenetration conflicts and to optimize configurations locally. We develop an efficient and easy-to-implement physics engine that is specialized for collision detection and contact handling. In succession of the development of this engine a number of novel algorithms for distance calculation and intersection volume were designed and imple- mented, which are presented in this work. They are highly specialized to pro- vide fast responses for cuboids and triangles as input geometry whereas the concepts they are based on can easily be extended to other convex shapes. Especially noteworthy in this context is our ε-distance algorithm - a novel application that is not only very robust and fast but also compact in its im- plementation. Several state-of-the-art third party implementations are being presented and we show that our implementations beat them in runtime and robustness. The packing algorithm that lies on top of the physics engine is a Monte Carlo based approach implemented for packing cuboids into a container described by a triangle soup. We give an implementation for the SAE J1100 variant of the trunk packing problem. We compare this implementation to several established approaches and we show that it gives better results in faster time than these existing implementations.

A general-purpose tunable landscape generator

The research literature on metalieuristic and evolutionary computation has proposed a large number of algorithms for the solution of challenging real-world optimization problems. It is often not possible to study theoretically the performance of these algorithms unless significant assumptions are made on either the algorithm itself or the problems to which it is applied, or both. As a consequence, metalieuristics are typically evaluated empirically using a set of test problems. Unfortunately, relatively little attention has been given to the development of methodologies and tools for the large-scale empirical evaluation and/or comparison of metaheuristics. In this paper, we propose a landscape (test-problem) generator that can be used to generate optimization problem instances for continuous, bound-constrained optimization problems. The landscape generator is parameterized by a small number of parameters, and the values of these parameters have a direct and intuitive interpretation in terms of the geometric features of the landscapes that they produce. An experimental space is defined over algorithms and problems, via a tuple of parameters for any specified algorithm and problem class (here determined by the landscape generator). An experiment is then clearly specified as a point in this space, in a way that is analogous to other areas of experimental algorithmics, and more generally in experimental design. Experimental results are presented, demonstrating the use of the landscape generator. In particular, we analyze some simple, continuous estimation of distribution algorithms, and gain new insights into the behavior of these algorithms using the landscape generator.

Trajectory planning of single and dual-arm robots for time-optimal handling of liquids and objects

This Thesis studies the optimal control problem of single-arm and dual-arm serial robots to achieve the time-optimal handling of liquids and objects. The first topic deals with the planning of time-optimal anti-sloshing trajectories of an industrial robot carrying a cylindrical container filled with a liquid, considering 1-dimensional and 2-dimensional planar motions. A technique for the estimation of the sloshing height is presented, together with its extension to 3-dimensional motions. An experimental validation campaign is provided and discussed to assess the thoroughness of such a technique. As far as anti-sloshing trajectories are concerned, 2-dimensional paths are considered and, for each one of them, three constrained optimizations with different values of the sloshing-height thresholds are solved. Experimental results are presented to compare optimized and non-optimized motions. The second part focuses on the time-optimal trajectory planning for dual-arm object handling, employing two collaborative robots (cobots) and adopting an admittance-control strategy. The chosen manipulation approach, known as cooperative grasping, is based on unilateral contact between the cobots and the object, and it may lead to slipping during motion if an internal prestress along the contact-normal direction is not prescribed. Thus, a virtual penetration is considered, aimed at generating the necessary internal prestress. The stability of cooperative grasping is ensured as long as the exerted forces on the object remain inside the static-friction cone. Constrained-optimization problems are solved for 3-dimensional paths: the virtual penetration is chosen among the control inputs of the problem and friction-cone conditions are treated as inequality constraints. Also in this case experiments are presented in order to prove evidence of the firm handling of the object, even for fast motions.

Derivative-free optimization and filter methods to solve nonlinear constrained problems

In real optimization problems, usually the analytical expression of the objective function is not known, nor its derivatives, or they are complex. In these cases it becomes essential to use optimization methods where the calculation of the derivatives, or the verification of their existence, is not necessary: the Direct Search Methods or Derivative-free Methods are one solution. When the problem has constraints, penalty functions are often used. Unfortunately the choice of the penalty parameters is, frequently, very difficult, because most strategies for choosing it are heuristics strategies. As an alternative to penalty function appeared the filter methods. A filter algorithm introduces a function that aggregates the constrained violations and constructs a biobjective problem. In this problem the step is accepted if it either reduces the objective function or the constrained violation. This implies that the filter methods are less parameter dependent than a penalty function. In this work, we present a new direct search method, based on simplex methods, for general constrained optimization that combines the features of the simplex method and filter methods. This method does not compute or approximate any derivatives, penalty constants or Lagrange multipliers. The basic idea of simplex filter algorithm is to construct an initial simplex and use the simplex to drive the search. We illustrate the behavior of our algorithm through some examples. The proposed methods were implemented in Java.