There has been limited success with parallel implementations of both the simplex method and interior point methods for solving real-world linear programs. Experience with a parallel implementation of CPLEX, a state of the art implementation of the simplex method, on an Intel distributed-memory multiprocessor machine will be described. We will exploit the structure of the class of problems arising from airline crew scheduling. A particular instance with 12,753,313 variables will be studied. This instance is too large to fit on current sequential machines in standard linear programming data structures. We will show how our implementation exploits both distributed memory and parallelism and allows the full problem to be kept in memory. Finally, we will discuss algorithmic ideas that our implementation affords us and show results for a variant of the greatest decrease algorithm, an idea suggested many years ago but never tested on linear programming problems of significant size.

Removing the minimum number of vertices or points from a square lattice such that no square path exists is known as the square path problem. Finding this number as the size of the lattice increases is not so trivial. Results provided by Erdos-Posa and Bienstock-Dean provides an upper bound for eliminating all cycles from a planar graph but sheds little light on the case of the square lattice. This paper provides several values for the minimum number of vertices needed to be removed such that no square path exists.

In the first part of this research we consider a linesearch globalization of the local primal-dual interior-point Newton's method for nonlinear programming recently introduced by El-Bakry, Tapia, Tsuchiya, and Zhang. Our linesearch uses a new merit function and a new notion of centrality. We establish a global convergence theory and present rather promising numerical experimentation. In the second part, we consider an inexact Newton's method implementation of the linesearch globalization algorithm given in the first part. This inexact method is designed to solve large scale nonlinear programming problems. The iterative solution technique uses an orthogonal projection-Krylov subspace scheme to solve the highly indefinite and nonsymmetric linear systems associated with nonlinear programming. Our iterative projection method maintains linearized feasibility with respect to both the equality constraints and complementarity condition. This guarantees that in each iteration the linear solver generates a descent direction, so that the iterative solver is not required to find a Newton step but rather cheaply provides a way to march toward an optimal solution of the problem. This makes the use of a preconditioner inconsequential except near the solution of the problem, where the Newton step is effective. Moreover, we limit the problem to finding a good preconditioner only for the Hessian of the Lagrangian function associated with the nonlinear programming problem plus a positive diagonal matrix. We report numerical experimentation for several large scale problems to illustrate the viability of the method.

A branch-and-bound algorithm for the solution of a class of mixed-integer nonlinear programming problems arising from the field of investment portfolio selection is presented. The problems in this class are characterized by the inclusion of the fixed transaction costs associated with each asset, a constraint that explicitly limits the number of distinct assets in the selected portfolio, or both. Modeling either of these forms of limiting the cost of owning an investment portfolio involves the introduction of binary variables, resulting in a mathematical programming problem that has a nonconvex feasible set. Two objective functions are examined in this thesis; the first is a positive definite quadratic function which is commonly used in the selection of investment portfolios. The second is a convex function that is not continuously differentiable; this objective function, although not as popular as the first, is, in many cases, a more appropriate objective function. To take advantage of the structure of the model, the branch-and-bound algorithm is not applied in the standard fashion; instead, we generalize the implicit branch-and-bound algorithm introduced by Bienstock (3). This branch-and-bound algorithm adopts many of the standard techniques from mixed-integer linear programming, including heuristics for finding feasible points and cutting planes. Implicit branch-and-bound involves the solution of a sequence of subproblems of the original problem, and thus it is necessary to be able to solve these subproblems efficiently. For each of the two objective functions, we develop an algorithm for solving its corresponding subproblems; these algorithms exploit the structure of the constraints and the objective function, simplifying the solution of the resulting linear systems. Convergence for each algorithm is proven. Results are provided for computational experiments performed on investment portfolio selection problems for which the cardinality of the universe of assets available for inclusion in the selected portfolio ranges in size from 52 to 1140.

This thesis describes a flexible framework for abstract numerical algorithms which treats algorithms as objects and makes them reusable, composable, and modifiable. These algorithm objects are implemented using the Rice Vector Library (RVL) interface, decoupling the algorithmic code from the details of linear algebra and calculus in Hilbert Space. I made many improvements to the RVL design, including abstract return types for reductions. These improvements allowed me to demonstrate the breadth of this design by incorporating semantically similar objects from other packages which had significant syntatic differences to the RVL objects. By adapting other libraries, I gain access to a variety of tools, including parallel linear algebra implementations. The benefits of the algorithm framework can be seen when abstract numerical algorithms are coupled with parallel simulators without needing to modify either the algorithm or the simulator.

Two classes of primal-dual interior-point methods for nonlinear programming are studied. The first class corresponds to a path-following Newton method formulated in terms of the nonnegative variables rather than all primal and dual variables. The centrality condition is a relaxation of the perturbed Karush-Kuhn-Tucker condition and primarily forces feasibility in the constraints. In order to globalize the method using a linesearch strategy, a modified augmented Lagrangian merit function is defined in terms of the centrality condition. The second class is the Quasi-Newton interior-point methods. In this class the well known Boggs-Tolle-Wang characterization of Q-superlinear convergence for Quasi-Newton method for equality constrained optimization is extended. Critical issues in this extension are; the choice of the centering parameter, the choice of the steplength parameter, and the choice of the primary variables.

This thesis is concerned with the study of pseudospectral discretizations of optimal control problems governed by ordinary differential equations and with their application to the solution of the International Space Station (ISS) momentum dumping problem. Pseudospectral methods are used to transcribe a given optimal control problem into a nonlinear programming problem. Adjoint estimates are presented and analyzed that provide approximations of the original adjoint variables using Lagrange multi pliers corresponding to the discretized optimal control problem. These adjoint estimations are derived for a broad class of pseudospectral discretizations and generalize the previously known adjoint estimation procedure for the Legendre pseudospectral discretization. The error between the desired solution to the infinite dimensional optimal control problem and the solution computed using pseudospectral collocation and nonlinear programming is estimated for linear-quadratic optimal control problems. Numerical results are given for both linear-quadratic and nonlinear optimal control problems. The Legendre pseudospectral method is applied to formulations of the ISS momentum dumping problem. Computed solutions are verified through simulations using adaptive higher order integration of the system dynamics.

No description available.

No description available.

No description available.