Academic literature on the topic 'Optimization nonlinear resource allocation problems'

In this paper, we study the resource allocation for simultaneous wireless information and power transfer (SWIPT) systems with the nonlinear energy harvesting (EH) model. A simple optimal resource allocation scheme based on the time slot switching is proposed to maximize the average achievable rate for the SWIPT systems. The optimal resource allocation is formulated as a nonconvex optimization problem, which is the combination of a series of nonconvex problems due to the binary feature of the time slot-switching ratio. The optimal problem is then solved by using the time-sharing strong duality theorem and Lagrange dual method. It is found that with the proposed optimal resource allocation scheme, the receiver should perform EH in the region of medium signal-to-noise ratio (SNR), whereas switching to information decoding (ID) is performed when the SNR is larger or smaller. The proposed resource allocation scheme is compared with the traditional time switching (TS) resource allocation scheme for the SWIPT systems with the nonlinear EH model. Numerical results show that the proposed resource allocation scheme significantly improves the system performance in energy efficiency.

Aim. The presented study aims to address the issues of parameter estimation in the problems of optimal resources allocation for the previously introduced competition indicator; to analyze the influence of dimensionality, resource constraints, and other factors on the competition indicator; to exemplify the relationship between the indicator and the extremum of the objective function, constraints, and dual estimates.Tasks. The authors consider cases when the competition indicator captures a change in the initial data that cannot be estimated on the basis of traditional indicators of analysis and estimates: the maximum of the objective function, the optimal solution, Lagrange multipliers, or dual variables; determine the relationship between the competition indicator and the optimum of the objective function and dual variables through examples and in general; show that the analysis of the results of solving the problem becomes more capacious and informative if the factor of variable “competitiveness” is applied; identify patterns between efficiency, competition, resource constraints, and dual estimates.Methods. The selected competition indicator for optimal resource allocation tasks is based on the concept of “rigorous selection” of competitors applying for resources. The indicators are calculated in full accordance with the known optimality conditions for problems of this class, making it possible to interpret the results of optimization as a measure of competition for resources.Results. The provided examples reflect linear and nonlinear functions as well as the relationship between the competition indicator and dual estimates, resource constraints, and efficiency. It is proved that the competition indicator logically fits into the traditional analysis of the results of solving the problem of linear and nonlinear programming with allowance for duality.Conclusion. The competition indicators considered in the study can be included in the standard analysis for solving the problems of optimal resource allocation, which involves finding an extremum, searching for an optimal plan, analyzing stability, limits, dual estimates, a measure of resource scarcity. As can be seen from the examples, applying the competition indicator to the analysis not only makes the analysis of the results more capacious and informative, but also makes it possible to detect patterns between competition and efficiency, similar to when the removal of barriers and restrictions in the economy leads to its revival, and the reduction of resources causes increased competition.

In cellular networks, device-to-device communications can increase the spectrum efficiency, but some conventional schemes only consider uplink or downlink resource allocation. In this paper, we propose the joint uplink and downlink resource allocation scheme which maximizes the system capacity and guarantees the signal-to-noise-and-interference ratio of both cellular users and device-to-device pairs. The optimization problem is formulated as a mixed integer nonlinear problem that is usually NP hard. To achieve the reasonable resource allocation, the optimization problem is divided into two sub-problems including power allocation and channel assignment. It is proved that the objective function of power control is a convex function, in which the optimal transmission power can be obtained. The Hungarian algorithm is developed to achieve joint uplink and downlink channel assignment. The proposed scheme can improve the system capacity performance and increase the spectrum efficiency. Numerical results reveal that the performance of the proposed scheme of jointly uplink and downlink is better than that of the schemes for independent allocation.

In the hybrid communication scenario of the Heterogeneous Cloud Radio Access Network and Device-to-Device in 5G, spectrum efficiency promotion and the interference controlling caused by spectrum reuse are still challenges. In this article, a novel resource management method, consisting of power and channel allocation, is proposed to solve this problem. An optimization model to maximum the system throughput and spectrum efficiency of the system, which is constrained by Signal to Interference plus Noise Ratio requirements of all users in diverse layers, is established. To solve the non-convex mixed integer nonlinear optimization problem, the optimization model is decomposed into two sub-problems, which are all solvable quasi-convex power allocation and non-convex channel allocation. The first step is to solve a power allocation problem based on solid geometric programming with the vertex search method. Then, a channel allocation constructed by three-dimensional hypergraph matching is established, and the best result of this problem is obtained by a heuristic greed algorithm based on the bipartite conflict graph and µ-claw search. Finally, the simulation results show that the proposed scheme improves the throughput performance at least 6% over other algorithms.

The hierarchical edge-cloud enabled paradigm has recently been proposed to provide abundant resources for 5G wireless networks. However, the computation and communication capabilities are heterogeneous which makes the potential advantages difficult to be fully explored. Besides, previous works on mobile edge computing (MEC) focused on server caching and offloading, ignoring the computational and caching gains brought by the proximity of user equipments (UEs). In this paper, we investigate the computation offloading in a three-tier cache-assisted hierarchical edge-cloud system. In this system, UEs cache tasks and can offload their workloads to edge servers or adjoining UEs by device-to-device (D2D) for collaborative processing. A cost minimization problem is proposed by the tradeoff between service delay and energy consumption. In this problem, the offloading decision, the computational resources and the offloading ratio are jointly optimized in each offloading mode. Then, we formulate this problem as a mixed-integer nonlinear optimization problem (MINLP) which is non-convex. To solve it, we propose a joint computation offloading and resource allocation optimization (JORA) scheme. Primarily, in this scheme, we decompose the original problem into three independent subproblems and analyze their convexity. After that, we transform them into solvable forms (e.g., convex optimization problem or linear optimization problem). Then, an iteration-based algorithm with the Lagrange multiplier method and a distributed joint optimization algorithm with the adoption of game theory are proposed to solve these problems. Finally, the simulation results show the performance of our proposed scheme compared with other existing benchmark schemes.

This paper, which based on the conventional dynamic programming solution , using the method that the decision variables of various stages are fully discrete in their feasible region to solve the optimal target function value under the various state variables. The method can be generic in solving the maximum and minimum objective function value, while avoiding the problem of the different discrete step lengths of the state variables lead to lower the precision of the target value. So, the method will make the solution process of the various stages more specific image, contributing to combining with the practical problems and understanding the connotation of the practical problems (e.g. water resource optimization allocation ).

Power allocation plays a pivotal role in improving the communication performance of interference-limitedwireless network (IWN). However, the optimization of power allocation is usually formulated as a mixed-integernon-linear programming (MINLP) problem, which is hard to solve. Whale optimization algorithm (WOA)has recently gained the attention of the researcher as an efficient method to solve a variety of optimizationproblems. WOA algorithm also has the disadvantages of low convergence accuracy and easy to fall into local optimum.To solve the above problems, we propose Cosine Compound Whale Optimization Algorithm (CCWOA).First of all, its unique cosine nonlinear convergence factor can balance the rate of the whole optimization processand prevent the convergence speed from being too fast. Secondly, the inertia weight and sine vector canincrease the probability of jumping out of the local optimal solution. Finally, the Archimedean spiral can reducethe risk of losing the optimal solution. A representative benchmark function is selected to test the convergencerate of CCWOA algorithm and the optimization performance of jumping out of local optimum. Compared withthe representative algorithms PFP and GAP, the optimization effect of CCWOA is almost consistent with theabove two algorithms, and even exceeds 4% - 6% in numerical value. The advantage of CCWOA is that it haslower algorithm complexity, which has a good advantage when the network computing resources are fixed. Inaddition, the optimization effect of CCWOA is higher than that of WOA, which lays a good foundation for furtherapplication of swarm intelligence optimization algorithm in network resource allocation.

The resource limitation of multi-access edge computing (MEC) is one of the major issues in order to provide low-latency high-reliability computing services for Internet of Things (IoT) devices. Moreover, with the steep rise of task requests from IoT devices, the requirement of computation tasks needs dynamic scalability while using the potential of offloading tasks to mobile volunteer nodes (MVNs). We, therefore, propose a scalable vehicle-assisted MEC (SVMEC) paradigm, which cannot only relieve the resource limitation of MEC but also enhance the scalability of computing services for IoT devices and reduce the cost of using computing resources. In the SVMEC paradigm, a MEC provider can execute its users’ tasks by choosing one of three ways: (i) Do itself on local MEC, (ii) offload to the remote cloud, and (iii) offload to the MVNs. We formulate the problem of joint node selection and resource allocation as a Mixed Integer Nonlinear Programming (MINLP) problem, whose major objective is to minimize the total computation overhead in terms of the weighted-sum of task completion time and monetary cost for using computing resources. In order to solve it, we adopt alternative optimization techniques by decomposing the original problem into two sub-problems: Resource allocation sub-problem and node selection sub-problem. Simulation results demonstrate that our proposed scheme outperforms the existing schemes in terms of the total computation overhead.

The time, quality, and cost are three important but contradictive objectives in a building construction project. It is a tough challenge for project managers to optimize them since they are different parameters. This paper presents a time-cost-quality optimization model that enables managers to optimize multiobjectives. The model is from the project breakdown structure method where task resources in a construction project are divided into a series of activities and further into construction labors, materials, equipment, and administration. The resources utilized in a construction activity would eventually determine its construction time, cost, and quality, and a complex time-cost-quality trade-off model is finally generated based on correlations between construction activities. A genetic algorithm tool is applied in the model to solve the comprehensive nonlinear time-cost-quality problems. Building of a three-storey house is an example to illustrate the implementation of the model, demonstrate its advantages in optimizing trade-off of construction time, cost, and quality, and help make a winning decision in construction practices. The computational time-cost-quality curves in visual graphics from the case study prove traditional cost-time assumptions reasonable and also prove this time-cost-quality trade-off model sophisticated.

In this paper, the maximization of the achievable information rate is proposed for the multi-relay amplify-and-forward cooperative simultaneous wireless information and power transfer communication systems, where the nonlinear characteristic of the energy harvesting (EH) circuits is taken into account for the receivers of the relay nodes. The time switching (TS) and power splitting (PS) schemes are considered for the EH receivers and the achievable rate maximization problems are formulated as convex and non-convex optimization problems, respectively. The optimal TS and PS ratios for the relay nodes along with the maximum achievable rates for the system are obtained, respectively, by solving the optimal problems with efficient algorithms. The asymptotic maximum achievable rates at low and high input signal-to-noise ratios (SNRs) for both the PS and TS schemes are also analyzed. It is demonstrated that the PS scheme is more susceptible to the variation of the relays’ location and the channel parameters than TS scheme, whereas the TS scheme is more susceptible to the mismatch of the resource allocation than PS scheme. Specifically, compared to the linear EH model, the nonlinear EH model achieves significant performance gain for the TS scheme, whereas inconspicuous performance improvement is achieved for the PS scheme.

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<br>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.<br>Includes bibliographical references (leaves 213-214).<br>by Patrick Ahamad Hosein.<br>Ph.D.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.03 – системи та процеси керування – Національний технічний університет "Харківський політехнічний інститут", Харків 2018. Дисертаційну роботу присвячено вирішенню важливої та актуальної проблеми наукового обґрунтування і розробки комплексу моделей і методів оцінки, прогнозування та управління стратегічною діяльністю підприємства в умовах невизначеності. Розроблено моделі та методи оцінки і прогнозування стану об'єктів в умовах невизначеності з великим числом можливих станів і великим числом нечітко заданих факторів. Сформульовано і реалізовано концепцію системного стратегічного фінансового планування, що забезпечує комплексне рішення приватних задач стратегічного фінансового планування та управління станом підприємства з урахуванням їх взаємозалежності і взаємозв'язку. Запропоновано економіко-математичні моделі вибору стратегічних напрямків діяльності підприємства, що дозволило врахувати відмінності в рентабельності, рівнях ризику, розмірах розміщеного капіталу. Розроблено моделі та методи управління розподілом активів підприємства по стратегічних напрямках діяльності для кожної зі стадій багатокрокового управління інвестиційним портфелем підприємства з урахуванням відмінностей їх рентабельності та рівня ризику. Обґрунтовано комплекс математичних моделей і методів системного вирішення сукупності оптимізаційних задач вибору проекту плану матеріально-технічного розвитку з урахуванням обсягу вкладених коштів, рівня позикових коштів і леверидж-ефекту, що виникає при цьому. Розроблено моделі та методи розв'язання задач управління інвестиційним портфелем, що враховують невизначеність і ризик при оцінюванні стану зовнішнього середовища, а також рівня можливого прибутку від діяльності підприємства. Розглянуто та удосконалено моделі динаміки вартості активів в умовах ризику і невизначеності. Запропоновано математичну модель марківської динаміки вартості у марківському зовнішньому середовищі.<br>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. Дисертаційну роботу присвячено вирішенню важливої та актуальної проблеми наукового обґрунтування і розробки комплексу моделей і методів оцінки, прогнозування та управління стратегічною діяльністю підприємства в умовах невизначеності. Розроблено моделі та методи оцінки і прогнозування стану об'єктів в умовах невизначеності з великим числом можливих станів і великим числом нечітко заданих факторів. Сформульовано і реалізовано концепцію системного стратегічного фінансового планування, що забезпечує комплексне рішення приватних задач стратегічного фінансового планування та управління станом підприємства з урахуванням їх взаємозалежності і взаємозв'язку. Запропоновано економіко-математичні моделі вибору стратегічних напрямків діяльності підприємства, що дозволило врахувати відмінності в рентабельності, рівнях ризику, розмірах розміщеного капіталу. Розроблено моделі та методи управління розподілом активів підприємства по стратегічних напрямках діяльності для кожної зі стадій багатокрокового управління інвестиційним портфелем підприємства з урахуванням відмінностей їх рентабельності та рівня ризику. Обґрунтовано комплекс математичних моделей і методів системного вирішення сукупності оптимізаційних задач вибору проекту плану матеріально-технічного розвитку з урахуванням обсягу вкладених коштів, рівня позикових коштів і леверидж-ефекту, що виникає при цьому. Розроблено моделі та методи розв'язання задач управління інвестиційним портфелем, що враховують невизначеність і ризик при оцінюванні стану зовнішнього середовища, а також рівня можливого прибутку від діяльності підприємства. Розглянуто та удосконалено моделі динаміки вартості активів в умовах ризику і невизначеності. Запропоновано математичну модель марківської динаміки вартості у марківському зовнішньому середовищі.<br>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.<br>Includes bibliographical references (p. 129-131).<br>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.<br>(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.<br>by Lavanya Marla.<br>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.<br>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.<br>Ph. D.

This book aims to empower readers to learn and apply engineering, operations research, and modeling techniques to improve public health programs and healthcare systems. Readers will engage in in-depth study of disease detection and control strategies from a “systems science” perspective, which involves the use of common engineering, operations research, and mathematical modeling techniques such as optimization, queuing theory, Markov and Kermack-McKendrick models, and microsimulation. Chapters focus on applying these techniques to classical public health dilemmas such as how to optimize screening programs, reduce waiting times for healthcare services, solve resource allocation problems, and compare macroscale disease control strategies that cannot be easily evaluated through standard public health methods such as randomized trials or cohort studies. The book is organized around solving real-world problems, typically derived from actual experiences by staff at nongovernmental organizations, departments of public health, and international health agencies. In addition to teaching the theory behind modeling methods, the book aims to confer practical skills to readers through practice in model implementation using the statistical software R.

Reliability of data transmission is a fundamental problem in wireless communications. Fading in wireless channels causes the signal strength to vary at the receiver and this results in loss of data packets. To improve the reliability, automatic repeat request (ARQ) schemes were introduced. However these ARQ schemes suffer from a reduction in the throughput. To address the throughput reduction, conventional ARQ schemes were combined with forward error correction (FEC) schemes to develop hybrid-ARQ (HARQ) schemes. For improving the reliability of data transmission, HARQ schemes are included in the wireless standards like LTE, LTE-Advanced and WiMAX. Conventional HARQ systems use the same transmission power in different ARQ rounds. However this is not optimal in terms of minimizing the average energy spent for successful transmission of a data packet. In this book chapter, the recent research results related to HARQ systems are reviewed first. Next, optimal resource allocation in HARQ systems with a limit on the maximum number of allowed transmissions for a data packet is considered in the next part. Specifically, the problem of minimizing the rate-outage probability under a constraint on average energy consumption per data packet for both incremental redundancy (IR)-based and Chase combining (CC)-based HARQ systems is considered. Towards solving the optimization problems, the expressions for rate-outage probability of both IR-HARQ and CC-HARQ systems in i.i.d. Rayleigh fading channels is provided. Methods to solve the optimization problems using nonlinear optimization techniques are discussed. To reduce the complexity of finding a solution, the rate-outage probability expressions are approximated, using which, the non-convex optimization problems are converted into geometric programming problems (GPPs), for which the closed-form solutions are derived. Illustrative and analytical results show that the proposed power allocation provides significant gains in energy savings over the traditional equal power allocation transmission, and the closed-form GPP solution can provide a performance close to that of the exact method for smaller values of rate-outage probability.

Model predictive control (MPC) is a heuristic control strategy to find a consequence of best controllers during each finite-horizon regarding to certain performance functions of a dynamic system. MPC involves two main operations: estimation and optimization. Due to high complexity of the performance functions, such as, nonlinear, non-convex, large-scale objective functions, the optimization algorithms for MPC must be capable of handling those problems with both computational efficiency and accuracy. Multiagent coordination optimization (MCO) is a recently developed heuristic algorithm by embedding multiagent coordination into swarm intelligence to accelerate the searching process for the optimal solution in the particle swarm optimization (PSO) algorithm. With only some elementary operations, the MCO algorithm can obtain the best solution extremely fast, which is especially necessary to solve the online optimization problems in MPC. Therefore, in this paper, we propose an MCO based MPC strategy to enhance the performance of the MPC controllers when addressing non-convex large-scale nonlinear problems. Moreover, as an application, the network resource balanced allocation problem is numerically illustrated by the MCO based MPC strategy.

This paper presents the robustness analysis for an algorithm that solves simultaneous resource allocation and route optimization problem (SARO). These problems appear in the context of multi-hop routing applications in sensor networks, which require placement of multiple resource nodes and determining routes from each sensor location to a common data destination center via these resource nodes. In [1], we proposed an algorithm based on Maximum Entropy Principle that addressed the determination of locations of these resource nodes and the corresponding multi-hop routing problem such that the total communication cost is minimized. Such placement of resource nodes is sensitive to multiple parameters such as sensor locations, destination center location, communication costs between sensor and resource nodes, between resource nodes, and between resource nodes and destination center. This paper studies the sensitivity of the solution from the algorithm to these parameters. This robustness analysis is necessary since some of these parameters are typically not known precisely, the sensitivity analysis helps the network design by identifying the hierarchy in parameters in terms of how they affect the algorithm solution, and therefore also indicate how precisely these parameters need to be estimated. In this direction, we propose a modification of our algorithm to account for the uncertainty in sensor locations; here a probability distribution of sensor locations instead of their precise locations is assumed to be known. We also present and characterize a phase-transition aspect of the algorithm, where the number of distinct locations of resource nodes increase at certain critical values of annealing variable — a parameter in the algorithm. Simulations are provided that corroborate our analysis and instantiate relative sensitivities between different parameters.