京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19122号 / 情博第568号 / 新制||情||100(附属図書館) / 32073 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 太田 快人, 教授 永持 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

A multi-commodity flow problem consists of moving several commodities from their respective sources to their sinks through a network where each edge has different costs and capacity constraints. This paper explores different linear programming algorithms and their performance regarding finding an optimal solution for multi-commodity flow problems. By testing several of different network constraints, we examine which algorithms are most suitable for specific network and problem structures. Furthermore, we implement our own multi-commodity solver and compare its performance against state-of-the-art linear programming solvers. The results show that for the methods we tested it is difficult to discern which class of linear programming methods are optimal solvers for multi-commodity flow problems and that their performance depends on how the network and commodities are structured.

No description available.

La présente étude concerne l’étude d’optimisation thermique d’une machine électrique. Un modèle nodal est utilisé pour la simulation du champ de température. Ce modèle résout l’équation de la chaleur en trois dimensions, en coordonnées cylindriques et en régime transitoire ou permanent. On prend en compte les deux mécanismes de transport les plus importants : La conduction et la convection. L’évaluation de ce modèle est effectuée par l’intermédiaire de 13 valeurs de débits de référence. C’est en faisant varier ces variables qu’on évalue la performance du refroidissement dans la machine. Avant de partir sur l’étude d’optimisation de cettegéométrie, on a lancé une étude d’optimisation d’un cas plus simple afin de mieux comprendre les différents outils d’optimisation disponibles. L’expérience acquise avec les cas simples est utilisée dans l’optimisation thermique de la machine. La machine est thermiquement évaluée sur la combinaison de deux critères : la température maximale et la température moyenne. Des contraintes ont été additionnées afin d’obtenir des résultats physiquement acceptables. Le problème est résolu à l’aide des méthodes de gradient (Active-set et Point-Intérieur) et des Algorithmes Génétiques. / This work relates the thermal optimization of an electrical machine. The lumped method is used to simulate the temperature field. This model solves the heat equation in three dimensions, in cylindrical coordinates and in transient or steady state. We consider two transport mechanisms: conduction and convection. The evaluation of this model is performed by means of 13 design variables that correspond to the main flow rates of the equipment. We analyse the machine cooling performance by varying these 13 flow rates. Before starting the study of such a complicated geometry, we picked a simpler case in order to better understand the variety of the available optimization tools. The experience obtained in the simpler case is applyed in the resolution of the thermal optimization problem of the electrical machine. This machine is evaluated from the thermal point of view by combining two criteria : the maximum and the mean temperature. Constraints are used to keep the problem consistent. We solved the problem using the gradient based methods (Active-set and Interior-Point) and the Genetic Algorithms.

Neste trabalho propomos uma abordagem que utiliza o método de barreira modificada/penalidade para a resolução de problemas restritos gerais de otimização. Para isso, foram obtidos dados teóricos, a partir de um levantamento bibliográfico, que explicitaram os métodos primal-dual barreira logarítmica e método de barreira modificada. Nesta abordagem, as restrições de desigualdade canalizadas são tratadas pela função barreira de Frisch modificada, ou por uma extrapolação quadrática e as restrições de igualdade do problema através da função Lagrangiana. A implementação consiste num duplo estágio de aproximação: um ciclo externo, onde o problema restrito é convertido em um problema irrestrito, usando a função Lagrangiana barreira modificada/penalidade; e um ciclo interno, onde o método de Newton é utilizado para a atualização das variáveis primais e duais. É apresentada também uma função barreira clássica extrapolada para a inicialização dos multiplicadores de Lagrange. A eficiência do método foi verificada utilizando um problema teste e em problemas de fluxo de potência ótimo (FPO). / In this paper, we propose an approach that utilizes the penalty/modified barrier method to solve the general constrained problems. On this purpose, theoretical data were obtained, from a bibliographical review, which enlightened the logarithmic barrier primal-dual method and modified barrier method. In this approach, the bound constraints are handled by the modified log-barrier function, or by quadratic extrapolation and the equality constraints of the problem through Lagrangian function. The method, as implemented, consists of a two-stage approach: an outer cycle, where the constrained problem is transformed into unconstrained problem, using penalty/modified barrier Lagrangian function; and an inner cycle, where the Newton\'s method is used for update the primal and dual variables. Also, it is presented a classical barrier extrapolated function for initialization of Lagrange multipliers. The effectiveness of the proposed approach has been examined by solving a test problem and optimal power flow problems (OPF).

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura

Neste trabalho, os métodos de pontos interiores primal-dual e preditor corretor são estudados e desenvolvidos para o problema de minimização de custos na geração e perdas na transmissão do pré-despacho DC (fluxo de carga em corrente contínua) de um sistema de potência hidroelétrico, com base no modelo de fluxo em redes e no princípio do mínimo esforço. A estrutura matricial, resultante da simplificação do problema proposto pela inclusão do princípio do mínimo esforço, é estudada visando implementações eficientes. / In this work, the primal-dual and predictor corrector interior points methods are studied and developed for the predispatch DC problem that minimizes generation and transmission losses on hydroelectric power systems, on the basis of the network flow model and the minimum effort principle. The matrix structure, resulting of the simplification of the problem considered by inclusion of the minimum effort principle, is studied aiming efficient implementations. A disturbed primal-dual method is considered on the basis of a heuristic definition that determine the choice of the disturbance parameter. This method showed to be efficient in practice and converged in fewer iterations when compare with an existing implementation of the network flow model.

Neste trabalho, propomos um método de pontos interiores para minimização com restrições lineares de grande porte. Este método explora a linearidade das restrições, partindo de um ponto viável e preservando a viabilidade dos iterandos. Apresentamos os principais resultados de convergência global, além de uma descrição rica em detalhes de uma implementação prática de todos os passos do método. Para atestar a implementação do método, exibimos uma ampla experimentação numérica, e uma análise comparativa com métodos bem difundidos na comunidade de otimização contínua. / In this work, we propose an interior-point method for large-scale linearly constrained optimization. This method explores the linearity of the constraints, starting from a feasible point and preserving the feasibility of the iterates. We present the main global convergence results, together with a rich description of the implementation details of all the steps of the method. To validate the implementation of the method, we present a wide set of numerical experiments and a comparative analysis with well known softwares of the continuous optimization community.

Neste trabalho propomos uma abordagem que utiliza o método de barreira modificada/penalidade para a resolução de problemas restritos gerais de otimização. Para isso, foram obtidos dados teóricos, a partir de um levantamento bibliográfico, que explicitaram os métodos primal-dual barreira logarítmica e método de barreira modificada. Nesta abordagem, as restrições de desigualdade canalizadas são tratadas pela função barreira de Frisch modificada, ou por uma extrapolação quadrática e as restrições de igualdade do problema através da função Lagrangiana. A implementação consiste num duplo estágio de aproximação: um ciclo externo, onde o problema restrito é convertido em um problema irrestrito, usando a função Lagrangiana barreira modificada/penalidade; e um ciclo interno, onde o método de Newton é utilizado para a atualização das variáveis primais e duais. É apresentada também uma função barreira clássica extrapolada para a inicialização dos multiplicadores de Lagrange. A eficiência do método foi verificada utilizando um problema teste e em problemas de fluxo de potência ótimo (FPO). / In this paper, we propose an approach that utilizes the penalty/modified barrier method to solve the general constrained problems. On this purpose, theoretical data were obtained, from a bibliographical review, which enlightened the logarithmic barrier primal-dual method and modified barrier method. In this approach, the bound constraints are handled by the modified log-barrier function, or by quadratic extrapolation and the equality constraints of the problem through Lagrangian function. The method, as implemented, consists of a two-stage approach: an outer cycle, where the constrained problem is transformed into unconstrained problem, using penalty/modified barrier Lagrangian function; and an inner cycle, where the Newton\'s method is used for update the primal and dual variables. Also, it is presented a classical barrier extrapolated function for initialization of Lagrange multipliers. The effectiveness of the proposed approach has been examined by solving a test problem and optimal power flow problems (OPF).

Multivariate adaptive regression spline (MARS) denotes a modern methodology from statistical learning which is very important in both classification and regression, with an increasing number of applications in many areas of science, economy and technology. MARS is very useful for high dimensional problems and shows a great promise for fitting nonlinear multivariate functions. MARS technique does not impose any particular class of relationship between the predictor variables and outcome variable of interest. In other words, a special advantage of MARS lies in its ability to estimate the contribution of the basis functions so that both the additive and interaction effects of the predictors are allowed to determine the response variable. The function fitted by MARS is continuous, whereas the one fitted by classical classification methods (CART) is not. Herewith, MARS becomes an alternative to CART. The MARS algorithm for estimating the model function consists of two complementary algorithms: the forward and backward stepwise algorithms. In the first step, the model is built by adding basis functions until a maximum level of complexity is reached. On the other hand, the backward stepwise algorithm is began by removing the least significant basis functions from the model. In this study, we propose not to use the backward stepwise algorithm. Instead, we construct a penalized residual sum of squares (PRSS) for MARS as a Tikhonov regularization problem, which is also known as ridge regression. We treat this problem using continuous optimization techniques which we consider to become an important complementary technology and alternative to the concept of the backward stepwise algorithm. In particular, we apply the elegant framework of conic quadratic programming which is an area of convex optimization that is very well-structured, herewith, resembling linear programming and, hence, permitting the use of interior point methods. The boundaries of this optimization problem are determined by the multiobjective optimization approach which provides us many alternative solutions. Based on these theoretical and algorithmical studies, this MSc thesis work also contains applications on the data investigated in a T&Uuml / BiTAK project on quality control. By these applications, MARS and our new method are compared.