To optimize the beam angle and fluence map in Intensity Modulated Radiation Therapy (IMRT) planning, we apply Benders decomposition as well as develop a two-stage integer programming-based heuristic. Benders decomposition is first implemented in the traditional manner by iteratively solving the restricted master problem, and then identifying and adding the violated Benders cut. We also implemented Benders decomposition using the “lazy constraint” feature included in CPLEX. In contrast, our two-stage heuristic first seeks to find a good solution by iteratively eliminating the least used angles in the linear programming relaxation solution until the size of the formulation is manageable. In the second stage of the heuristic, the solution is improved by applying local branching. The various methods were tested on real patient data in order to investigate their effectiveness and runtime characteristics. The results indicated that implementing Benders using the lazy constraint usually led to better feasible solutions than the traditional approach. Moreover, the LP rounding heuristic was seen to generate high-quality solutions within a short amount of time, with further improvement obtained with the local branching search. / text

In this dissertation, we study an important problem of security in wireless networks. We study different attacks and defense strategies in general and more specifically jamming attacks. We begin the dissertation by providing a tutorial introducing the operations research community to the various types of attacks and defense strategies in wireless networks. In this tutorial, we give examples of mathematical programming models to model jamming attacks and defense against jamming attacks in wireless networks. Later we provide a comprehensive taxonomic classification of the various types of jamming attacks and defense against jamming attacks. The classification scheme will provide a one stop location for future researchers on various jamming attack and defense strategies studied in literature. This classification scheme also highlights the areas of research in jamming attack and defense against jamming attacks which have received less attention and could be a good area of focus for future research. In the next chapter, we provide a bi-level mathematical programming model to study jamming attack and defense strategy. We solve this using a game-theoretic approach and also study the impact of power level, location of jamming device, and the number of transmission channels available to transmit data on the attack and defense against jamming attacks. We show that by increasing the number of jamming devices the throughput of the network drops by at least 7%. Finally we study a special type of jamming attack, flow-jamming attack. We provide a mathematical programming model to solve the location of jamming devices to increase the impact of flow-jamming attacks on wireless networks. We provide a Benders decomposition algorithm along with some acceleration techniques to solve large problem instances in reasonable amount of time. We draw some insights about the impact of power, location and size of the network on the impact of flow-jamming attacks in wireless networks.

Most traditional routing problems assume perfect operability of all arcs and nodes. However, when independent arc failure probabilities exist, a secondary objective must be present to retain some measure of expected functionality. We first briefly consider the reliability-constrained single-path problem, where we look for the lowest cost path that meets a reliability side constraint. This analysis enables us to then examine the reliability-constrained two-path problem, which seeks to establish two minimum-cost paths between a source and destination node wherein at least one path must remain fully operable with some threshold probability. We consider the case in which both paths must be arc-disjoint and the case in which arcs can be shared between the paths. We prove both problems to be NP-hard. We examine strategies for solving the resulting nonlinear integer program, including pruning, coefficient tightening, lifting, and branch-and-bound partitioning schemes. Next, we consider the reliable h-path routing problem, which seeks a minimum-cost set of h ≥ 2 arc-independent paths between a source and destination node, such that the probability that at least one path remains operational is sufficiently large. Our prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. We propose two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms. Finally, we examine the robust design of an evacuation tree, in which evacuation is subject to capacity restrictions on arcs. Given a discrete set of disaster scenarios with varying network populations, arc capacities, transit times, and time-dependent penalty functions, we seek to establish an optimal a priori evacuation tree that minimizes the expected evacuation penalty. The solution strategy is based on Benders decomposition, and we provide effcient methods for obtaining primal and dual sub-problem solutions. We analyze techniques for strengthening the master problem formulation, thus reducing the number of master problem solutions required for the algorithm's convergence.

Dans cette thèse, nous étudions différents modèles, déterministes et stochastiques, pour les problèmes de dimensionnement de réseaux. Nous examinons également le problème du sac-à-dos stochastique ainsi que, plus généralement, les contraintes de capacité en probabilité. Dans une première partie, nous nous consacrons à des modèles de dimensionnement de réseaux déterministes, possédant de nombreuses contraintes techniques s'approchant de situations réalistes. Nous commençons par étudier deux modèles de réseaux de télécommunications. Le premier considère des réseaux multi-couches et des capacités sur les arcs, tandis que le second étudie des réseaux mono-couche, sans capacité, où les commodités doivent être acheminées sur un nombre K de chemins disjoint de taille au plus L. Nous résolvons ces deux problèmes grâce à un algorithme de ``branch-and-cut' basé sur la décomposition de Benders de formulations linéaires pour ces problèmes. La nouveauté de notre approche se situe principalement dans l'étude empirique de la fréquence optimale de génération de coupes au cours de l'algorithme. Nous étudions ensuite un problème d'expansion de réseaux de transmission électrique. Notre travail étudie différents modèles et formulations pour le problème, les comparant sur des réseaux brésiliens réels. En particulier, nous montrons que le re-dimensionnement permet des réductions de coût importantes. Dans une seconde partie, nous examinons des modèles de programmation stochastique. Premièrement, nous prouvons que trois cas particuliers du problème de sac-à-dos avec recours simple peuvent être résolu par des algorithmes de programmation dynamique. Nous reformulons ensuite le problème comme un programme non-linéaire en variables entières et testons un algorithme ``branch-and-cut' basé l'approximation extérieure de la fonction objective. Cet algorithme est ensuite transformé en un algorithme de ``branch-and-cut-and-price', utilisé pour résoudre un problème de dimensionnement de réseau stochastique avec recours simple. Finalement, nous montrons comment linéariser des contraintes de capacité en probabilité avec variables binaires lorsque les coefficients sont des variables aléatoires satisfaisant certaines propriétés.

Strategic network design has significant impacts on the operational performance of transportation and telecommunications industries. The corresponding networks are typically characterized by a multicommodity ow structure where a commodity is defined by a unique origin-destination pair and an associated amount of ow. In turn, multicommodity network design and hub location models are commonly employed when designing strategic networks in transportation and telecommunications applications. In this dissertation, these two modeling approaches are integrated and generalized to address important requirements in network design for truckload transportation and long-distance telecommunications networks. To this end, we first introduce a cost effective relay network design model and then extend this base model to address the specific characteristics of these applications. The base model determines relay point (RP) locations where the commodities are relayed from their origins to destinations. In doing this, we explicitly consider distance constraints for the RP-RP and nonRPRP linkages. In truckload transportation, a relay network (RP-network) can be utilized to decrease drivers' driving distances and keep them within their domiciles. This can potentially help alleviate the high driver turnover problem. In this case, the percentage circuitry, load-imbalance, and link-imbalance constraints are incorporated into the base model to control related performance metrics that are affected by the distance constraints. When compared to the networks from other modeling approaches, the RP-network is more effective in controlling drivers' tour lengths and capable of controlling the empty mileage to low levels without adding a large amount of additional travel distance. In telecommunications, an RP-network can be beneficial in long-distance data transfers where the signals' delity must be improved/regenerated at RPs along their travel paths. For this setting, we extend the base model to include fixed link setup costs and capacities. From our computational results, our models provide better network configuration that is cost effective and facilitates a better service quality (shorter delays and better connectivity). Concerning methodology, we develop effcient exact solution algorithms based on Benders decomposition, Lagrangean decomposition, and Lagrangean relaxation. The performance of the typical solution frameworks are enhanced via numerous accelerating techniques to allow the solution of large-sized instances in reduced solution times. The accelerating techniques and solution approaches are transferable to other network design problem settings with similar characteristics.

Bicycle sharing systems (BSS) have emerged as a powerful stimulus to non- motorized travel, especially for short-distance trips. However, the imbalances in the distribution of bicycles in BSS are widely observed. It is thus necessary to reposition bicycles to reduce the unmet demand due to such imbalances as much as possible. This paper formulates a new mixed-integer linear programming model considering the dynamic nature of the demand to solve the repositioning problem, which is later validated by an illustrative example. Due to the NP-Hard nature of this problem, we seek for two heuristics (greedy algorithm and rolling horizon approach) and one exact solution method (Benders’ decomposition) to get an acceptable solution for problems with large instances within a reasonable computation time. We create four datasets based on real world data with 12, 24, 36, and 48 stations respectively. Computational results show that our model and solution methods performed well. Finally, this paper gives some suggestions on extensions or modifications that might be added to our work in the future. / text

Multiple-resource satellite scheduling problem (MuRRSP) is a complex and difficult scheduling problem, which schedules a large number of task requests onto ground-station antennas in order to communicate with the satellites. We first examined several exact algorithms that were previously implemented in the machine scheduling field. They are column generation and logic-based Benders decomposition. A new hybrid approach that combines both column generation and logic-based Benders decomposition is proposed. The hybrid performed well when there is a large number of machines. Next, we presented a connection between the parallel machine scheduling problem and MuRRSP in order to solve MuRRSP with exact algorithms. Furthermore, we proposed a strengthened cut in the sub-problem of the logic-based Benders decomposition. The resulting algorithm proved to be very effective. Barbulescu’s benchmark problems were solved and proved optimal with an average run-time less than one-hour. To the best of our knowledge, previous efforts to solve MuRRSP were all heuristic based and no optimal schedules existed.

Multiple-resource satellite scheduling problem (MuRRSP) is a complex and difficult scheduling problem, which schedules a large number of task requests onto ground-station antennas in order to communicate with the satellites. We first examined several exact algorithms that were previously implemented in the machine scheduling field. They are column generation and logic-based Benders decomposition. A new hybrid approach that combines both column generation and logic-based Benders decomposition is proposed. The hybrid performed well when there is a large number of machines. Next, we presented a connection between the parallel machine scheduling problem and MuRRSP in order to solve MuRRSP with exact algorithms. Furthermore, we proposed a strengthened cut in the sub-problem of the logic-based Benders decomposition. The resulting algorithm proved to be very effective. Barbulescu’s benchmark problems were solved and proved optimal with an average run-time less than one-hour. To the best of our knowledge, previous efforts to solve MuRRSP were all heuristic based and no optimal schedules existed.

The focus of this work is an industrial refinery model developed by TotalEnergies SE. The model is a sparse, large-scale, nonconvex, mixed-integer nonlinear program (MINLP). The nonconvexity of the problem arises from the many bilinear, trilinear, fractional, logarithmic, exponential, and sigmoidal terms. In order to account for various sources of uncertainty in refinery planning, the industrial refinery model is extended into a two-stage stochastic program, where binary scheduling decisions must be made prior to the realization of the uncertainty, and mixed-integer recourse decisions are made afterwards. Two case studies involving uncertainty are formulated and solved in order to demonstrate the economic and logistical benefits of robust solutions over their deterministic counterparts. A full-space solution strategy is proposed wherein the integrality constraints are relaxed and a multi-step initialization strategy is employed in order to gradually approach the feasible region of the multi-scenario problem. The full-space solution strategy was significantly hampered by difficulties with finding a feasible point and numerical problems. In order to facilitate the identification of a feasible point and to reduce the incidence of numerical difficulties, a hybrid surrogate refinery model was developed using the ALAMO modelling tool. An evaluation procedure was employed to assess the surrogate model, which was shown to be reasonably accurate for most output variables and to be more reliable than the high-fidelity model. Feasible solutions are obtained for the continuous relaxations of both case studies using the full-space solution strategy in conjunction with the surrogate model. In order to solve the original MINLP problems, a decomposition strategy based on the generalized Benders decomposition (GBD) algorithm is proposed. The binary decisions are designated as complicating variables that, when fixed, reduce the full-space problem to a series of independent scenario subproblems. Through the application of the GBD algorithm, feasible mixed-integer solutions are obtained for both case studies, however optimality could not be guaranteed. Solutions obtained via the stochastic programming framework are shown to be more robust than solutions obtained via a deterministic problem formulation. / Thesis / Master of Applied Science (MASc)

No description available.