No description available.

Dans ce document, nous étudions deux problèmes de sectorisation et proposons plusieurs méthodes de résolution exactes basées sur la décomposition de Dantzig-Wolfe et la génération de colonnes. Nous proposons deux modélisations en fonction de la manière d’appréhender l’objectif du problème qui consiste à obtenir des secteurs compacts. Pour chacune des modélisations, nous comparons des approches de résolution exactes basées sur des formulations compactes ou sur des formulations étendues obtenues par la décomposition de Dantzig-Wolfe. Le premier type de modèles proposé définit la fonction objectif à la manière d’un problème de p-median. Concernant les méthodes de résolution pour ce type de modèle, l’accent est mis sur l’accélération de la convergence de l’algorithme de génération de colonnes en mettant en place des techniques d’agrégation de contraintes afin de réduire la dégénérescence de l’algorithme du simplexe. Les expérimentations numériques montrent que la méthode d’agrégation de contraintes proposée permet effectivement de réduire le nombre d’itérations dégénérées. Cependant, elle ne suffit pas à accélérer l’algorithme de branch-and-price. Le choix d’utilisation de la formulation compacte ou de la formulation étendue dépend du type d’instances résolu. Le second type de modèles formule l’objectif d’une manière assez proche de celui des problèmes de p-centre. L’utilisation d’un tel objectif complexifie la résolution des sous-problèmes de génération de colonnes. L’accent est donc mis sur la conception d’algorithmes de branch-and-bound et de programmation dynamique pour les résoudre efficacement. Les expériences montrent que l’algorithme de branch-and-price surpasse les approches de résolution utilisant une formulation compacte du problème. / In this document, we study two districting problems and propose several exact methods, based on Dantzig-Wolfe decomposition and column generation, to solve them. For each model, we compare exact approaches based either on compact formulations or on extended formulations obtained using Dantzig-Wolfe decomposition. The first type of model that we propose defines the objective function in a p-median problem fashion. Regarding the methods used to solve that kind of model, we emphasize accelerating the convergence of the column generation algorithm by designing constraint aggregation techniques in order to reduce the degeneracy in the simplex algorithm. Numerical experiments show that this constraint aggregation method indeed reduces the proportion of degenerated iterations. However, it is not enough to speed up the branch-and-price algorithm. Choosing to tackle the problem through either a compact formulation or an extended formulation depends on the structure of the instances to solve. The second type of model formulates the objective function in a way quite similar to that of p-centre problems. Using such an objective function induces complex column generation subproblems. We focus on designing branch-and-bound and dynamic programming algorithms in order to solve them efficiently. Experiments show that the branch-and-price approach surpasses any proposed method based on compact formulations of the problem.

Disertační práce začíná rešerší výpočtů pro návrh sendvičových nosníků, desek a složitějších konstrukcí, kde zaujímá významnou roli MKP. Dále jsou popsány optimalizační metody pro ujasnění široké oblasti matematického programování a základních principů topologické optimalizace až po její implementaci na kompozitní konstrukce jinými autory. Pro názornost jsou zmíněny jak analytické, tak i numerické přístupy k optimalizaci sendvičů, kde numerické přístupy umožňují řešit daleko širší oblast úkolů. Cíl disertační práce je stanoven jako implementace zautomatizovaného algoritmu pro optimalizaci za účelem vylepšení návrhového procesu sendvičů s ohledem na napjatost a únosnost. Cíle je dosaženo prostřednictvím vlastní implementace gradientní optimalizace založené na principech topologické optimalizace, známé jako diskrétní optimalizace materiálu (Discrete Material Optimization - DMO) a jejích variant, které pomáhají najít optimální vrstvení. Přístup k materiálové interpolaci a interpolaci poruchový omezujících podmínek je vyvinut a naprogramován v pythonu za použití teorie smykových deformací prvního řádu (First Order Shear Deformation Theory - FSDT) pro vyhodnocení napětí na elementech na základě zatížení daného MKP řešičem Nastran. Gradientní optimalizér hledá nejlepší materiály pro každou vrstvu potahu sendviče a jádra z definovaných kandidátů. Program je odzkoušený na příkladech různé složitosti od nosníku tvořeného jedním elementem, kde je skutečné optimum známé, až po praktickou úlohu sendvičové kuchyňky z dopravního letadla. Výsledky ukázaly, že algoritmus je schopen dosáhnout diskrétního řešení bez (významného) narušení omezujících podmínek a může tedy být prakticky využit ke zefektivnění koncepčního návrhu sendvičů.

[pt] Otimização Robusta é uma das formas mais comuns de considerar in- certeza nos parâmetros de um problema de otimização. A forma tradicional de achar soluções robustas consiste em resolver a contraparte robusta de um problema, o que em muitos casos, na prática, pode ter um custo computacional proibitivo. Neste trabalho, estudamos métodos iterativos para resolver problemas de Otimização Convexa Robusta de forma aproximada, que não exigem a formulação da contraparte robusta. Utilizamos conceitos de Online Learning para propor um novo algoritmo que utiliza agregação de restrições, demonstrando garantias teóricas de convergência. Desenvolvemos ainda uma modificação deste algoritmo que, apesar de não possuir tais garantias, obtém melhor performance prática. Por fim, implementamos outros métodos iterativos conhecidos da literatura de Otimização Robusta e fazemos uma análise computacional de seus desempenhos. / [en] Robust Optimization is a common paradigm to consider uncertainty in the parameters of an optimization problem. The traditional way to find robust solutions requires solving the robust counterpart of an optimiza- tion problem, which, in practice, can often be prohibitively costly. In this work, we study iterative methods to approximately solve Robust Convex Optimization problems, which do not require solving the robust counter- part. We use concepts from the Online Learning framework to propose a new algorithm that performs constraint aggregation, and we demonstrate theoretical convergence guarantees. We then develop a modification of this algorithm that, although without such guarantees, obtains better practical performance. Finally, we implement other classical iterative methods from the Robust Optimization literature and present a computational study of their performances.