We develop a detailed, large-scale, airspace planning and collaborative decision-making model (APCDM), that is part of an $11.5B, 10-year, Federal Aviation Administration (FAA)-sponsored effort to increase U.S. National Airspace (NAS) capacity by 30 percent. Given a set of flights that must be scheduled during some planning horizon, we use a mixed-integer programming formulation to select a set of flight plans from among alternatives subject to flight safety, air traffic control workload, and airline equity constraints. Novel contributions of this research include three-dimensional probabilistic conflict analyses, the derivation of valid inequalities to tighten the conflict safety representation constraints, the development of workload metrics based on average (and its variance from) peak load measures, and the consideration of equity among airline carriers in absorbing the costs related to re-routing, delays, and cancellations. We also propose an improved set of flight plan cost factors for representing system costs and investigating fairness issues by addressing flight dependencies occurring in hubbed operations, as well as market factors such as schedule convenience, reliability, and the timeliness of connections. The APCDM model has potential use for both tactical and strategic applications, such as air traffic control in response to severe weather phenomenon or spacecraft launches, FAA policy evaluation, Homeland Defense contingency planning, and military air campaign planning. The model is tested to consider various airspace restriction scenarios imposed by dynamic severe weather systems and space launch Special Use Airspace (SUA) impositions. The results from this model can also serve to augment the FAA's National Playbook of standardized flight profiles in different disruption-prone regions of the National Airspace. / Ph. D.

With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows probabilistic data parameters in mixed integer programming, a well-known tool for optimization modeling with deterministic input data. However, akin to the mixed integer programs, these stochastic models are theoretically intractable and computationally challenging to solve because of the presence of integer variables. This dissertation focuses on theory, algorithms and applications of two-stage stochastic mixed integer (non)linear programs and it has three-pronged plan. In the first direction, we study two-stage stochastic p-order conic mixed integer programs (TSS-CMIPs) with p-order conic terms in the second-stage objectives. We develop so called scenario-based (non)linear cuts which are added to the deterministic equivalent of TSS-CMIPs (a large-scale deterministic conic mixed integer program). We provide conditions under which these cuts are sufficient to relax the integrality restrictions on the second-stage integer variables without impacting the integrality of the optimal solution of the TSS-CMIP. We also introduce a multi-module capacitated stochastic facility location problem and TSS-CMIPs with structured CMIPs in the second stage to demonstrate the significance of the foregoing results for solving these problems. In the second direction, we propose risk-neutral and risk-averse two-stage stochastic mixed integer linear programs for load shed recovery with uncertain renewable generation and demand. The models are implemented using a scenario-based approach where the objective is to maximize load shed recovery in the bulk transmission network by switching transmission lines and performing other corrective actions (e.g. generator re-dispatch) after the topology is modified. Experiments highlight how the proposed approach can serve as an offline contingency analysis tool, and how this method aids self-healing by recovering more load shedding. In the third direction, we develop a dual decomposition approach for solving two-stage stochastic quadratically constrained quadratic mixed integer programs. We also create a new module for an open-source package DSP (Decomposition for Structured Programming) to solve this problem. We evaluate the effectiveness of this module and our approach by solving a stochastic quadratic facility location problem. / Doctor of Philosophy / With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows two-stages of decision making where the first-stage strategic decisions (such as deciding the locations of facilities or topology of a power transmission network) are taken before the realization of uncertainty, and the second-stage operational decisions (such as transportation decisions between customers and facilities or power flow in the transmission network) are taken in response to the first-stage decision and a realization of the uncertain (demand) data. This modeling tool is gaining wide acceptance because of its applications in healthcare, power systems, wildfire planning, logistics, and chemical industries, among others. Though intriguing, two-stage stochastic programs are computationally challenging. Therefore, it is crucial to develop theoretical results and computationally efficient algorithms, so that these models for real-world applied problems can be solved in a realistic time frame. In this dissertation, we consider two-stage stochastic mixed integer (non)linear programs, provide theoretical and algorithmic results for them, and introduce their applications in logistics and power systems. First, we consider a two-stage stochastic mixed integer program with p-order conic terms in the objective that has applications in facility location problem, power system, portfolio optimization, and many more. We provide a so-called second-stage convexification technique which greatly reduces the computational time to solve a facility location problem, in comparison to solving it directly with a state-of-the-art solver, CPLEX, with its default settings. Second, we introduce risk-averse and risk-neutral two-stage stochastic models to deal with uncertainties in power systems, as well as the risk preference of decision makers. We leverage the inherent flexibility of the bulk transmission network through the systematic switching of transmission lines in/out of service while accounting for uncertainty in generation and demand during an emergency. We provide abundant computational experiments to quantify our proposed models, and justify how the proposed approach can serve as an offline contingency analysis tool. Third, we develop a new solution approach for two-stage stochastic mixed integer programs with quadratic terms in the objective function and constraints and implement it as a new module for an open-source package DSP We perform computational experiments on a stochastic quadratic facility location problem to evaluate the performance of this module.

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable. / Location decisions are frequently subject to dynamic aspects such as changes in customer demand. Often, flexibility regarding the geographic location of facilities, as well as their capacities, is the only solution to such issues. Even when demand can be forecast, finding the optimal schedule for the deployment and dynamic adjustment of capacities remains a challenge. In this thesis, we focus on multi-period facility location problems that allow for dynamic capacity adjustment, in particular those with complex cost structures. We investigate such problems from different Operations Research perspectives, presenting and comparing several mixed-integer programming (MIP) models, assessing their use in practice and developing efficient solution algorithms. The thesis is divided into four parts. We first motivate our research by an industrial application, in which a logging company needs to locate camps to host the workers involved in forestry operations. We present a MIP model that allows for the construction of additional camps, the expansion and relocation of existing ones, as well as partial closing and reopening of facilities. The model uses particular capacity constraints that involve integer rounding on the left hand side. Economies of scale are considered on several levels of the cost structure. The usefulness of the model is assessed by two case studies. The second part introduces the Dynamic Facility Location Problem with Generalized Modular Capacities (DFLPG). The model generalizes existing formulations for several dynamic facility location problems and provides stronger linear programming relaxations than the specialized formulations. The model can address facility location problems where the costs for capacity changes are defined for all pairs of capacity levels, as it is the case in the previously introduced industrial problem. It is applied to three special cases: capacity expansion and reduction, temporary facility closing and reopening, and the combination of both. We prove dominance relationships between our formulation and existing models for the special cases. Computational experiments on a large set of randomly generated instances with up to 100 facility locations and 1000 customers show that our model can obtain optimal solutions in shorter computing times than the existing specialized formulations. Given the complexity of such models for large instances, the third part of the thesis proposes efficient Lagrangian heuristics. Based on subgradient and bundle methods, good quality solutions are found even for large-scale instances with up to 250 facility locations and 1000 customers. To improve the final solution quality, a restricted model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian based heuristics provide highly reliable results, producing good quality solutions in short computing times even for instances where generic solvers do not find feasible solutions. Finally, we adapt the Lagrangian heuristics to solve the industrial application. Two different relaxations are proposed and compared. Extensions of the previous concepts are presented to ensure a reliable solution of the problem, providing high quality solutions in reasonable computing times.

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes. / The berth allocation problem (BAP) is one of the key decision problems at port terminals and it has been widely studied. In previous research, the BAP has been formulated as a generalized set partitioning problem (GSPP) and solved using standard solver. The assignments (columns) were generated a priori in a static manner and provided as an input to the optimization model. The GSPP approach is able to solve to optimality relatively large size problems. However, a main drawback of this approach is the explosion in the number of feasible assignments of vessels with increase in problem size which leads in turn to the optimization solver to run out of memory. In this research, we address the limitation of the GSPP approach and present a column generation framework where assignments are generated dynamically to solve large problem instances of the berth allocation problem at port terminals. We propose a column generation based algorithm to address the problem that can be easily adapted to solve any variant of the BAP based on different spatial and temporal attributes. We test and validate the proposed approach on a discrete berth allocation model with dynamic vessel arrivals and berth dependent handling times. Computational experiments on a set of artificial instances indicate that the proposed methodology can solve even very large problem sizes to optimality or near optimality in computational time of only a few minutes.

No description available.

Wir betrachten ein Kraftwerkssystem mit thermischen Blöcken und Pumpspeicherwerken und entwickeln dafür ein Modell für den kostenoptimalen Wochenbetrieb. Auf Grund der Ungewißheit des Bedarfs an elektrischer Energie ist das mathematische Modell ein mehrstufiges stochastisches Problem. Dieses Modell beinhaltet viele gemischt-ganzzahlige stochastische Entscheidungsvariablen. Die Variablen einzelner Einheiten sind aber nur durch wenige Nebenbedingungen miteinander verbunden, welches die Zerlegung in stochastische Teilprobleme erleichtert. Diese stochastischen Teilprobleme besitzen deterministische Analoga, deren Lösungsverfahren entsprechend erweitert werden können. In dieser Arbeit werden ein Abstiegsverfahren für stochastische Speicherprobleme und eine Erweiterung der dynamischen Programmierung auf stochastische Probleme betrachtet. Die Lösung des dualen Problems führt zu Schattenpreisen, die bestimmte Einsatzentscheidungen bevorteilen. Die Heuristik zur Suche von primalen zulässigen Punkten wertet eine Folge von zugeordneten Economic-Dispatch-Problemen aus. Die Kombination der Einschränkung auf dual bevorzugte Fahrweisen (Lagrangian reduction) mit der Auswertung einer Folge von Economic-Dispatch-Problemen (Facettensuche) führt zu einem effizienten Verfahren. Die numerischen Ergebnisse an Hand realistischer Daten eines deutschen Versorgungsunternehmens rechtfertigen diesen Zugang. / We consider a power generation system comprising thermal units and pumped hydro storage plants, and introduce a model for its weekly cost-optimal operation. Due to the uncertainty of the load, the mathematical model represents a dynamic (multi-stage) stochastic program. The model involves a large number of mixed-integer (stochastic) decisions but its constraints are loosely coupled across operating power units. The coupling structure is used to design a stochastic Lagrangian relaxation method, which leads to a decomposition into stochastic single unit subproblems. The stochastic subproblems have deterministic counterparts, which makes it easy to develop algorithms for the stochastic problems. In this paper, a descent method for stochastic storage problems and an extension of dynamic programming towards stochastic programs are developed. The solution of the dual problem provides multipliers leading to preferred schedules (binary primal variables). The crossover heuristics evaluates the economic dispatch problems corresponding to a sequence of such preferred schedules. The combination of the restriction on dual preferred schedules (Lagrangian reduction) with the evaluation of a sequence (facet search) leads to an efficient method. The numerical results on realistic data of a German utility justify this approach.

O objetivo deste trabalho é verificar se ações de companhias que adotam boas práticas de governança corporativa proporcionam maiores retornos e menor risco aos investidores ao compará-las com ações de empresas que não se comprometeram a adotar tais práticas. Para cumprir este objetivo são utilizados três modelos de otimização de portfolios. O primeiro modelo, o modelo Maxmin, maximiza o menor retorno mensal, enquanto o segundo maximiza o retorno anual. Já o terceiro modelo minimiza o desvio médio absoluto da carteira, que é considerado como uma medida de risco. Todos os modelos serão solucionados por métodos de programação linear (PL), em que não é considerado o número de ações da carteira, e de programação inteira mista (PIM), em que são inseridas restrições nos modelos que permitem especificar o número mínimo e máximo de ações. Os modelos são aplicados para uma carteira composta por ações que estão no IGC e para uma carteira formada por ações que estão no IBOVESPA. Os resultados obtidos para as duas carteiras são comparados, buscando evidenciar a idéia de que a boa governança corporativa está relacionada com maiores retornos e menores riscos. Neste sentido, o presente trabalho busca verificar empiricamente se, realmente, as ações de empresas com boa governança proporcionam maiores retornos e menor risco aos acionistas e, desta forma, fornecer novas informações que contribuam com o conhecimento e maior desenvolvimento do tema. Os resultados deste trabalho evidenciam o melhor desempenho da carteira formada pelas ações do IGC, que apresentaram maiores retornos e menores riscos. Diante destes resultados, há indícios de que o compromisso com práticas adicionais de boa governança corporativa pode estar proporcionando maior retorno e menor risco. / The objective of this work is to verify if shares of companies that adopt good corporate governance practice provides greater returns and lower risks to investors when compared with shares of companies that do not adopt these set of practices. Three optimization portfolios models were used to accomplish this objective. The first model, the maxmin model, maximizes the smallest monthly return, while the second maximizes the annual return. The third model minimizes the mean absolute deviation, which is considered a risk measure. All the models will be solved by linear programming (LP) methods, when it is not possible to determinate the number of shares in the portfolio, and mixed integer programming (MIP) methods, in which are inserted constraints that permit specify the minimum number and maximum number of shares in the models. The three models are applied to a portfolio formed by shares that are in IGC and to a portfolio formed by shares that are in IBOVESPA. The obtained results for both portfolios will be compared, willing to evidence the idea that good corporate governance is related with greater returns and lower risks. This study has the purpose to verify empirically if shares of companies with good governance provides greater returns and lower risks to investors and, this way, supplies new information that contribute with knowledge and greater development of the theme. The results of this work show that the better performance of portfolio formed by shares of IGC, that presented greater returns and lower risks. According to these results, there are indicators that the commitment with additional corporate governance practices can be providing greater returns and lower risks.

No description available.

<p>У раду је презентован нови хибридни алгоритам симулираног каљења (SA) и<br />мешовитог целобројног линеарног програмирања (MILP) за статичко планирање<br />радијалних дистрибутивних мрежа са дистрибутивним генераторима. Oвде је<br />развијен један нови статички алгоритам који уважава: инвестиционе трошкове,уважава<br />трошкове губитака, трошкове прекида напајања потрошача услед кварова на<br />гранама и дистрибутивним генераторима, као и трошкове губитака производње<br />дистрибутивних генератора услед кварова на гранама.<br />Проблем планирања развоја дистрибутивних мрежа је најпре моделован као<br />проблем целобројног мешовитог целобројног линеарног програмирања (MILP) са<br />циљем минимизације наведених трошкова. Да би се смањила комплексност<br />проблема планирања, предложена је декомпозиција проблема на низ мањих<br />подпроблема (локалних мрежа) које се решавају MILP моделом. Поступак SA<br />декомпозиције и решавања итератативно је вођен и контролисан са предложеним<br />алгоритмом који укључује механизам интензификације и диверзификације како<br />би се постигло крајње решење.<br />Применом алгоритма на реалним мрежама очекује се да нови хеуристичкичекује<br />алгоритам генерише квалитетније планове развоја од хеуристичких алгоритама и<br />алгоритама заснованих на вештачкој интелигенцији који су до сада развијени.<br />Решења добијена применом развијеног алгоритма ће бити упоређена са правим<br />глобалним оптимумом, и на основу тога ће се дефинисати његов квалитет.</p> / <p>U radu je prezentovan novi hibridni algoritam simuliranog kaljenja (SA) i<br />mešovitog celobrojnog linearnog programiranja (MILP) za statičko planiranje<br />radijalnih distributivnih mreža sa distributivnim generatorima. Ovde je<br />razvijen jedan novi statički algoritam koji uvažava: investicione troškove,uvažava<br />troškove gubitaka, troškove prekida napajanja potrošača usled kvarova na<br />granama i distributivnim generatorima, kao i troškove gubitaka proizvodnje<br />distributivnih generatora usled kvarova na granama.<br />Problem planiranja razvoja distributivnih mreža je najpre modelovan kao<br />problem celobrojnog mešovitog celobrojnog linearnog programiranja (MILP) sa<br />ciljem minimizacije navedenih troškova. Da bi se smanjila kompleksnost<br />problema planiranja, predložena je dekompozicija problema na niz manjih<br />podproblema (lokalnih mreža) koje se rešavaju MILP modelom. Postupak SA<br />dekompozicije i rešavanja iteratativno je vođen i kontrolisan sa predloženim<br />algoritmom koji uključuje mehanizam intenzifikacije i diverzifikacije kako<br />bi se postiglo krajnje rešenje.<br />Primenom algoritma na realnim mrežama očekuje se da novi heurističkičekuje<br />algoritam generiše kvalitetnije planove razvoja od heurističkih algoritama i<br />algoritama zasnovanih na veštačkoj inteligenciji koji su do sada razvijeni.<br />Rešenja dobijena primenom razvijenog algoritma će biti upoređena sa pravim<br />globalnim optimumom, i na osnovu toga će se definisati njegov kvalitet.</p> / <p>In this paper, we present a new hybrid algorithm of simulated annealing and mixed<br />integer linear programming for static planning radial distribution networks with<br />distribution generators. It was developed a new static algorithm that takes into<br />account: investment costs, losses, costs a power of consumers due to faults on theestment<br />branches and distribution generators, as well as the cost of loss of production of<br />distribution of generators due to faults on the branches.<br />The problem of planning the development of the distribution network is first modeled<br />as a mixed integer problem of integer linear programming with the goal of minimizing<br />those costs. To reduce the complexity of the planning problem, the proposed<br />decomposition problem in a number of smaller sub-probproblems (local network) which<br />are dealt model. The process of decomposition and solving iteratativno is managed<br />and controlled with the proposed algorithm, which includes a mechanism of<br />intensification and diversification to achieve a final solution.<br />By applying the algorithm on real networks, it is expected that new heuristic<br />algorithm generates better plans for the development of heuristic algorithms and<br />algorithms based on artificial intelligence that have been developed. Solutions<br />obtained using the developed heuristic algorithm will be compared with the real<br />global optimum, and on that basis will also define their quality.</p>

[pt] Esta tese investiga e desenvolve algoritmos baseados em relaxação Lagrangiana e técnica de desagregação multiparamétrica normalizada para resolver problemas não convexos de programação inteira-mista quadrática com restrições quadráticas. Primeiro, é realizada uma revisão de técnias de relaxação para este tipo de problema e subclasses do mesmo. Num segundo momento, a técnica de desagregação multiparamétrica normalizada é aprimorada para sua versão reformulada onde o tamanho dos subproblemas a serem resolvidos tem seu tamanho reduzido, em particular no número de variáveis binárias geradas. Ademais, dificuldas em aplicar a relaxação Lagrangiana a problemas não convexos são discutidos e como podem ser solucionados caso o subproblema dual seja substituído por uma relaxação não convexa do mesmo. Este método Lagrangiano modificado é comparado com resolvedores globais comerciais e resolvedores de código livre. O método proposto convergiu em 35 das 36 instâncias testadas, enquanto o Baron, um dos resolvedores que obteve os melhores resultados, conseguiu convergir apenas para 4 das 36 instâncias. Adicionalmente, mesmo para a única instância que nosso método não conseguiu resolver, ele obteve um gap relativo de menos de 1 por cento, enquanto o Baron atingiu um gap entre 10 por cento e 30 por cento para a maioria das instâncias que o mesmo não convergiu. / [en] This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming. First, relaxations for quadratic programming and related problem classes are reviewed. Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables. Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations. This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances. The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36. Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1 percent in all instances, while Baron achieved relative gaps between 10 percent and 30 percent in most of them.