Дисертації з теми "Optimization nonlinear resource allocation problems"

Les problèmes d’optimisation combinatoire sont généralement réputés NP-difficiles, donc il n’y a pas d’algorithmes efficaces pour les résoudre. Afin de trouver des solutions optimales locales ou réalisables, on utilise souvent des heuristiques ou des algorithmes approchés. Les dernières décennies ont vu naitre des méthodes approchées connues sous le nom de métaheuristiques, et qui permettent de trouver une solution approchées. Cette thèse propose de résoudre des problèmes d’optimisation déterministe et stochastique à l’aide de métaheuristiques. Nous avons particulièrement étudié la méthode de voisinage variable connue sous le nom de VNS. Nous avons choisi cet algorithme pour résoudre nos problèmes d’optimisation dans la mesure où VNS permet de trouver des solutions de bonne qualité dans un temps CPU raisonnable. Le premier problème que nous avons étudié dans le cadre de cette thèse est le problème déterministe de largeur de bande de matrices creuses. Il s’agit d’un problème combinatoire difficile, notre VNS a permis de trouver des solutions comparables à celles de la littérature en termes de qualité des résultats mais avec temps de calcul plus compétitif. Nous nous sommes intéressés dans un deuxième temps aux problèmes de réseaux mobiles appelés OFDMA-TDMA. Nous avons étudié le problème d’affectation de ressources dans ce type de réseaux, nous avons proposé deux modèles : Le premier modèle est un modèle déterministe qui permet de maximiser la bande passante du canal pour un réseau OFDMA à débit monodirectionnel appelé Uplink sous contraintes d’énergie utilisée par les utilisateurs et des contraintes d’affectation de porteuses. Pour ce problème, VNS donne de très bons résultats et des bornes de bonne qualité. Le deuxième modèle est un problème stochastique de réseaux OFDMA d’affectation de ressources multi-cellules. Pour résoudre ce problème, on utilise le problème déterministe équivalent auquel on applique la méthode VNS qui dans ce cas permet de trouver des solutions avec un saut de dualité très faible. Les problèmes d’allocation de ressources aussi bien dans les réseaux OFDMA ou dans d’autres domaines peuvent aussi être modélisés sous forme de problèmes d’optimisation bi-niveaux appelés aussi problèmes d’optimisation hiérarchique. Le dernier problème étudié dans le cadre de cette thèse porte sur les problèmes bi-niveaux stochastiques. Pour résoudre le problème lié à l’incertitude dans ce problème, nous avons utilisé l’optimisation robuste plus précisément l’approche appelée « distributionnellement robuste ». Cette approche donne de très bons résultats légèrement conservateurs notamment lorsque le nombre de variables du leader est très supérieur à celui du suiveur. Nos expérimentations ont confirmé l’efficacité de nos méthodes pour l’ensemble des problèmes étudiés
Combinatorial optimization problems are generally NP-hard problems, so they can only rely on heuristic or approximation algorithms to find a local optimum or a feasible solution. During the last decades, more general solving techniques have been proposed, namely metaheuristics which can be applied to many types of combinatorial optimization problems. This PhD thesis proposed to solve the deterministic and stochastic optimization problems with metaheuristics. We studied especially Variable Neighborhood Search (VNS) and choose this algorithm to solve our optimization problems since it is able to find satisfying approximated optimal solutions within a reasonable computation time. Our thesis starts with a relatively simple deterministic combinatorial optimization problem: Bandwidth Minimization Problem. The proposed VNS procedure offers an advantage in terms of CPU time compared to the literature. Then, we focus on resource allocation problems in OFDMA systems, and present two models. The first model aims at maximizing the total bandwidth channel capacity of an uplink OFDMA-TDMA network subject to user power and subcarrier assignment constraints while simultaneously scheduling users in time. For this problem, VNS gives tight bounds. The second model is stochastic resource allocation model for uplink wireless multi-cell OFDMA Networks. After transforming the original model into a deterministic one, the proposed VNS is applied on the deterministic model, and find near optimal solutions. Subsequently, several problems either in OFDMA systems or in many other topics in resource allocation can be modeled as hierarchy problems, e.g., bi-level optimization problems. Thus, we also study stochastic bi-level optimization problems, and use robust optimization framework to deal with uncertainty. The distributionally robust approach can obtain slight conservative solutions when the number of binary variables in the upper level is larger than the number of variables in the lower level. Our numerical results for all the problems studied in this thesis show the performance of our approaches

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1990.
Includes bibliographical references (leaves 213-214).
by Patrick Ahamad Hosein.
Ph.D.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.03 – системи та процеси керування – Національний технічний університет "Харківський політехнічний інститут", Харків 2018. Дисертаційну роботу присвячено вирішенню важливої та актуальної проблеми наукового обґрунтування і розробки комплексу моделей і методів оцінки, прогнозування та управління стратегічною діяльністю підприємства в умовах невизначеності. Розроблено моделі та методи оцінки і прогнозування стану об'єктів в умовах невизначеності з великим числом можливих станів і великим числом нечітко заданих факторів. Сформульовано і реалізовано концепцію системного стратегічного фінансового планування, що забезпечує комплексне рішення приватних задач стратегічного фінансового планування та управління станом підприємства з урахуванням їх взаємозалежності і взаємозв'язку. Запропоновано економіко-математичні моделі вибору стратегічних напрямків діяльності підприємства, що дозволило врахувати відмінності в рентабельності, рівнях ризику, розмірах розміщеного капіталу. Розроблено моделі та методи управління розподілом активів підприємства по стратегічних напрямках діяльності для кожної зі стадій багатокрокового управління інвестиційним портфелем підприємства з урахуванням відмінностей їх рентабельності та рівня ризику. Обґрунтовано комплекс математичних моделей і методів системного вирішення сукупності оптимізаційних задач вибору проекту плану матеріально-технічного розвитку з урахуванням обсягу вкладених коштів, рівня позикових коштів і леверидж-ефекту, що виникає при цьому. Розроблено моделі та методи розв'язання задач управління інвестиційним портфелем, що враховують невизначеність і ризик при оцінюванні стану зовнішнього середовища, а також рівня можливого прибутку від діяльності підприємства. Розглянуто та удосконалено моделі динаміки вартості активів в умовах ризику і невизначеності. Запропоновано математичну модель марківської динаміки вартості у марківському зовнішньому середовищі.
Thesis for the degree of Doctor of Engineering in specialty 05.13.03 – systems and management processes. – National Technical University "Kharkov Polytechnic Institute", Kharkov, 2018. The thesis is devoted to the solution of an important and actual problem of the scientific substantiation and development of a complex of models and methods for assessing, forecasting and managing the strategic activity of an enterprise under uncertainty. Models and methods for estimating and predicting the state of objects under conditions of uncertainty with a large number of possible states and a large number of fuzzy factors are developed. The concept of strategic financial planning has been formulated and implemented, providing a comprehensive solution of particular problems of strategic financial planning and management of the enterprise condition taking into account their interdependence and interconnection. Economic and mathematical models for choosing strategic directions of the enterprise's activities were proposed, which allowed taking into account differences in profitability, risk levels, and the size of the allocated capital. The models and methods of managing the distribution of the company's assets by strategic lines of activity for each of the stages of multi-step management of the enterprise's investment portfolio, taking into account the differences in their profitability and the level of risk are developed. The complex of mathematical models and methods of the system solution of a set of optimization tasks for the selection of the draft plan for material and technical development is substantiated, taking into account the amount of funds invested, the level of borrowed funds and the resulting leverage effect. Models and methods for solving investment portfolio management problems have been developed, taking into account uncertainty and risk in assessing the state of the external environment, as well as the level of possible profit from the activities of the enterprise. Models of the dynamics of the value of assets under risk and uncertainty are reviewed and improved. A mathematical model of the Markovian value dynamics in Markov's environment is proposed.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.03 – системи та процеси керування – Національний технічний університет "Харківський політехнічний інститут", Харків 2018. Дисертаційну роботу присвячено вирішенню важливої та актуальної проблеми наукового обґрунтування і розробки комплексу моделей і методів оцінки, прогнозування та управління стратегічною діяльністю підприємства в умовах невизначеності. Розроблено моделі та методи оцінки і прогнозування стану об'єктів в умовах невизначеності з великим числом можливих станів і великим числом нечітко заданих факторів. Сформульовано і реалізовано концепцію системного стратегічного фінансового планування, що забезпечує комплексне рішення приватних задач стратегічного фінансового планування та управління станом підприємства з урахуванням їх взаємозалежності і взаємозв'язку. Запропоновано економіко-математичні моделі вибору стратегічних напрямків діяльності підприємства, що дозволило врахувати відмінності в рентабельності, рівнях ризику, розмірах розміщеного капіталу. Розроблено моделі та методи управління розподілом активів підприємства по стратегічних напрямках діяльності для кожної зі стадій багатокрокового управління інвестиційним портфелем підприємства з урахуванням відмінностей їх рентабельності та рівня ризику. Обґрунтовано комплекс математичних моделей і методів системного вирішення сукупності оптимізаційних задач вибору проекту плану матеріально-технічного розвитку з урахуванням обсягу вкладених коштів, рівня позикових коштів і леверидж-ефекту, що виникає при цьому. Розроблено моделі та методи розв'язання задач управління інвестиційним портфелем, що враховують невизначеність і ризик при оцінюванні стану зовнішнього середовища, а також рівня можливого прибутку від діяльності підприємства. Розглянуто та удосконалено моделі динаміки вартості активів в умовах ризику і невизначеності. Запропоновано математичну модель марківської динаміки вартості у марківському зовнішньому середовищі.
Thesis for the degree of Doctor of Engineering in specialty 05.13.03 – systems and management processes. – National Technical University "Kharkov Polytechnic Institute", Kharkov, 2018. The thesis is devoted to the solution of an important and actual problem of the scientific substantiation and development of a complex of models and methods for assessing, forecasting and managing the strategic activity of an enterprise under uncertainty. Models and methods for estimating and predicting the state of objects under conditions of uncertainty with a large number of possible states and a large number of fuzzy factors are developed. The concept of strategic financial planning has been formulated and implemented, providing a comprehensive solution of particular problems of strategic financial planning and management of the enterprise condition taking into account their interdependence and interconnection. Economic and mathematical models for choosing strategic directions of the enterprise's activities were proposed, which allowed taking into account differences in profitability, risk levels, and the size of the allocated capital. The models and methods of managing the distribution of the company's assets by strategic lines of activity for each of the stages of multi-step management of the enterprise's investment portfolio, taking into account the differences in their profitability and the level of risk are developed. The complex of mathematical models and methods of the system solution of a set of optimization tasks for the selection of the draft plan for material and technical development is substantiated, taking into account the amount of funds invested, the level of borrowed funds and the resulting leverage effect. Models and methods for solving investment portfolio management problems have been developed, taking into account uncertainty and risk in assessing the state of the external environment, as well as the level of possible profit from the activities of the enterprise. Models of the dynamics of the value of assets under risk and uncertainty are reviewed and improved. A mathematical model of the Markovian value dynamics in Markov's environment is proposed.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007.
Includes bibliographical references (p. 129-131).
We consider large-scale, network-based, resource allocation problems under uncertainty, with specific focus on the class of problems referred to as multi-commodity flow problems with time-windows. These problems are at the core of many network-based resource allocation problems. Inherent data uncertainty in the problem guarantees that deterministic optimal solutions are rarely, if ever, executed. Our work examines methods of proactive planning, that is, robust plan generation to protect against future uncertainty. By modeling uncertainties in data corresponding to service times, resource availability, supplies and demands, we can generate solutions that are more robust operationally, that is, more likely to be executed or easier to repair when disrupted. The challenges are the following: approaches to achieve robustness 1) can be extremely problem-specific and not general; 2) suffer from issues of tractability; or 3) have unrealistic data requirements. We propose in this work a modeling and algorithmic framework that addresses the above challenges.
(cont.) Our modeling framework involves a decomposition scheme that separates problems involving multi-commodity flows with time-windows into routing (that is, a routing master problem) and scheduling modules (that is, a scheduling sub-problem), and uses an iterative scheme to provide feedback between the two modules, both of which are more tractable than the integrated model. The master problem has the structure of a multi-commodity flow problem and the sub-problem is a set of network flow problems. This decomposition allows us to capture uncertainty while maintaining tractability. Uncertainty is captured in part by the master problem and in part by the sub-problem. In addition to solving problems under uncertainty, our decomposition scheme can also be used to solve large-scale resource allocation problems without uncertainty. As proof-of-concept, we apply our approach to a vehicle routing and scheduling problem and compare its solutions to those of other robust optimization approaches. Finally, we propose a framework to extend our robust, decomposition approach to the more complex problem of network design.
by Lavanya Marla.
S.M.

In this thesis we deal with two problems of resource allocation solved through a Mixed-Integer Linear Programming approach and a Mixed-Integer Nonlinear Chance Constraint Programming approach. In the first part we propose a framework to model general guillotine restrictions in two dimensional cutting problems formulated as Mixed-Integer Linear Programs (MILP). The modeling framework requires a pseudo-polynomial number of variables and constraints, which can be effectively enumerated for medium-size instances. Our modeling of general guillotine cuts is the first one that, once it is implemented within a state of-the-art MIP solver, can tackle instances of challenging size. Our objective is to propose a way of modeling general guillotine cuts via Mixed Integer Linear Programs (MILP), i.e., we do not limit the number of stages (restriction (ii)), nor impose the cuts to be restricted (restriction (iii)). We only ask the cuts to be guillotine ones (restriction (i)). We mainly concentrate our analysis on the Guillotine Two Dimensional Knapsack Problem (G2KP), for which a model, and an exact procedure able to significantly improve the computational performance, are given. In the second part we present a Branch-and-Cut algorithm for a class of Nonlinear Chance Constrained Mathematical Optimization Problems with a finite number of scenarios. This class corresponds to the problems that can be reformulated as Deterministic Convex Mixed-Integer Nonlinear Programming problems, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows. We apply the Branch-and-Cut algorithm to the Mid-Term Hydro Scheduling Problem, for which we propose a chance-constrained formulation. A computational study using data from ten hydro plants in Greece shows that the proposed methodology solves instances orders of magnitude faster than applying a general-purpose solver for Convex Mixed-Integer Nonlinear Problems to the deterministic reformulation, and scales much better with the number of scenarios.

Since its inception, cognitive radio (CR) has quickly been accepted as the enabling radio technology for next-generation wireless communications. A CR promises unprecedented flexibility in radio functionalities via programmability at the lowest layer, which was once done in hardware. Due to its spectrum sensing, learning, and adaptation capabilities, CR is able to address the heart of the problem associated with spectrum scarcity (via dynamic spectrum access (DSA)) and interoperability (via channel switching). It is envisioned that CR will be employed as a general radio platform upon which numerous wireless applications can be implemented. For both theoretical and practical purposes, it is important for network researchers to model a cognitive radio ad hoc network (CRN) and optimize its performance. Such efforts are important not only for theoretical understanding, but also in that such results can be used as benchmarks for the design of distributed algorithms and protocols. However, due to some unique characteristics associated with CRNs, existing analytical techniques may not be applied directly. As a result, new theoretical results, along with new mathematical techniques, need to be developed. In this thesis, we focus on modeling and optimization of CRNs. In particular, we will study multicast communications in CRN and MIMO-empowered CRN, which we describe as follows. An important service that must be supported by CRNs is multicast. Although there are a lot of research on multicast in ad hoc networks, those results cannot be applied to a CRN, because of the complexity associated with a CR node (e.g., multiple available frequency bands, difference in available bands from neighboring nodes). In addition, a single-layer approach (e.g., multicast routing) is overly simplistic when resource optimization (i.e., minimizing network resource) is the main objective. For this purpose, a cross-layer approach is usually necessary, which should include joint consideration of multiple lower layers, in addition to network layer. However, such a joint formulation is usually highly complex and difficult. In this thesis, we aim to develop some novel algorithms that provide near-optimal solutions. Our goal is to minimize the required network-wide resource to support a set of multicast sessions, with a certain bit rate for each multicast session. The unique characteristics associated with CR and distinguish this problem from existing multicast research for ad hoc networks. In this work, we formulate this problem via a cross-layer approach with joint consideration of scheduling and routing. Although the problem formulation is in the form of mixed integer linear program (MILP), we are successful in developing a polynomial time algorithm that offers highly competitive solution. The main ideas of the algorithm include identification of key integer variables, fixing these variables via a series of relaxed linear program (LP), and tying up such integer fixing with a bottom-up tree construction. By comparing with a lower bound, we find that the proposed algorithm can provide a solution that is very close to the optimum. In parallel to the development of CR for DSA, multiple-input multiple-output (MIMO) has widely been accepted and now implemented in commercial wireless products to increase capacity. The goal of MIMO and how it operates are largely independent and orthogonal to CR. Instead of exploiting idle channels for wireless communications, MIMO attempts to increase capacity within the same channel via space-time processing. Assuming that CR and MIMO will ultimately marry each other and offer the ultimate flexibility in DSA and spectrum efficiency, we would like to inquire the potential capacity gain in this marriage. In particular, we are interested in how such marriage will affect the capacity of a user communication session in a multi-hop CRN. We explore MIMO-empowered CR network, which we call CRN^MIMO, to achieve ultimate flexibility in DSA and spectrum efficiency. Given that CR and MIMO handle interference at different levels (across channels vs. within a channel), we are interested in how joint optimization of both will maximize user capacity in a multi-hop network. To answer this question, we develop a tractable mathematical model for CRN^MIMO, which captures the essence of channel assignment (for CR) and degree-of-freedom (DoF) allocation (for MIMO). Based on this mathematical model, we use numerical results to show how channel assignment in CRN and DoF allocation in MIMO can be jointly optimized to maximize capacity. More important, for a CRN^MIMO with A_MIMO antennas at each node, we show that joint optimization of CR and MIMO offers more than A_MIMO-fold capacity increase than a CRN with only a single antenna at each node.
Master of Science

Le domaine avionique a été transformé par l'apparition des architectures modulaires intégrées (IMA). Celles-ci définissent un support d'exécution et de communication standard et mutualisé afin de réduire la complexité de l'architecture physique. Cependant, du fait du partage des ressources, cette démarche introduit une plus grande complexité lors de la conception et de l'intégration des applications ce qui implique d'assister les concepteurs avec des outils dédiés. La présente thèse contribue à cet effort en se focalisant sur deux problèmes d'allocation de ressources : i) le problème de l'ordonnancement multiprocesseur de tâches strictement périodiques et ii) le problème du routage des messages échangés entre les fonctions avioniques. Le premier problème a été formalisé sous la forme d'un programme linéaire en nombres entiers afin de garantir un potentiel maximum d'évolution sur les durées d'exécutions des traitements. L'inefficacité d'une approche exacte pour des instances de grande taille, nous a conduit à développer une heuristique originale s'inspirant de la théorie des jeux couplée avec un algorithme multi-start. Le routage est formalisé sous la forme d'un problème d'optimisation sur la charge maximum des liens. Deux propositions sont faites pour le résoudre, l'une, exacte, est basée sur une formulation nœud-lien, et la seconde est une heuristique à deux niveaux basé sur une formulation lien-chemin. Mots-Clés en français : ordonnancement temps-réel, optimisation, systèmes avioniques, architectures modulaires intégrées, tâches strictement périodique, théorie de jeux, routage des liens virtuels

This dissertation addresses five fundamental resource allocation problems on networks, all of which have applications to support Homeland Security or industry challenges. In the first application, we model and solve the strategic problem of minimizing the expected loss inflicted by a hostile terrorist organization. An appropriate allocation of certain capability-related, intent-related, vulnerability-related, and consequence-related resources is used to reduce the probabilities of success in the respective attack-related actions, and to ameliorate losses in case of a successful attack. Given the disparate nature of prioritizing capital and material investments by federal, state, local, and private agencies to combat terrorism, our model and accompanying solution procedure represent an innovative, comprehensive, and quantitative approach to coordinate resource allocations from various agencies across the breadth of domains that deal with preventing attacks and mitigating their consequences. Adopting a nested event tree optimization framework, we present a novel formulation for the problem as a specially structured nonconvex factorable program, and develop two branch-and-bound schemes based respectively on utilizing a convex nonlinear relaxation and a linear outer-approximation, both of which are proven to converge to a global optimal solution. We also investigate a fundamental special-case variant for each of these schemes, and design an alternative direct mixed-integer programming model representation for this scenario. Several range reduction, partitioning, and branching strategies are proposed, and extensive computational results are presented to study the efficacy of different compositions of these algorithmic ingredients, including comparisons with the commercial software BARON. The developed set of algorithmic implementation strategies and enhancements are shown to outperform BARON over a set of simulated test instances, where the best proposed methodology produces an average optimality gap of 0.35% (compared to 4.29% for BARON) and reduces the required computational effort by a factor of 33. A sensitivity analysis is also conducted to explore the effect of certain key model parameters, whereupon we demonstrate that the prescribed algorithm can attain significantly tighter optimality gaps with only a near-linear corresponding increase in computational effort. In addition to enabling effective comprehensive resource allocations, this research permits coordinating agencies to conduct quantitative what-if studies on the impact of alternative resourcing priorities. The second application is motivated by the author's experience with the U.S. Army during a tour in Iraq, during which combined operations involving U.S. Army, Iraqi Army, and Iraqi Police forces sought to interdict the transport of selected materials used for the manufacture of specialized types of Improvised Explosive Devices, as well as to interdict the distribution of assembled devices to operatives in the field. In this application, we model and solve the problem of minimizing the maximum flow through a network from a given source node to a terminus node, integrating different forms of superadditive synergy with respect to the effect of resources applied to the arcs in the network. Herein, the superadditive synergy reflects the additional effectiveness of forces conducting combined operations, vis-à-vis unilateral efforts. We examine linear, concave, and general nonconcave superadditive synergistic relationships between resources, and accordingly develop and test effective solution procedures for the underlying nonlinear programs. For the linear case, we formulate an alternative model representation via Fourier-Motzkin elimination that reduces average computational effort by over 40% on a set of randomly generated test instances. This test is followed by extensive analyses of instance parameters to determine their effect on the levels of synergy attained using different specified metrics. For the case of concave synergy relationships, which yields a convex program, we design an inner-linearization procedure that attains solutions on average within 3% of optimality with a reduction in computational effort by a factor of 18 in comparison with the commercial codes SBB and BARON for small- and medium-sized problems; and outperforms these softwares on large-sized problems, where both solvers failed to attain an optimal solution (and often failed to detect a feasible solution) within 1800 CPU seconds. Examining a general nonlinear synergy relationship, we develop solution methods based on outer-linearizations, inner-linearizations, and mixed-integer approximations, and compare these against the commercial software BARON. Considering increased granularities for the outer-linearization and mixed-integer approximations, as well as different implementation variants for both these approaches, we conduct extensive computational experiments to reveal that, whereas both these techniques perform comparably with respect to BARON on small-sized problems, they significantly improve upon the performance for medium- and large-sized problems. Our superlative procedure reduces the computational effort by a factor of 461 for the subset of test problems for which the commercial global optimization software BARON could identify a feasible solution, while also achieving solutions of objective value 0.20% better than BARON. The third application is likewise motivated by the author's military experience in Iraq, both from several instances involving coalition forces attempting to interdict the transport of a kidnapping victim by a sectarian militia as well as, from the opposite perspective, instances involving coalition forces transporting detainees between interment facilities. For this application, we examine the network interdiction problem of minimizing the maximum probability of evasion by an entity traversing a network from a given source to a designated terminus, while incorporating novel forms of superadditive synergy between resources applied to arcs in the network. Our formulations examine either linear or concave (nonlinear) synergy relationships. Conformant with military strategies that frequently involve a combination of overt and covert operations to achieve an operational objective, we also propose an alternative model for sequential overt and covert deployment of subsets of interdiction resources, and conduct theoretical as well as empirical comparative analyses between models for purely overt (with or without synergy) and composite overt-covert strategies to provide insights into absolute and relative threshold criteria for recommended resource utilization. In contrast to existing static models, in a fourth application, we present a novel dynamic network interdiction model that improves realism by accounting for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. We further enhance the realism of our model by considering a multi-component objective function, wherein the interdictor seeks to minimize the maximum value of a regret function that consists of the evader's net flow from the source to the terminus; the interdictor's procurement, deployment, and redeployment costs; and penalties incurred by the evader for misperceptions as to the interdicted state of the network. For the resulting minimax model, we use duality to develop a reformulation that facilitates a direct solution procedure using the commercial software BARON, and examine certain related stability and convergence issues. We demonstrate cases for convergence to a stable equilibrium of strategies for problem structures having a unique solution to minimize the maximum evader flow, as well as convergence to a region of bounded oscillation for structures yielding alternative interdictor strategies that minimize the maximum evader flow. We also provide insights into the computational performance of BARON for these two problem structures, yielding useful guidelines for other research involving similar non-convex optimization problems. For the fifth application, we examine the problem of apportioning railcars to car manufacturers and railroads participating in a pooling agreement for shipping automobiles, given a dynamically determined total fleet size. This study is motivated by the existence of such a consortium of automobile manufacturers and railroads, for which the collaborative fleet sizing and efforts to equitably allocate railcars amongst the participants are currently orchestrated by the \textit{TTX Company} in Chicago, Illinois. In our study, we first demonstrate potential inequities in the industry standard resulting either from failing to address disconnected transportation network components separately, or from utilizing the current manufacturer allocation technique that is based on average nodal empty transit time estimates. We next propose and illustrate four alternative schemes to apportion railcars to manufacturers, respectively based on total transit time that accounts for queuing; two marginal cost-induced methods; and a Shapley value approach. We also provide a game-theoretic insight into the existing procedure for apportioning railcars to railroads, and develop an alternative railroad allocation scheme based on capital plus operating costs. Extensive computational results are presented for the ten combinations of current and proposed allocation techniques for automobile manufacturers and railroads, using realistic instances derived from representative data of the current business environment. We conclude with recommendations for adopting an appropriate apportionment methodology for implementation by the industry.
Ph. D.

Les travaux de thèse présentés s’intéressent à l’optimisation des systèmes hospitaliers. Une solution existante est la mutualisation de ressources au sein d’un même territoire. Cela peut passer par différentes formes de coopération dont la Communauté Hospitalière de Territoire. Différents problèmes sont définis en fonction du niveau de décision : stratégique, tactique ou opérationnel ; et du niveau de modélisation : macroscopique, mesoscopique et microscopique. Des problèmes de dimensionnement, de planification et d’ordonnancement peuvent être considérés. Nous définissons notamment le problème de planification d’activités avec affectation de ressources. Plusieurs cas sont dissociés : soit les ressources humaines sont à capacité infinie, soit elles sont à capacité limitée et leur affectation sur site est une donnée, soit elles sont à capacité limitée et leur affectation sur site est une variable. Ces problèmes sont spécifiés et formalisés mathématiquement. Tous ces problèmes sont comparés à un problème de bin packing : le problème du bin packing de base pour le problème où les ressources humaines sont à capacité infinie, le problème du bin packing avec interdépendances dans les deux autres cas. Le problème du bin packing avec incompatibilités est ainsi défini. De nombreuses méthodes de résolution ont déjà été proposées pour le problème du bin packing. Nous faisons plusieurs propositions dont un couplage hiérarchique entre une heuristique et une métaheuristique. Des métaheuristiques basées individu et une métaheuristique basée population, l’optimisation par essaim particulaire, sont utilisées. Cette proposition nécessite un nouveau codage inspiré des problèmes de permutation d’ordonnancement. Cette méthode donne de très bons résultats sur les instances du problème du bin packing. Elle est simple à appliquer : elle couple des méthodes déjà connues. Grâce au couplage proposé, les nouvelles contraintes à considérer nécessitent d’être intégrées uniquement au niveau de l’heuristique. Le fonctionnement de la métaheuristique reste le même. Ainsi, notre méthode est facilement adaptable au problème de planification d’activités avec affectation de ressources. Pour les instances de grande taille, le solveur utilisé comme référence ne donne qu’un intervalle de solutions. Les résultats de notre méthode sont une fois encore très prometteurs : les solutions obtenues sont meilleures que la borne supérieure retournée par le solveur. Il est envisageable d’adapter notre méthode sur d’autres problèmes plus complexes par intégration dans l’heuristique des nouvelles contraintes à considérer. Il serait notamment intéressant de tester ces méthodes sur de réelles instances hospitalières afin d’évaluer leur portée
The presented work is about optimization of the hospital system. An existing solution is the pooling of resources within the same territory. This may involve different forms of cooperation between several hospitals. Various problems are defined at the decision level : strategic, tactical or operational ; and at the modeling level : macroscopic, mesoscopic and microscopic. Problems of sizing, planning and scheduling may be considered. We define the problem of activities planning with resource allocation. Several cases are dissociated : either human resources are under infinite capacity, or they are under limited capacity and their assignment on a place is given, or they are under limited capacity and their assignment is a variable. These problems are specified and mathematically formalized. All thes problems are compared to a bin packing problem : the classical problem of bin packing is used for the problem where human resources are under infinite capacity, the bin packing problem with interdependencies is used in the two other cases. The bin packing problem with incompatibilities is defined. Many resolution methods have been proposed for the bin packing problem. We make several propositions including a hierarchical coupling between heuristic and metaheuristic. Single based metaheuristics and a population based metaheuristic, the particle swarm optimization, are used. This proposition requires a new encoding inspired by permutation problems. This method gives very good results to solve instances of the bin packing problem. It is easy to apply : it combines already known methods. With the proposed coupling, the new constraints to be considered need to be integrated only on the heuristic level. The running of the metaheuristic is the same. Thus, our method is easily adaptable to the problem of activities planning with resource allocation. For big instances, the solver used as a reference returns only an interval of solutions. The results of our method are once again very promising : the obtained solutions are better than the upper limit returned by the solver. It is possible to adapt our method on more complex issues through integration into the heuristic of the new constraints to consider. It would be particularly interesting to test these methods on real hospital authorities to assess their significance

碩士
國立暨南國際大學
資訊管理學系
93
Resource allocation problem (RAP) has lots of applications, many researchers devote their efforts in developing new methods for tackling this problem. In RAP, resource is limited, the objective is to optimize the resource allocation while satisfying all resource constraints simultaneously. There are two main types of the resource allocation problems, one is called the single-objective resource allocation problem, which makes the resource allocation to optimize a single objective function. The other is called multi-objective resource allocation problem, which makes the resource allocation to optimize multiple objective functions and this problem has caused much attention from researchers and practitioners. The difference between the two problems is that multi-objective resource allocation problem seeks to optimize multi objectives and there always exist conflicts between these objectives. For example, in manufacturing process, we hope to attain more benefit while reducing the cost. Therefore, we must design an integrated fitness evaluation function to measure the goodness of candidate solutions. Most existing methods for solving RAP are mathematical programming approaches, such as dynamic programming, linear programming, and branch and bound. However, as the numbers of variables and constraints increase, the computational time used by mathematical programming approaches will grow dramatically. As such, we propose new techniques based on swarm intelligence, including ant colony optimal algorithm and particle swarm optimal algorithm to find approximate solutions with reasonable times. We also embed other heuristics to expedite the convergence of the proposed algorithms. On the other hand, weighted-sum approach is the most broadly used method to solve the multi-objective resource allocation problem; however, it is prone to be subjective. Therefore, we design Pareto-based swarm intelligence algorithms to evaluate the fitness of each solution considering all problem objectives simultaneously, and we seek to find as many Pareto-optimal solutions as possible. keyword：ant colony optimization, genetic algorithm, particle swarm optimization, resource allocation problem, mathematical programming, Pareto-optimal

碩士
國立暨南國際大學
管理學院經營管理碩士學位學程碩士在職專班
97
Abstract This study focuses on the supply chain system that typically resides a number of facilities on different locations and assigns them to the customers for retrieving resources. The determined assignment has to assure that the demands from customers are satisfied by the facility services. This problem belongs to FLRAP (facility location and resource allocation problem) field in operational research. Due to the efforts devoted by many researchers, more practical variations of the FLRAP have been derived and these formulations fit more into the real world situations. This study will introduce different mathematical models and their related problems. Besides local search and algorithm, it also includes the meta-heuristic algorithm. This study will introduce different mathematical formulations of FLRAP and the associated solution methods including classical local search and recently proposed metaheuristics. We choose particle swarm optimization algorithm to tackle FLRAP; that is, finding the optimal resource allocation and transportation routes such that the incurred cost is minimized. Keywords: particle swarm optimization, resource allocation, operational research, metaheuristic

abstract: We live in a networked world with a multitude of networks, such as communication networks, electric power grid, transportation networks and water distribution networks, all around us. In addition to such physical (infrastructure) networks, recent years have seen tremendous proliferation of social networks, such as Facebook, Twitter, LinkedIn, Instagram, Google+ and others. These powerful social networks are not only used for harnessing revenue from the infrastructure networks, but are also increasingly being used as “non-conventional sensors” for monitoring the infrastructure networks. Accordingly, nowadays, analyses of social and infrastructure networks go hand-in-hand. This dissertation studies resource allocation problems encountered in this set of diverse, heterogeneous, and interdependent networks. Three problems studied in this dissertation are encountered in the physical network domain while the three other problems studied are encountered in the social network domain. The first problem from the infrastructure network domain relates to distributed files storage scheme with a goal of enhancing robustness of data storage by making it tolerant against large scale geographically-correlated failures. The second problem relates to placement of relay nodes in a deployment area with multiple sensor nodes with a goal of augmenting connectivity of the resulting network, while staying within the budget specifying the maximum number of relay nodes that can be deployed. The third problem studied in this dissertation relates to complex interdependencies that exist between infrastructure networks, such as power grid and communication network. The progressive recovery problem in an interdependent network is studied whose goal is to maximize system utility over the time when recovery process of failed entities takes place in a sequential manner. The three problems studied from the social network domain relate to influence propagation in adversarial environment and political sentiment assessment in various states in a country with a goal of creation of a “political heat map” of the country. In the first problem of the influence propagation domain, the goal of the second player is to restrict the influence of the first player, while in the second problem the goal of the second player is to have a larger market share with least amount of initial investment.
Dissertation/Thesis
Doctoral Dissertation Computer Science 2016

Text in Afikaans
In this thesis contributions to the solution of the generalised knapsack problem are given and discussed. Attention is given to problems with functions that are calculable but not necessarily in a closed form. Algorithms and test problems can be used for problems with closed-form functions as well. The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be investigated and good test problems must be designed. A measure of convexity for convex functions is developed and adapted for concave functions. A test problem generator makes use of this measure of convexity to create challenging test problems for the concave, convex and mixed knapsack problems. Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped as well as the generalised knapsack problem. The in uence of the size of the problem and the funding ratio on the speed and the accuracy of the algorithms are investigated. When applicable, the in uence of the interval length ratio and the ratio of concave functions to the total number of functions is also investigated. The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf- cient conditions for optimality for the convex knapsack problem with xed interval lengths is given and proved. For the general convex knapsack problem, the key theorem, which contains the stronger necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well. The exact search-lambda algorithm is developed for the concave knapsack problem with functions that are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this heuristic as well as on the S-shaped and generalised knapsack problems.
Mathematical Sciences
D. Phil. (Operasionele Navorsing)