Soil sampling can help producers gain more accurate knowledge about soil nutrient properties and field-level characteristics. This information aids in the placement and timing of fertilizer application. Optimal input application may lower variable costs, increase economic returns, and moderate off-site environmental impacts of farming. Yet producer decisions to incorporate soil information into management practices and perceptions about the value of soil test information over time depends on a wide range of economic, social, and producer characteristics. Studies examining the value of soil information for optimal nutrient management may help inform producers considering adopting these technologies about the potential benefits of soil testing. This thesis provides two studies examining (1) the factors associated with the adoption of precision soil sampling and the length of time this information is perceived useful by cotton producers, and (2) the value of soil test information with regards to optimal potassium fertilizer management in cotton production over multiple growing seasons. Perceptions about the usefulness of soil test information over time depend on a variety of factors directly or indirectly related to input management. In the first study, the adoption and frequency of soil testing is examined as a function of off-farm, farm business, information sources, and operator characteristics using a Poisson hurdle regression model. Analyzing data from a survey of cotton farmers in 12 Southern states, the length of time producers perceived soil test information to be useful were influenced by farmer experience, land tenure, and the use of other information gathering technologies such as Greenseeker® and electro conductivity. In the second study, optimal potassium (K) management with information about fertilizer carryover was analyzed using a dynamic programming model. Monte Carlo simulation results suggest the information site-specific technologies provides with respect to residual fertilizer carryover effects of K are greatest when a producer is able to identify the magnitude of soil carryover capacity and incorporate this information to manage K. The information obtained from this research may provide insight for cotton producers, agribusiness firms, and agricultural service providers about the perception and potential benefits of soil sampling information to manage inputs in cotton production.

Dynamic Programming is an optimization technique used in computer science and mathematics. Introduced in the 1950s, it has been applied to many classic combinatorial optimization problems, such as the Shortest Path Problem, the Knapsack Problem, and the Traveling Salesman Problem, with varying degrees of practical success. In this thesis, we present two applications of dynamic programming to optimization problems. The first application is as a method to compute the Branch-Cut-and-Price (BCP) family of lower bounds for the Traveling Salesman Problem (TSP), and several vehicle routing problems that generalize it. We then prove that the BCP family provides a set of lower bounds that is at least as strong as the Approximate Linear Program (ALP) family of lower bounds for the TSP. The second application is a novel dynamic programming model used to determine the placement of cuts for a particular form of skull surgery called Cranial Vault Remodeling.

The thesis focuses on a model that seeks to address patient scheduling step of the surgical scheduling process to determine the number of surgeries to perform in a given day. Specifically, provided a master schedule that provides a cyclic breakdown of total OR availability into specific daily allocations to each surgical specialty, we look to provide a scheduling policy for all surgeries that minimizes a combination of the lead time between patient request and surgery date, overtime in the ORs and congestion in the wards. We cast the problem of generating optimal control strategies into the framework of Markov Decision Process (MDP). The Approximate Dynamic Programming (ADP) approach has been employed to solving the model which would otherwise be intractable due to the size of the state space. We assess performance of resulting policy and quality of the driven policy through simulation and we provide our policy insights and conclusions.

Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.

New and exciting possibilities in vehicle control are revealed by the consideration of topography through the combination GPS and three dimensional road maps. This thesis explores how information about future road slopes can be utilized in a heavy truck with the aim at reducing the fuel consumption over a route without increasing the total travel time. A model predictive control (MPC) scheme is used to control the longitudinal behavior of the vehicle, which entails determining accelerator and brake levels and also which gear to engage. The optimization is accomplished through discrete dynamic programming. A cost function is used to define the optimization criterion. Through the function parameters the user is enabled to decide how fuel use, negative deviations from the reference velocity, velocity changes, gear shifts and brake use are weighed. Computer simulations with a load of 40 metric tons shows that the fuel consumption can be reduced with 2.5% with a negligible change in travel time, going from Link¨oping to J¨onk¨oping and back. The road slopes are calculated by differentiation of authentic altitude measurements along this route. The complexity of the algorithm when achieving these results allows the simulations to run two to four times faster than real time on a standard PC, depending on the desired update frequency of the control signals.

In the field of proteomic mass spectrometry, proteins can be sequenced by two independent yet complementary algorithms: de novo sequencing which uses no prior knowledge and database search which relies upon existing protein databases. In the case where an organism’s protein database is not available, the software Spider was developed in order to search sequence tags produced by de novo sequencing against a database from a related organism while accounting for both errors in the sequence tags and mutations. This thesis further develops Spider by using the concept of reconstruction in order to predict the real sequence by considering both the sequence tags and their matched homologous peptides. The significant value of these reconstructed sequences is demonstrated. Additionally, the runtime is greatly reduced and separated into independent caching and matching steps. This new approach allows for the development of an efficient algorithm for search. In addition, the algorithm’s output can be used for new applications. This is illustrated by a contribution to a complete protein sequencing application.

Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.

Algorithmic Framework for Improving Heuristics in Stochastic, Stage-Wise Optimization Problems Jaein Choi 172 Pages Directed by Dr. Jay H. Lee and Dr. Matthew J. Realff The goal of this thesis is the development of a computationally tractable solution method for stochastic, stage-wise optimization problems. In order to achieve the goal, we have developed a novel algorithmic framework based on Dynamic Programming (DP) for improving heuristics. The propose method represents a systematic way to take a family of solutions and patch them together as an improved solution. However, patching is accomplished in state space, rather than in solution space. Since the proposed approach utilizes simulation with heuristics to circumvent the curse of dimensionality of the DP, it is named as Dynamic Programming in Heuristically Restricted State Space. The proposed algorithmic framework is applied to stochastic Resource Constrained Project Scheduling problems, a real-world optimization problem with a high dimensional state space and significant uncertainty equivalent to billions of scenarios. The real-time decision making policy obtained by the proposed approach outperforms the best heuristic applied in simulation stage to form the policy. The proposed approach is extended with the idea of Q-Learning technique, which enables us to build empirical state transition rules through simulation, for stochastic optimization problems with complicated state transition rules. Furthermore, the proposed framework is applied to a stochastic supply chain management problem, which has high dimensional action space as well as high dimensional state space, with a novel concept of implicit sub-action space that efficiently restricts action space for each state in the restricted state space. The resulting real-time policy responds to the time varying demand for products by stitching together decisions made by the heuristics and improves overall performance of the supply chain. The proposed approach can be applied to any problem formulated as a stochastic DP, provided that there are reasonable heuristics available for simulation.

The first part of this two-part thesis examines the reverse-flow operation of auto-thermal methane reforming in a microreactor. A theoretical study is undertaken to explain the physical origins of the experimentally observed improvements in the performance of the reverse-flow operation compared to the unidirectional operation. First, a scaling analysis is presented to understand the effect of various time scales existing within the microreactor, and to obtain guidelines for the optimal reverse-flow operation. Then, the effect of kinetic parameters, transport properties, reactor design and operating conditions on the reactor operation is parametrically studied through numerical simulations. The reverse-flow operation is shown to be more robust than the unidirectional operation with respect to both optimal operating conditions as well as variations in hydrogen throughput requirements. A rational scheme for improved catalyst placement in the microreactor, which exploits the spatial temperature profiles in the reactor, is also presented. Finally, a design modification of the microreactor called "opposed-flow" reactor, which retains the performance benefits of the reverse-flow operation without requiring the input / output port switching, is suggested. In the second part of this thesis, a novel simulation-based Approximate Dynamic Programming (ADP) framework is presented for optimal control of switching between multiple metabolic states in a microbial bioreactor. The cybernetic modeling framework is used to capture these cellular metabolic switches. Model Predictive Control, one of the most popular advanced control methods, is able to drive the reactor to the desired steady state. However, the nonlinearity and switching nature of the system cause computational and performance problems with MPC. The proposed ADP has an advantage over MPC, as the closed-loop optimal policy is computed offline in the form of so-called value or cost-to-go function. Through the use of an approximation of the value function, the infinite horizon problem is converted into an equivalent single-stage problem, which can be solved online. Various issues in implementation of ADP are also addressed.

This dissertation develops and evaluates a new adaptive traffic signal control system for arterials. This control system is based on reinforcement learning, which is an important research area in distributed artificial intelligence and has been extensively used in many applications including real-time control. In this dissertation, a systematic comparison between the reinforcement learning control methods and existing adaptive traffic control methods is first presented from the theoretical perspective. This comparison shows both the connections between them and the benefits of using reinforcement learning. A Neural-Fuzzy Actor-Critic Reinforcement Learning (NFACRL) method is then introduced for traffic signal control. NFACRL integrates fuzzy logic and neural networks into reinforcement learning and can better handle the curse of dimensionality and generalization problems associated with ordinary reinforcement learning methods. This NFACRL method is first applied to isolated intersection control. Two different implementation schemes are considered. The first scheme uses a fixed phase sequence and variable cycle length, while the second one optimizes phase sequence in real time and is not constrained to the concept of cycle. Both schemes are further extended for arterial control, with each intersection being controlled by one NFACRL controller. Different strategies used for coordinating reinforcement learning controllers are reviewed, and a simple but robust method is adopted for coordinating traffic signals along the arterial. The proposed NFACRL control system is tested at both isolated intersection and arterial levels based on VISSIM simulation. The testing is conducted under different traffic volume scenarios using real-world traffic data collected during morning, noon, and afternoon peak periods. The performance of the NFACRL control system is compared with that of the optimized pre-timed and actuated control. Testing results based on VISSIM simulation show that the proposed NFACRL control has very promising performance. It outperforms optimized pre-timed and actuated control in most cases for both isolated intersection and arterial control. At the end of this dissertation, issues on how to further improve the NFACRL method and implement it in real world are discussed.