International fishing as a special dynamic game will be analyzed, which is a combination of classical population dynamics and oligopoly theory. The interaction of the countries or firms is through market rules assuming that all markets are open to all participants. In addition, all fishing parties base their activity on the existing common fish stock. The available fish stock and the beliefs of the participants on the fish stock are the state variables. Depending on the possible symmetry of the fishing parties and on their behavior several alternative models will be formed. The classical competitive model will be first formulated and examined, and two special cases will be introduced. First, when the countries, or firms, are identical, second, when one country, or firm, is significantly different than the others. Next, we will assume that a grand coalition is formed, and the total profit of the industry is maximized. Finally, the partially cooperative case will be examined, in which each participant's objective function contains a certain proportion of the profits of the others in addition to its own profits. In all cases, a detailed mathematical model will be constructed, the equilibrium will be computed and the modified population dynamics rule will be formulated. For each case, I will determine the number of positive equilibria, the stability of which will be analyzed first based on the assumption that each participant has instantaneous information on the fish stock. However, there is always a time lag due to information collection and implementation. Since the delay is uncertain, continuously distributed time lags will be assumed. Under this assumption, the dynamic system will be described by Volterra-type integro-differential equations. The asymptotical behavior of the state trajectory will be analyzed by using linearization. Conditions for the local asymptotical stability will be first derived, and in the case of instability, special bifurcations, especially the birth of limit cycles, will be studied. In illustrating the theoretical, analytic results, simple computer studies will be presented.

<p> This dissertation presents a methodology for the joint optimization of a variety of pavement construction and management activities for segment and system problems under multiple budget constraints. The objective of pavement management is to minimize the total discounted life time costs for the agency and the highway users by finding optimal policies. The scope of the dissertation is focused on continuous time and continuous state formulations of pavement condition. We use a history-dependent pavement deterioration model to account for the influence of history on the deterioration rate. </p><p> Three topics, representing different aspects of the problem are covered in the dissertation. In the first part, the subject is the joint optimization of pavement design, maintenance and rehabilitation (M&R;) strategies for the segment-level problem. A combination of analytical and numerical tools is proposed to solve the problem. In the second part of the dissertation, we present a methodology for the joint optimization of pavement maintenance, rehabilitation and reconstruction (MR&R;) activities for the segment-level problem. The majority of existing Pavement Management Systems (PMS) do not optimize reconstruction jointly with maintenance and rehabilitation policies. We show that not accounting for reconstruction in maintenance and rehabilitation planning results in suboptimal policies for pavements undergoing cumulative damage in the underlying layers (base, sub-base or subgrade). We propose dynamic programming solutions using an augmented state which includes current surface condition and age. In the third part, we propose a methodology for the joint optimization of rehabilitation and reconstruction activities for heterogeneous pavement systems under multiple budget constraints. Within a bottom-up solution approach, Genetic Algorithm (GA) is adopted. The complexity of the algorithm is polynomial in the size of the system and the policy-related parameters. </p>

Demand for broadband services such as fax, videotelephony, video conference and data transmission continues to explode as we move into the twenty-first century. The new broadband demand differs from voice traffic in that it varies rapidly with respect to the average length of time capacity is held by a customer. Hence, steady state models of network traffic are not valid in general, and may not provide approximations that are sufficiently accurate for network design. In addition, modern telecommunications networks incorporate advanced switching technology that can provide flexible routing of network traffic based on network load and projected demand. It is desireable to take advantage of this new flexibility to design reliable, yet low cost, networks. In this dissertation a multistage stochastic linear programming model for the design of broadband networks is presented, along with a specialized algorithm for solving the program. The algorithm is based on Network Recourse Decomposition (NRD) first introduced by Powell and Cheung. The solution method incorporates cost calculations that prove to be useful for both sizing and routing decisions.

The objective of this study is to develop a practical mathematical model to determine optimal operating rules for the reservoir system of the West Branch Penobscot River in the State of Maine of the US. This system is composed of five major lakes and it has three objectives. The hydrological data are not available in winter in the upstream four lakes due to freeze and the length of flow data is less than 25 years. Dynamic programming (DP) has been used extensively for solving reservoir operation problems. One major drawback of DP for multiple reservoir operation is the "curse of dimensionality". Many variations of the original DP have been proposed to ease this problem, for example, incremental DP, discrete differential DP, differential DP, gradient DP, and spline DP. Instead of a DP approach, this study proposes using a nonlinear programming (NLP) approach to solve the multi-reservoir system. NLP has been developed extensively in the field of operations research but not yet widely used in reservoir operations. A distinct advantage of using an NLP model is that it can avoid the dimensionality problem because it solves directly the problem without discretizing the decision variables. To use the NLP approach, a real time operation model is specified at first. Then, a multivariate first-order autoregressive model is used to generate a large number of future inflow sequences. The MINOS software package is then used to optimize the problem with each inflow sequence. MINOS can be implemented seemly in the simulation process and can solve the problems without starting values of variables. The number of runs in a simulation is determined by a statistical model, which shows that 500 runs are sufficient. Finally, the expected values and standard deviations of decision variables are tabulated and the distributions of decision variables are plotted. The proposed real time operation model runs once every month. An information-updating scheme is embedded into the simulation and optimization models. For each month, the synthetic streamflows are updated to reflect the most recent hydrological conditions. Besides, the objective function and constraints can be modified if the situation of the system changes.

This dissertation presents a new multiple objective optimization algorithm that is capable of solving for the entire Pareto set in one single optimization run. The multi-objective complex evolution (MOCOM-UA) procedure is based on the following three concepts: (1) population, (2) rank-based selection, and (3) competitive evolution. In the MOCOM-UA algorithm, a population of candidate solutions is evolved in the feasible space to search for the Pareto set. Ranking of the population is accomplished through Pareto Ranking, where all points are successively placed on different Pareto fronts. Competitive evolution consists of selecting subsets of points (including all worst points in the population) based on their ranks and moving the worst points toward the Pareto set using the newly developed multi-objective simplex (MOSIM) procedure. Test analysis on the MOCOM-UA algorithm is accomplished on mathematical problems of increasing complexity and based on a bi-criterion measure of performance. The two performance criteria used are (1) efficiency, as measured by the ability of the algorithm to converge quickly and (2) effectiveness, as measured by the ability of the algorithm to locate the Pareto set. Comparison of the MOCOM-UA algorithm against three multi-objective genetic algorithms (MOGAs) favors the former. In a realistic application, the MOCOM-UA algorithm is used to calibrate the Soil Moisture Accounting model of the National Weather Service River Forecasting Systems (NWSRFS-SMA). Multi-objective calibration of this model is accomplished using two bi-criterion objective functions, namely the Daily Root Mean Square-Heteroscedastic Maximum Likelihood Estimator (DRMS, HMLE) and rising limb-falling limb (RISE, FALL) objective functions. These two multi-objective calibrations provide some interesting insights into the influence of different objectives in the location of final parameter values as well as limitations in the structure of the NWSRFS-SMA model.

<p> This dissertation is devoted to solving general mixed integer optimization problems. Our main focus is understanding and developing strong cutting planes for mixed integer linear programs through Gomory and Johnson's <i> k</i>-dimensional infinite group relaxation. Each cut generated from this problem has an associated function, and among the strongest are extreme functions. For <i>k</i>=1 , we give an algorithm for testing the extremality of piecewise linear (possibly discontinuous) functions with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically for deciding extremality in this important class of minimal valid functions. We extend this algorithm to a large class of functions for <i>k </i>= 2 and develop theory for a more general result for <i>k</i> &ge; 2. For the <i>k</i>-dimensional infinite group relaxation, we prove that any minimal valid function that is continuous piecewise linear with at most <i>k</i>+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for <i>k</i>=1, and Cornu&eacute;jols and Molinaro for <i>k</i>=2. </p><p> We also contribute to the understanding of cutting plane closures for mixed integer programs. Cutting planes derived from maximal lattice-free convex sets have recently been studied intensely by the integer programming community. Although some fairly general results were obtained by Andersen, Louveaux and Weismantel, and later by Averkov, some basic questions remain unresolved. We show that when the number of integer variables is two the triangle closure is a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of our proof are also used to refine Cornu&eacute;jols and Margot's necessary conditions identifying valid inequalities as facet-defining and to obtain polynomial complexity results concerning the mixed integer hull. </p><p> Finally, we study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorithm, which is attributed to Heinz. This improvement is achieved by applying a new modern Lenstra-type algorithm, finding optimal ellipsoid roundings, and considering sparse encodings of polynomials. Our algorithm achieves a time-complexity of 2^{2nlog₂(n) + O(n)} in terms of the dimension <i>n</i>.</p>

Over the years, mathematical models have become increasingly complex. Rarely can we accurately model a process using only linear or quadratic functions. Instead, we must employ complicated routines written in some programming language. At the same time, most algorithms rely on the ability to exploit structural features within a model. Thus, our ability to compute with a model directly relates to our ability to analyze it. Mathematical programs exemplify these difficult modeling issues. Our desire to accurately model a process is mediated by our ability to solve the resulting problem. Nonetheless, many problems contain hidden structural features that, when identified, allow us to transform the problem into a more computable form. Thus, we must develop methods that not only recognize these hidden features, but exploit them by transforming one problem formulation into another. We present a new domain specific language for mathematical programming. The goal of this language is to develop a system of techniques that allow us to automatically determine the structure of a problem then transform it into a more desirable form. Our technical contribution to this area includes the grammar, type system, and semantics of such a language. Then, we use these tools to develop a series of transformations that manipulate the mathematical model.

This thesis introduces and analyzes a family of trust-region interior-point (TRIP) reduced sequential quadratic programming (SQP) algorithms for the solution of minimization problems with nonlinear equality constraints and simple bounds on some of the variables. These nonlinear programming problems appear in applications in control, design, parameter identification, and inversion. In particular they often arise in the discretization of optimal control problems. The TRIP reduced SQP algorithms treat states and controls as independent variables. They are designed to take advantage of the structure of the problem. In particular they do not rely on matrix factorizations of the linearized constraints, but use solutions of the linearized state and adjoint equations. These algorithms result from a successful combination of a reduced SQP algorithm, a trust-region globalization, and a primal-dual affine scaling interior-point method. The TRIP reduced SQP algorithms have very strong theoretical properties. It is shown in this thesis that they converge globally to points satisfying first and second order necessary optimality conditions, and in a neighborhood of a local minimizer the rate of convergence is quadratic. Our algorithms and convergence results reduce to those of Coleman and Li for box-constrained optimization. An inexact analysis is presented to provide a practical way of controlling residuals of linear systems and directional derivatives. Complementing this theory, numerical experiments for two nonlinear optimal control problems are included showing the robustness and effectiveness of these algorithms. Another topic of this dissertation is a specialized analysis of these algorithms for equality-constrained optimization problems. The important feature of the way this family of algorithms specializes for these problems is that they do not require the computation of normal components for the step and an orthogonal basis for the null space of the Jacobian of the equality constraints. An extension of More and Sorensen's result for unconstrained optimization is presented, showing global convergence for these algorithms to a point satisfying the second-order necessary optimality conditions.

Currently, the Houston Independent School District has approximately 175 elementary schools providing education for more than 110,000 students. A question of major logistical impact is how to assign students to schools in an optimal fashion. Many conventional methods exist to deal with such problems, yet the sheer magnitude of the HISD student assignment problem presents new computational challenges which must be dealt with effectively if the problem is to be solved. This monograph examines issues related to finding the solution of school/student assignment problems on a workstation taken from real problem data giving rise to problems with over 20 million variables and 110,000 constraints.

This work concerns efficiently solving a class of nonlinear integer programming problems: min $\{f(x)$: $x \in \{0,1\}\sp{n}\}$ where $f(x)$ is a general nonlinear function. The notion of subgradient for the objective function is introduced. A necessary and sufficient condition for the optimal solution is constructed. And a new algorithm, called the subgradient algorithm, is developed. The algorithm is an iterative procedure, searching for the solution iteratively among feasible points, and in each iteration, generating the next iterative point by solving the problem for a local piecewise linear model of the original problem which is constructed with supporting planes for the objective function at a set of feasible points. Special continuous optimization techniques are used to compute the supporting planes. The problem for each local piecewise linear model is solved by solving an equivalent linear integer program. The fundamental theory for the new approach is built and all related mathematical proofs and derivations such as proofs for convergence properties, the finiteness of the algorithm, as well as the correct formulation of the subproblems are presented. The algorithm is parallelized and implemented on parallel distributed-memory machines. The preliminary numerical results show that the algorithm can solve test problems effectively. To implement the subgradient algorithm, a parallel software system written in EXPRESS C is developed. The system contains a group of parallel subroutines that can be used for either continuous or discrete optimization such as subroutines for QR, LU and Cholesky factorizations, triangular system solvers and so on. A sequential implementation of the simplex algorithm for linear programming also is included. Especially, a parallel branch-and-bound procedure is developed. Different from directly parallelizing the sequential binary branch-and-bound algorithm, a parallel strategy with multiple branching is used for good processor scheduling. Performance results of the system on NCUBE are given.