This work contributes to modeling, theoretical, and practical aspects of structured Mathematical Programming problems. Many real-world applications have nonlinear characteristics and can be modeled as Mixed Integer Nonlinear Programming problems (MINLP). Modern global solvers have significant difficulty handling large-scale instances of them. Several convexification and underestimation techniques were proposed in the last decade as a part of the solution process, and we join this trend. The thesis has three major parts. The first part considers MINLP problems containing convex (in the sense of continuous relaxations) and posynomial terms (also called monomials), i.e. products of variables with some powers. Recently, a linear Mixed Integer Programming (MIP) approach was introduced for minimization the number of variables and transformations for convexification and underestimation of these structured problems. We provide polyhedral analysis together with separation for solving our variant of this minimization subproblem, containing binary and bounded continuous variables. Our novel mixed hyperedge method allows to outperform modern commercial MIP software, providing new families of facet-defining inequalities. As a byproduct, we introduce a new research area called mixed conflict hypergraphs. It merges mixed conflict graphs and 0-1 conflict hypergraphs. The second part applies our mixed hyperedge method to a linear subproblem of the same purpose for another class of structured MINLP problems. They contain signomial terms, i.e. posynomial terms of both positive and negative signs. We obtain new facet-defining inequalities in addition to those families from the first part. The final part is dedicated to managing guest flow in Georgia Aquarium after the Dolphin Tales opening with applying a large-scale MINLP. We consider arrival and departure processes related to scheduled shows and develop three stochastic models for them. If demand for the shows is high, all processes become interconnected and require a generalized model. We provide and solve a Signomial Programming problem with mixed variables for minimization resources to prevent and control congestions.

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.

Consider a binary matroid M given by its matrix representation. We show that if M is a lift of a graphic or a cographic matroid, then in polynomial time we can either solve the single commodity flow problem for M or find an obstruction for which the Max-Flow Min-Cut relation does not hold. The key tool is an algorithmic version of Lehman's Theorem for the set covering polyhedron.

Consider a binary matroid M given by its matrix representation. We show that if M is a lift of a graphic or a cographic matroid, then in polynomial time we can either solve the single commodity flow problem for M or find an obstruction for which the Max-Flow Min-Cut relation does not hold. The key tool is an algorithmic version of Lehman's Theorem for the set covering polyhedron.

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.

Spatial resource allocation is an important consideration in shipbuilding and large-scale manufacturing industries. Spatial scheduling problems (SSP) involve the non-overlapping arrangement of jobs within a limited physical workspace such that some scheduling objective is optimized. Since jobs are heavy and occupy large areas, they cannot be moved once set up, requiring that the same contiguous units of space be assigned throughout the duration of their processing time. This adds an additional level of complexity to the general scheduling problem, due to which solving large instances of the problem becomes computationally intractable. The aim of this study is to gain a deeper understanding of the relationship between the spatial and temporal components of the problem. We exploit these acquired insights on problem characteristics to aid in devising solution procedures that perform well in practice. Much of the literature on SSP focuses on the objective of minimizing the makespan of the schedule. We concentrate our efforts towards the minimum sum of completion times objective and state several interesting results encountered in the pursuit of developing fast and reliable solution methods for this problem. Specifically, we develop mixed-integer programming models that identify groups of jobs (batches) that can be scheduled simultaneously. We identify scenarios where batching is useful and ones where batching jobs provides a solution with a worse objective function value. We present computational analysis on large instances and prove an approximation factor on the performance of this method, under certain conditions. We also provide greedy and list-scheduling heuristics for the problem and compare their objectives with the optimal solution. Based on the instances we tested for both batching and list-scheduling approaches, our assessment is that scheduling jobs similar in processing times within the same space yields good solutions. If processing times are sufficiently different, then grouping jobs together, although seemingly makes a more effective use of the space, does not necessarily result in a lower sum of completion times.

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)