This thesis will address several problems in discrete optimization. These problems are considered hard to solve. However, good approximation algorithms for these problems may be helpful in approximating problems in computational biology and computer science. Given an undirected graph G=(V,E) and a family of subsets of vertices S, the minimum crossing spanning tree is a spanning tree where the maximum number of edges crossing any single set in S is minimized, where an edge crosses a set if it has exactly one endpoint in the set. This thesis will present two algorithms for special cases of minimum crossing spanning trees. The first algorithm is for the case where the sets of S are pairwise disjoint. It gives a spanning tree with the maximum crossing of a set being 2OPT+2, where OPT is the maximum crossing for a minimum crossing spanning tree. The second algorithm is for the case where the sets of S form a laminar family. Let b_i be a bound for each S_i in S. If there exists a spanning tree where each set S_i is crossed at most b_i times, the algorithm finds a spanning tree where each set S_i is crossed O(b_i log n) times. From this algorithm, one can get a spanning tree with maximum crossing O(OPT log n). Given an undirected graph G=(V,E), and a family of subsets of vertices S, the minimum crossing perfect matching is a perfect matching where the maximum number of edges crossing any set in S is minimized. A proof will be presented showing that finding a minimum crossing perfect matching is NP-hard, even when the graph is bipartite and the sets of S are pairwise disjoint.

Natural disasters and extreme events are often characterized by their violence and unpredictability, resulting in consequences that in severe cases result in devastating physical and ecological damage as well as countless fatalities. In August 2005, Hurricane Katrina hit the Southern coast of the United States wielding serious weather and storm surges. The brunt of Katrina’s force was felt in Louisiana, where the hurricane has been estimated to total more than $108 billion in damage and over 1,800 casualties. Hurricane Rita followed Katrina in September 2005 and further contributed $12 billion in damage and 7 fatalities to the coastal communities of Louisiana and Texas. Prior to making landfall, residents of New Orleans received a voluntary, and then a mandatory, evacuation order in an attempt to encourage people to move themselves out of Hurricane Katrina’s predicted destructive path. Consistent with current practice in nearly all states, this evacuation order did not include or convey any information to individuals regarding route selection, shelter availability and assignment, or evacuation timing. This practice leaves the general population free to determine their own routes, destinations and evacuation times independently. Such freedom often results in inefficient and chaotic utilization of the roadways within an evacuation region, quickly creating bottlenecks along evacuation routes that can slow individual egress and lead to significant and potentially dangerous exposure of the evacuees to the impending storm. One way to assist the over-burdened and over-exposed population during extreme event evacuation is to provide an evacuation strategy that gives specific information on individual route selection, evacuation timing and shelter destination assignment derived from effective, strategic pre-planning. For this purpose, we present a mixed integer linear program to devise effective and controlled evacuation networks to be utilized during extreme event egress. To solve our proposed model, we develop a solution methodology based on Benders Decomposition and test its performance through an experimental design using the Central Texas region as our case study area. We show that our solution methods are efficient for large-scale instances of realistic size and that our methods surpass the size and computational limitations currently imposed by more traditional approaches such as branch-and-cut. To further test our model under conditions of uncertain individual choice/behavior, we create an agent-based simulation capable of modeling varying levels of evacuee compliance to the suggested optimal routes and varying degrees of communication between evacuees and between evacuees and the evacuation authority. By providing evacuees with information on when to evacuate, where to evacuate and how to get to their prescribed destination, we are able to observe significant cost and time increases for our case study evacuation scenarios while reducing the potential exposure of evacuees to the hurricane through more efficient network usage. We provide discussion on scenario performance and show the trade-offs and benefits of alternative batch-time evacuation strategies using global and individual effectiveness measures. Through these experiments and the developed methodology, we are able to further motivate the need for a more coordinated and informative approach to extreme event evacuation.

This thesis will address several problems in discrete optimization. These problems are considered hard to solve. However, good approximation algorithms for these problems may be helpful in approximating problems in computational biology and computer science. Given an undirected graph G=(V,E) and a family of subsets of vertices S, the minimum crossing spanning tree is a spanning tree where the maximum number of edges crossing any single set in S is minimized, where an edge crosses a set if it has exactly one endpoint in the set. This thesis will present two algorithms for special cases of minimum crossing spanning trees. The first algorithm is for the case where the sets of S are pairwise disjoint. It gives a spanning tree with the maximum crossing of a set being 2OPT+2, where OPT is the maximum crossing for a minimum crossing spanning tree. The second algorithm is for the case where the sets of S form a laminar family. Let b_i be a bound for each S_i in S. If there exists a spanning tree where each set S_i is crossed at most b_i times, the algorithm finds a spanning tree where each set S_i is crossed O(b_i log n) times. From this algorithm, one can get a spanning tree with maximum crossing O(OPT log n). Given an undirected graph G=(V,E), and a family of subsets of vertices S, the minimum crossing perfect matching is a perfect matching where the maximum number of edges crossing any set in S is minimized. A proof will be presented showing that finding a minimum crossing perfect matching is NP-hard, even when the graph is bipartite and the sets of S are pairwise disjoint.

Many important applications in the real world that can be modelled as combinatorial optimization problems are actually dynamic in nature. However, research on dynamic optimization focuses on continuous optimization problems, and rarely targets combinatorial problems. Moreover, dynamic combinatorial problems, when addressed, are typically tackled within an application context. <br /><br /> In this thesis, dynamic combinatorial problems are addressed collectively by adopting an evolutionary based algorithmic approach. On the plus side, their ability to manipulate several solutions at a time, their robustness and their potential for adaptability make evolutionary algorithms a good choice for solving dynamic problems. However, their tendency to converge prematurely, the difficulty in fine-tuning their search and their lack of diversity in tracking optima that shift in dynamic environments are drawbacks in this regard. <br /><br /> Developing general methodologies to tackle these conflicting issues constitutes the main theme of this thesis. First, definitions and measures of algorithm performance are reviewed. Second, methods of benchmark generation are developed under a generalized framework. Finally, methods to improve the ability of evolutionary algorithms to efficiently track optima shifting due to environmental changes are investigated. These methods include adapting genetic parameters to population diversity and environmental changes, the use of multi-populations as an additional means to control diversity, and the incorporation of local search heuristics to fine-tune the search process efficiently. <br /><br /> The methodologies developed for algorithm enhancement and benchmark generation are used to build and test evolutionary models for dynamic versions of the travelling salesman problem and the flexible manufacturing system. Results of experimentation demonstrate that the methods are effective on both problems and hence have a great potential for other dynamic combinatorial problems as well.

Doctor of Philosophy / Department of Agricultural Economics / Nathan P. Hendricks / Risk averse farmers face a substantial challenge managing irrigation water when they face limited water availability. The two primary reasons for limited water availability in the High Plains Aquifer region of the United States are limited well capacity (i.e., the rate at which groundwater can be extracted) or a constraint imposed by a policy. In this dissertation, I study how risk averse farmers optimally manage limited water availability in the face of weather uncertainty and also the impact of limited water availability on farmer welfare. I use AquaCrop, a daily biophysical crop simulation model, to predict corn yield under alternative irrigation scenarios with historical weather. Since no simple functional form exists for the crop production function, I use discrete optimization and consider 234,256 potential irrigation strategies. I also account for risk preferences by using expected utility analysis to determine the optimal irrigation strategy. Using a daily biophysical model is important because water stress in a short period of the growing season can impact crop yield (even if average water availability throughout the growing season is sufficient) and well capacity is a constraint on daily water use. The daily biophysical crop simulation model accounts for the dynamic response of crop production to water availability. First, I examine how optimal irrigation strategies change due to limited water availability. I find that it is never optimal for irrigators to apply less than a particular minimum instantaneous rate per irrigated acre. An optimal required instantaneous rate implies that a farmer with a low well capacity focuses on adjustment at the extensive margin. On the other hand, farmers who initially have a high well capacity should adjust at the intensive margin in response to well capacity declining. I also find that total water use increases as the degree of risk aversion increases. More risk averse farmers increase water use by increasing irrigation intensity to reduce the variance in corn yields. Another important finding is that a higher well capacity could actually promote less water use because the higher well capacity allows a greater instantaneous rate of application that allows the farmer to decrease irrigation intensity while still maintaining or increasing corn yield. This finding may imply an accelerated rate of groundwater extraction when the groundwater depletion reaches a particular threshold. Second, I analyze the welfare loss due to limited water availability. The relationship between welfare loss and well capacity due to a policy constraint differs by soil type. I found the welfare loss from a water constraint policy does not always increase as well capacity increases. Farmers with very high well capacity may make small or no adjustment at the extensive margin due to a higher instantaneous rate and higher soil water holding capacity. However, that is not the case for a farmer with land that has lower soil water holding capacity as the increase in well capacity results in greater welfare loss. I also investigate the effect of risk averse behavior on the magnitude of welfare loss. I found that the welfare loss per unit of reduced water use is lower for the farmer with more risk aversion. Thus, economic models that ignore risk aversion misestimate the cost of reducing water use. Finally, I investigate the incentive for adopting drip irrigation and its effect on water use. I find that a decrease in well capacity increases the benefits of adopting drip irrigation but is not sufficient to overcome the high initial investment cost without government support. While subsidies of the magnitude offered by current U.S. programs are sufficient to induce drip irrigation adoption, I find that such subsidies have the unintended consequence of increasing total water use, particularly for small well capacities.

We propose an approach to address data uncertainty for discrete optimization problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. When both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows to control the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0 - 1 discrete optimization problem on n variables, then we solve the robust counterpart by solving n + 1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0 -1 discrete optimization problem remains polynomially solvable. Moreover, we show that the robust counterpart of an NP-hard α-approximable 0 - 1 discrete optimization problem remains α-approximal. / Singapore-MIT Alliance (SMA)

In the literature, a large number of metaheuristic search techniques have been proposed up to present time and some of those have been used in structural optimization. Scatter search is one of those techniques which has proved to be effective when solving combinatorial and nonlinear optimization problems such as scheduling, routing, financial product design and other problem areas. Scatter search is an evolutionary method that uses strategies based on a composite decision rules and search diversification and intensification for generating new trial points. Broodly speaking, this thesis is concerned with the use and application of scatter search technique in structural optimization. A newly developed optimization algorithm called modified scatter search is modified which is computerized in a software called SOP2012. The software SOP2012 is integrated with well-known structural analysis software SAP2000 using application programming interface for size optimum design of steel structures. Numerical studies are carried out using a test suite consisting of five real size design examples taken from the literature. In these examples, various steel truss and frame structures are designed for minimum weight according to design limitations imposed by AISC-ASD (Allowable Stress Design Code of American Institute of Steel Construction). The results reveal that the modified scatter search technique is very effective optimization technique for truss structures, yet its performance can be assessed ordinary for frame structures.

Many important applications in the real world that can be modelled as combinatorial optimization problems are actually dynamic in nature. However, research on dynamic optimization focuses on continuous optimization problems, and rarely targets combinatorial problems. Moreover, dynamic combinatorial problems, when addressed, are typically tackled within an application context. <br /><br /> In this thesis, dynamic combinatorial problems are addressed collectively by adopting an evolutionary based algorithmic approach. On the plus side, their ability to manipulate several solutions at a time, their robustness and their potential for adaptability make evolutionary algorithms a good choice for solving dynamic problems. However, their tendency to converge prematurely, the difficulty in fine-tuning their search and their lack of diversity in tracking optima that shift in dynamic environments are drawbacks in this regard. <br /><br /> Developing general methodologies to tackle these conflicting issues constitutes the main theme of this thesis. First, definitions and measures of algorithm performance are reviewed. Second, methods of benchmark generation are developed under a generalized framework. Finally, methods to improve the ability of evolutionary algorithms to efficiently track optima shifting due to environmental changes are investigated. These methods include adapting genetic parameters to population diversity and environmental changes, the use of multi-populations as an additional means to control diversity, and the incorporation of local search heuristics to fine-tune the search process efficiently. <br /><br /> The methodologies developed for algorithm enhancement and benchmark generation are used to build and test evolutionary models for dynamic versions of the travelling salesman problem and the flexible manufacturing system. Results of experimentation demonstrate that the methods are effective on both problems and hence have a great potential for other dynamic combinatorial problems as well.

In today's world, it is becoming increasingly important to be able to design high performance integrated circuits (ICs) and have them run at as low power as possible. Gate sizing and threshold voltage (Vt) assignment optimizations are one of the major contributors to such trade-offs for power and performance of ICs. In fact, the ever increasing design sizes and more aggressive timing requirements make gate sizing and Vt assignment one of the most important CAD problems in physical synthesis. A promising gate sizing optimization algorithm has to satisfy requirements like being scalable to tackle very large design sizes, being able to optimally utilize a large (but finite) number of possible gate configurations available in standard cell library based on different gate sizes and/or threshold voltages (Vt) and/or gate lengths (Lg), and also, being able to handle non-convex cell delays in modern cell libraries. The work in this thesis makes use of the research-oriented infrastructure made available as part of the ISPD (International Symposium on Physical Design) 2012 Gate Sizing Contest that addresses the issues encountered in modern gate sizing problems. We present a two-phase optimization approach where Lagrangian Relaxation is used to formulate the optimization problem. In the first phase, the Lagrangian relaxed subproblem is iteratively solved using a greedy algorithm, while in the second phase, a cell downsizing and Vt upscaling heuristic is employed to further recover power from the timing-feasible and power-optimized sizing solution obtained at the end of first phase. We also propose a multi-core implementation of the first-phase optimizations, which constitute majority of the total runtime, to take advantage of multi-core processors available today. A speedup of the order of 4 to 9 times is seen on different benchmarks as compared to serial implementation when run on a 2 socket 6-core machine. Compared to the winner of ISPD 2012 contest, we further reduce leakage power by 17.21% and runtime by 87.92%, on average, while obtaining feasible sizing solutions on all the benchmark designs. / text

Les tâches réalisées en traitement d'image tendent à devenir de plus en plus complexes. Par exemple, dans le contexte routier, les systèmes d'aide à la conduite, (Advanced driver-assistance systems), visent à une automatisation complète de la tâche de conduite. L’évaluation de la fiabilité représente un enjeu important pour ce type d’application. Face à la difficulté des tâches à réaliser, les chaînes de traitements sont souvent divisées en de nombreuses étapes de calculs de sorte qu'il est difficile de caractériser les sorties de la chaîne en fonction des perturbations des entrées. Les étapes du traitement consistent le plus souvent en des problèmes formulés comme la minimisation d'une énergie. Cette énergie est généralement difficile à optimiser, ce qui nécessite la mise en œuvre de méthodes d’optimisation adaptées. Dans cette thèse, nous cherchons à caractériser la solution d’un traitement à partir des calculs réalisés au cours de l’étape d'optimisation. Cette approche nous a permis de proposer des indices de stabilité de la solution dans le cadre de deux méthodes d’optimisation discrètes : la coupure de graphe et la programmation dynamique. Tout d’abord, nous nous sommes intéressés au problème de la reconstruction stéréoscopique en contexte routier et au dé-bruitage, dans le cadre de l’optimisation par coupure de graphe. Les modèles issus de l’interprétation bayésienne amènent à optimiser des énergies qui ne peuvent pas être traitées avec les schémas d’optimisation classiques par fusion binaire. Nous avons proposé un schéma adapté qui met en jeu des fusions binaires par expansion et par saut. L’application de ce schéma aux problèmes de la reconstruction stéréoscopique et au dé-bruitage, nous a permis d’obtenir des solutions possédant les caractéristiques que nous recherchions : des contours d’objets nets et des dégradés progressifs dans les zones homogènes. Ensuite, dans le contexte de la programmation dynamique, nous avons réinterprété l’a priori mis en jeu dans la méthode de reconstruction Semi-Global Matching ainsi que certaines de ses variantes. Nous avons proposé d’ajouter un paramètre à ces méthodes afin de modifier les directions privilégiées par l’a priori. Enfin, nous avons proposé des indices de stabilité de la solution dans le cadre de la coupure de graphe et de la programmation dynamique. La prise en compte de ces indices, dans une étape de raffinement des solutions, permet une amélioration des résultats / Problems solved by image processing tend to be more and more complex. For instance, in road context, ADAS (Advanced driver-assistance systems) aim to a completely automatic diving tack. Evaluating system reliability is an important challenge in that case. These tasks being hard to perform, processing chains are often divide in numerous processing steps. As a consequence, characterizing the output using the input of the chain is not obvious. Most of the time, image processing steps are formulate as an energy minimization. These energies are often hard to minimize and need to apply suitable optimization methods. In this thesis, we aim to characterize the solution during the optimization step. Using this approach, we proposed stability index with two discrete optimization methods : graph-cut and dynamic optimization. First, we focused on stereoscopic reconstruction problem in road context and on denoising problem using graph-cut. Models obtained by Bayesian interpretation lead to optimize energies witch cannot be handled by classical binary fusion optimization scheme. We proposed a suitable scheme composed of fusion by expansion and fusions by step. When this scheme is apply to stereoscopic reconstruction and denoising, obtained solution have the wanted characteristics : sharp edges and shading in homogeneous areas. Next, in dynamic programming context, we reinterpreted the prior used in Semi-Global Matching (SGM) stereoscopic reconstruction method and in some of its variants. We proposed an additional parameter in order to modify the favored direction in the prior. At last, we proposed stability index of the solution in graph-cut and dynamic programing context. Using this index in a solution refinement step shows improvements