This thesis presents new results on a few problems involving maximum flows. The first topic we explore is maximum flow network interdiction. The second topic we explore is reoptimization heuristics for rapidly solving an entire sequence of Maximum Flow Problems. In the Cardinality Maximum Flow Network Interdiction Problem (CMFNIP), an interdictor chooses R arcs to delete from an s-t flow network so as to minimize the maximum flow on the network induced on the undeleted arcs. This is an intensively studied problem that has nontrivial applications in military strategy, intercepting contraband and flood control. CMFNIP is a strongly NP-hard special case of the Maximum Flow Network Interdiction Problem (MFNIP), where each arc has an interdiction cost and the interdictor is constrained by an interdiction budget. Although there are several papers on MFNIP, very few theoretical results have been documented. In this talk, we introduce two exponentially large classes of valid inequalities for CMFNIP and prove that they can be separated in polynomial time. Second, we prove that the integrality gap of the commonly used integer linear programming formulation for CMFNIP is contained in the set Omega(|V| ^(1 e)) where |V| is the number of nodes in the network and e is in the interval (0,1). We prove that this result holds even when the linear programming relaxation is strengthened with our two classes of valid inequalities and we note that this result immediately extends to MFNIP. In the second part of this defense, we explore incremental algorithms for solving an online sequence of Maximum Flow Problems (MFPs). Sequences of MFPs arise in a diverse collection of settings including computational biology, finger biometry, constraint programming and real-time scheduling. To initiate this study, we develop an algorithm for solving a sequence of MFPs when the ith MFP differs from the (i-1)st MFP, for each possible i, in that the underlying networks differ by exactly one arc. Second, we develop maximum flow reoptimization heuristics to rapidly compute a robust minimum capacity s-t cut in light of uncertain arc capacities. Third, we develop heuristics to efficiently compute a maximum expected maximum flow in the context of two-stage stochastic programming. We present computational results illustrating the practical performance of our algorithms.

This thesis presents the design, development, and testing of a multi-agent systems laboratory that will enable the experimental investigation of Networked Control Systems. Networked Control Systems (NCS) are integrations of computation, networking, and physical dynamics, in which embedded devices are networked to sense, monitor, execute collaborative tasks, and interact with the physical world. As the potential for applications of NCS has increased, so has the research interest in this area. Possible applications include search and rescue, scientific data collection, and health care monitoring systems. One of the primary challenges in applying NCS is designing distributed algorithms that will enable the networked devices to achieve global objectives. Another challenge is in ensuring that distributed algorithms have the necessary robustness to achieve those global objectives in dynamic and unpredictable environments. A multi-agent systems laboratory provides the researcher with a means to observe the behavior and performance of distributed algorithms as they are executed on a set of networked devices. Through this observation, the researcher may discover robustness issues that were not present in computer simulation. The objective of this research is to design and implement the infrastructure for a multi-agent systems laboratory to observe distributed algorithms implemented on networked devices.

The cost of releasing a new drug on the market has increased rapidly in the last decade. The reasons for this increase vary with the drug, but the need to make correct decisions earlier in the drug development process and to maximize the information gained throughout the process is evident. Optimal experimental design (OD) describes the procedure of maximizing relevant information in drug development and drug treatment processes. While various optimization criteria can be considered in OD, the most common is to optimize the unknown model parameters for an upcoming study. To date, OD has mainly been used to optimize the independent variables, e.g. sample times, but it can be used for any design variable in a study. This thesis addresses the OD of multiple continuous or discrete design variables for nonlinear mixed effects models. The methodology for optimizing and the optimization of different types of models with either continuous or discrete data are presented and the benefits of OD for such models are shown. A software tool for optimizing these models in parallel is developed and three OD examples are demonstrated: 1) optimization of an intravenous glucose tolerance test resulting in a reduction in the number of samples by a third, 2) optimization of drug compound screening experiments resulting in the estimation of nonlinear kinetics and 3) an individual dose-finding study for the treatment of children with ciclosporin before kidney transplantation resulting in a reduction in the number of blood samples to ~27% of the original number and an 83% reduction in the study duration. This thesis uses examples and methodology to show that studies in drug development and drug treatment can be optimized using nonlinear mixed effects OD. This provides a tool than can lower the cost and increase the overall efficiency of drug development and drug treatment.

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

Quantitative Feedback Theory (QFT) is a control system design methodology founded on the premise that feedback is necessary only because of system uncertainty. Articulating flexible structures, such as flexible manipulators, present a difficult closed-loop control problem. In such servo systems, the coupling of the rigid and flexible modes and the non-minimum phase dynamics severely limit system stability and performance. The difficulties in controlling these structures is exacerbated by the denumerably infinite number of flexible modes and associated difficulties in developing accurate dynamic models for controller design. As such, the control of articulating flexible structures presents a non-trivial testbed for the design of QFT based robust control systems. This dissertation examines the multi-input multi-output (MIMO) QFT based control of an articulating flexible structure and presents an enhancement of the theoretical basis for the MIMO QFT design methodologies. The control problem under consideration is the active vibration control of an articulating single-link flexible manipulator. This is facilitated by an actuation scheme comprised of a combination of spatially discrete actuation, in the form of a DC motor to perform articulation, and spatially distributed actuation, in the form of a piezoelectric transducer for active vibration control. In the process of developing and experimentally validating the QFT based control system, shortcomings in the theoretical basis for the MIMO QFT design methodologies are addressed. Robust stability theorems are developed for the two main MIMO QFT design methodologies, namely the sequential and non-sequential MIMO QFT design methodologies. The theorems complement and extend the existing theoretical basis for the MIMO QFT design methodologies. The dissertation results expose salient features of the MIMO QFT design methodologies and provide connections to other multivariable design methodologies.

In this thesis, we consider a robust state estimation problem for discrete-time, homogeneous, first-order, finite-state finite-alphabet hidden Markov models (HMMs). Based on Kolmogorov's Theorem on the existence of a process, we first present the Kolmogorov model for the HMMs under consideration. A new change of measure is introduced. The statistical properties of the Kolmogorov representation of an HMM are discussed on the canonical probability space. A special Kolmogorov measure is constructed. Meanwhile, the ergodicity of two expanded Markov chains is investigated. In order to describe the uncertainty of HMMs, we study probability distance problems based on the Kolmogorov model of HMMs. Using a change of measure technique, the relative entropy and the relative entropy rate as probability distances between HMMs, are given in terms of the HMM parameters. Also, we obtain a new expression for a probability distance considered in the existing literature such that we can use an information state method to calculate it. Furthermore, we introduce regular conditional relative entropy as an a posteriori probability distance to measure the discrepancy between HMMs when a realized observation sequence is given. A representation of the regular conditional relative entropy is derived based on the Radon-Nikodym derivative. Then a recursion for the regular conditional relative entropy is obtained using an information state method. Meanwhile, the well-known duality relationship between free energy and relative entropy is extended to the case of regular conditional relative entropy given a sub-[special character]-algebra. Finally, regular conditional relative entropy constraints are defined based on the study of the probability distance problem. Using a Lagrange multiplier technique and the duality relationship for regular conditional relative entropy, a finite horizon robust state estimator for HMMs with regular conditional relative entropy constraints is derived. A complete characterization of the solution to the robust state estimation problem is also presented.

In this thesis, we consider a robust state estimation problem for discrete-time, homogeneous, first-order, finite-state finite-alphabet hidden Markov models (HMMs). Based on Kolmogorov's Theorem on the existence of a process, we first present the Kolmogorov model for the HMMs under consideration. A new change of measure is introduced. The statistical properties of the Kolmogorov representation of an HMM are discussed on the canonical probability space. A special Kolmogorov measure is constructed. Meanwhile, the ergodicity of two expanded Markov chains is investigated. In order to describe the uncertainty of HMMs, we study probability distance problems based on the Kolmogorov model of HMMs. Using a change of measure technique, the relative entropy and the relative entropy rate as probability distances between HMMs, are given in terms of the HMM parameters. Also, we obtain a new expression for a probability distance considered in the existing literature such that we can use an information state method to calculate it. Furthermore, we introduce regular conditional relative entropy as an a posteriori probability distance to measure the discrepancy between HMMs when a realized observation sequence is given. A representation of the regular conditional relative entropy is derived based on the Radon-Nikodym derivative. Then a recursion for the regular conditional relative entropy is obtained using an information state method. Meanwhile, the well-known duality relationship between free energy and relative entropy is extended to the case of regular conditional relative entropy given a sub-[special character]-algebra. Finally, regular conditional relative entropy constraints are defined based on the study of the probability distance problem. Using a Lagrange multiplier technique and the duality relationship for regular conditional relative entropy, a finite horizon robust state estimator for HMMs with regular conditional relative entropy constraints is derived. A complete characterization of the solution to the robust state estimation problem is also presented.

Quantitative Feedback Theory (QFT) is a control system design methodology founded on the premise that feedback is necessary only because of system uncertainty. Articulating flexible structures, such as flexible manipulators, present a difficult closed-loop control problem. In such servo systems, the coupling of the rigid and flexible modes and the non-minimum phase dynamics severely limit system stability and performance. The difficulties in controlling these structures is exacerbated by the denumerably infinite number of flexible modes and associated difficulties in developing accurate dynamic models for controller design. As such, the control of articulating flexible structures presents a non-trivial testbed for the design of QFT based robust control systems. This dissertation examines the multi-input multi-output (MIMO) QFT based control of an articulating flexible structure and presents an enhancement of the theoretical basis for the MIMO QFT design methodologies. The control problem under consideration is the active vibration control of an articulating single-link flexible manipulator. This is facilitated by an actuation scheme comprised of a combination of spatially discrete actuation, in the form of a DC motor to perform articulation, and spatially distributed actuation, in the form of a piezoelectric transducer for active vibration control. In the process of developing and experimentally validating the QFT based control system, shortcomings in the theoretical basis for the MIMO QFT design methodologies are addressed. Robust stability theorems are developed for the two main MIMO QFT design methodologies, namely the sequential and non-sequential MIMO QFT design methodologies. The theorems complement and extend the existing theoretical basis for the MIMO QFT design methodologies. The dissertation results expose salient features of the MIMO QFT design methodologies and provide connections to other multivariable design methodologies.