Solving Real-World Linear Programs: A Decade and More of Progress
Robert E. Bixby

This paper is an invited contribution to the 50th anniversary issue of the journal Operations Research, published by the Institute for Operations Research and the Management Sciences (INFORMS). It describes one person's perspective on the development of computational tools for linear programming. The paper begins with a short, personal history, followed by historical remarks covering the some 40 years of linear-programming developments that predate my own involvement in this subject. It concludes with a more detailed look at the evolution of computational linear programming since 1987.

October 2001

On the stationary points of the seismic reflection tomography and differential semblance functionals in laterally homogeneous media
Christiaan C. Stolk

This paper concerns the determination of the reference medium (velocity model) in reflection seismology by optimization. Several objective functionals have been proposed, that attain their minimum or maximum at the correct medium. We study the local minima of two of these, the differential semblance and reflection tomography functionals, both depending on the traveltimes of reflected waves. It is assumed that the medium contains a single, horizontal reflector, and that it depends smoothly on the vertical coordinate above the reflector. We show that stationary points of both functionals are global minima when the medium above the reflector is non-constant. For reflection tomography we study the Hessian at a constant medium to show that all local minima are in fact global minima. To obtain these results we study the linearization of the map from medium properties to the traveltime of reflected waves around a non-constant medium.

September 2001

Microlocal analysis of the scattering angle transform
Christiaan C. Stolk

The goal of seismic imaging is to map single reflection seismic data to an image of a medium parameter, ie. a reconstruction of the singularities in the medium parameter up to a pseudodifferential factor. Given a smooth model of the medium (background medium), satisfying certain conditions, there is a Fourier integral operator (FIO) mapping seismic data to an image. Under more restrictive conditions the data can be mapped to a family of images, each depending on a different subset of the data. This mapping is used in the determination of the background medium. The canonical relations of these operators consist of data from reflected bicharacteristics in the background medium. When several rays (projections of the bicharacteristics on the base space) connect an acquisition point with a scattering point (multipathing), the conditions for imaging using subsets of data are in general violated. In the geophysical literature scattering angle transforms have been proposed to yield image families in the presence of multipathing. It has been conjectured that an integral operator related to the Kirchhoff migration operator maps seismic data to a family of images. We show that this conjecture is false. The Kirchhoff type angle transform maps seismic data to a sum of a correct image and possible artifacts, ie. singularities in the image that do not correspond to singularities in the medium. We give an explicit example in which such artifacts are present.

July 2001

Comparison of two sets of first-order conditions as bases of interior-point Newton methods for optimization with simple bounds
Diane C. Jamrog, Richard A. Tapia, and Yin Zhang

In this paper, we compare the behavior of two Newton interior-point methods derived from two different first-order necessary conditions for the same nonlinear optimization problem with simple bounds. One set of conditions was proposed by Coleman and Li; the other is the standard KKT set of conditions. We discuss a perturbation of the CL conditions for problems with one-sided bounds and the difficulties involved in extending this to problems with general bounds. We study the numerical behavior of the Newton method applied to the systems of equations associated with the unperturbed and perturbed necessary conditions. Preliminary numerical results for convex quadratic objective functions indicate that, for this class of problems, Newton's method based on the perturbed KKT formulation appears to be the most robust.

Key words: optimization with simple bounds, first-order necessary conditions, interior-point Newton methods.

June 2001

Optimal Control of Unsteady Viscous Flows
S. Scott Collis, Kaveh Ghayour, Matthias Heinkenschloss, Michael Ulbrich, and Stefan Ulbrich

This paper is concerned with the formulation and numerical solution of a class of optimal boundary control problems governed by the unsteady two-dimensional compressible Navier-Stokes equations. Fundamental issues including the choice of the control space and the associated regularization term in the objective function, adjoint computations, as well as the impact of the inner product in the control space on the gradient computation are discussed. Numerical results are presented for a model problem consisting of two counter-rotating viscous vortices above an infinite wall which, due to the self-induced velocity field, propagate downward and interact with the wall. The wall boundary control is the temporal and spatial distribution of wall-normal velocity. Different objectives and different control regularizations are studied.

August 2001

On Numerical Solution of the Maximum Volume Ellipsoid Problem
Yin Zhang and Liyan Gao

In this paper we study practical solution methods for finding the maximum-volume ellipsoid inscribing a given full-dimensional polytope in R ⁿ defined by a finite set of affine inequalities. Our goal is to design a general-purpose algorithmic framework that is reliable and efficient in practice. To evaluate the merit of a practical algorithm, we consider two key factors: the computational cost per iteration and the typical number of iterations required for convergence. In addition, numerical stability is also an important factor. We investigate some new formulations upon which we build primal-dual type, interior-point algorithms, and provide theoretical justifications for the proposed formulations and algorithmic framework. Extensive numerical experiments have shown that one of the new algorithms should be the method of choice among the tested algorithms.

August 2001

A Geometric Build-Up Algorithm for Soving the Molecular Distance Geometry Problem with Sparse Distance Data
Qunfeng Dong and Zhijun Wu

Nuclear magnetic resonance (NMR) structure modeling usually produces a sparse set of inter-atomic distances in protein. In order to calculate the three-dimensional structure of protein, current approaches need to estimate all other "missing" distances to build a full set of distances. However, the estimation step is costly and prone to introducing errors. In this report, we describe a geometric build-up algorithm for solving protein structure by using only a sparse set of inter-atomic distances. Such a sparse set of distances can be obtained by combining NMR data with our knowledge on certain bond lengths and bond angles. It can also include confident estimations on some "missing" distances. Our algorithm utilizes a simple geometric relationship between coordinates and distances. The coordinates for each atom are calculated by using the coordinates of previously determined atoms and their distances. We have implemented the algorithm and tested it on several proteins. Our results showed that our algorithm successfully determined the protein structures with sparse sets of distances. Therefore, our algorithm reduces the need of estimating the "missing" distances and promises a more efficient approach to NMR structure modeling.

Key words: molecular distance geometry, protein structure determination, numerical linear algebra and optimization.

August 2001

A Linear-Time Algorithm for Solving the Molecular Distance Geometry Problem with Exact Inter-Atomic Distances
Qunfeng Dong and Zhijun Wu

We describe a linear-time algorithm for solving the molecular distance geometry problem with exact distances between all pairs of atoms. This problem needs to be solved in every iteration of general distance geometry algorithms for protein modeling such as the EMBED algorithm by Crippen and Havel. However, previous approaches to the problem rely on decomposing a distance matrix or minimizing an error function and require O(n²) to O(n³) floating point operations. The linear-time algorithm will provide a much more efficient approach to the problem, especially in large-scale applications. It exploits the problem structure and hence is able to identify infeasible data more easily as well.

Key words: molecular distance geometry, protein structure determination, numerical linear algebra and optimization.

June 2001

Solving the Double Digestion Problem as a Mixed-Integer Linear Program
Zhijun Wu and Yin Zhang

The double digestion problem for DNA restriction mapping is known to be NP-complete. Several approaches to the problem have been used including exhaustive search, simulated annealing, branch-and-bound. In this paper, we consider a mixed-integer linear programming formulation of the problem and show that with this formulation the problem can be solved efficiently to a fairly large size using state-of-the-art integer programming techniques. In particular, we present computational results obtained by using the CPLEX mixed-integer linear programming software on a set of randomly generated, large-scale double digestion problems.

Key words: DNA sequencing, restriction mapping, double digestion, NP-complete problems, mixed-integer linear programming.

August 2001

A Computational Study of a Gradient-Based Log-Barrier Algorithm for a Class of Large-Scale SDPs
Samuel Burer, Renato D. C. Monteiro, and Yin Zhang

The authors of this paper recently introduced a transformation that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, they proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints.

June 2001

A modified low-rank Smith method for large-scale Lyapunov equations
A. C. Antoulas, D. C. Sorensen, and S. Gugercin

In this note we present a modified cyclic low-rank Smith method to compute low-rank approximations to solutions of Lyapunov equations arising from large-scale dynamical systems. Unlike the original cyclic low-rank Smith method introduced by Penzl in [18], the number of the columns in the approximate solutions does not necessarily increase at each step. The number of columns required by the modified method is usually much lower than the original cyclic low-rank Smith method. The modified method never requires more columns than the original. Upper bounds are established for the errors in the low-rank approximate solutions and also for the errors in the resulting approximate Hankel singular values. Numerical results are given to verify the efficiency and accuracy of the new algorithm.

May 2001

On the decay rate of Hankel singular values and related issues
A. C. Antoulas, D. C. Sorensen, and Y. Zhou

This paper investigates the decay rate of the Hankel singular values of linear dynamical systems. This issue is of considerable interest in model reduction by means of balanced truncation, for instance, since the sum of the neglected singular values provides an upper bound for an appropriate norm of the approximation error. The decay rate involves a new set of invariants associated with a linear system, which are obtained by evaluating a modified transfer function at the poles of the system. These considerations are equivalent to studying the decay rate of the eigenvalues of the product of the solutions of two Lyapunov equations. The related problem of determining the decay rate of the eigenvalues of the solution to one Lyapunov equation will also be addressed. Very often these eigenvalues like the Hankel singular values, are decaying rapidly. This fact has motivated the development of several algorithms for computing low rank approximate solutions to Lyapunov equations. However, until now, conditions assuring rapid decay have not been well understood. Such conditions are derived here by relating the solution to a numerically low rank Cauchy matrix determined by the poles of the system. Bounds explaining rapid decay rates are obtained under some mild conditions.

May 2001

On the Matrix Cuts of Lovász and Schrijver and their use in Integer Programming
Sanjeeb Dash

An important approach to solving many discrete optimization problems is to associate the discrete set (over which we wish to optimize) with the 0-1 vectors in a given polyhedron and to derive linear inequalities valid for these 0-1 vectors from a linear inequality system defining the polyhedron. Lovász and Schrijver (1991) described a family of operators, called the matrix-cut operators, which generate strong valid inequalities, called matrix cuts, for the 0-1 vectors in a polyhedron. This family includes the commutative, semidefinite and division operators; each operator can be applied iteratively to obtain, in n iterations for polyhedra in n-space, the convex hull of 0-1 vectors.

We study the complexity of matrix-cut based methods for solving 0-1 integer linear programs. We first prove bounds on the (rank) number of iterations required to obtain the integer hull. We show that the upper bound of n, mentioned above, can be attained in the case of the semidefinite operator, answering a question of Goemans. We also determine the semidefinite rank of the standard linear relaxation of the traveling salesman polytope up to a constant factor. We study the use of the semidefinite operator in solving numerical instances and present results on some combinatorial examples and also on a few instances from the MIPLIB test set. Finally, we examine the lengths of cutting-plane proofs based on matrix cuts. We answer a question of Pudlák on such proofs, and prove an exponential lower bound on the length of cutting-plane proofs based on one class of matrix cuts.

March 2001

On Characterizing Graphs with Branchwidth at Most Four
Kymberly Dawn Riggins

There are several ways in which we can characterize classes of graphs. One such way of classifying graphs is by their brachwidth. In working to characterize the class of graphs with brachwidth at most four beta₄ we have found a set of reductions that reduces members of beta₄ to the zero graph. We have also computed several planar members of the obstruction set O_beta₄ for graphs with branchwidth at most four. This thesis will summarize previous results on branchwidth and reveal the previously mentioned new results.

April 2001

Software Components for Simulation and Optimization
Shannon D. Scott

Explicit-time finite-difference approximations to the acoustic wave equation admit data parallelism, in which the problem domain (a grid) is sub-divided among several processors. Communication must take place between the processors to update the inner-domain boundaries after each time step. Overlapped subdomains can defer communication until several time-steps have been taken. We show nonetheless that minimal overlapping produces the fastest run-times.

Complex simulation-driven optimization requires integration of subprograms with widely varying natural data stuctures and levels of abstraction. Component architectures provide an integration method that also alleviates platform and programming incompatibilities. A component architecture built on commodity software packages provided the necessary integration for our acoustic control application.

C++ Expression Templates allow a finite-difference equation, or most any other mathematical operation, to be represented in a more natural form than hand-coded loops, ideally without a loss of efficiency, by deferring the cost of evaluating the expression until assignment. In principle, compilers can optimize the expression as a whole. In practice, our experience suggests that compiler optimization must advance further before expression templates can reach their potential.

April 2001

A Mixed Integer Nonlinear Formulation for Improving Membrane Filtration Water Treatment Plant Design
Erica Zimmer Klampfl

This thesis provides several contributions to the problem of building large-scale membrane filtration water treatment plants needed to meet increasingly stringent drinking water standards. The first contribution is an extension of a small-scale model of membrane filtration water treatment plants to a model that determines building specifications for the needed large-scale plants at a minimum cost. The large-scale model allows choosing a mix of feed and backflush pumps and partitioning the membrane area into more than one array in order to capture design decisions that can greatly reduce the cost. However, these additions to the model change the mathematical formulation from a small nonconvex nonlinear programming problem (NLP) to a large nonconvex mixed integer nonlinear programming problem (MINLP), which is much more difficult to solve.

To address the difficulties associated with solving general nonconvex MINLPs, the second contribution is the development of an algorithm that exploits the structure of the nonconvex MINLP problem and the code written to implement the algorithm. The special structure of our nonconvex MINLP allows the development of a specific algorithm that exploits the structure and allows many benefits over existing methods. The algorithm guarantees termination to local optimizer for the MINLP, requires the solution of a small NLP and a relatively small IP compared to most algorithms that require the solution of a large NLP and a large MILP, requires the solution of an IP instead of an MILP, and requires very few iterations for termination. The MINLP is reformulated so that the algorithm needs only to iteratively solve alternations of an NLP and an integer programming problem (IP).

Finally, we establish design guidelines for building large-scale membrane filtration water treatment plants. These guidelines include suggestions on how to choose an appropriate mix of feed and backflush pumps, how to partition the membrane area for different size plants, and how to estimate costs. Specifically, we show that larger plants can be operated more cost efficiently than smaller plants at higher recoveries and that a more flexible consideration of facility configuation and pump selection may reduce costs for larger plants by approximately 20% per year.

February 2001

The Steepest Descent Minimization of Double-Well Stored Energies Does Not Yield Vectorial Microstructures
Petr Kloucek

We prove that the Steepest Descent algorithm applied to the minimization of total stored energies with rank-one related rotationally symmetric energy wells does not produce relaxing vectorial microstructures with non-trivial Young measures.

March 2001

Projection Methods for Balanced Model Reduction
D. C. Sorensen and A. C. Antoulas

The purpose of this paper is to investigate projection methods for the iterative computation of partially balanced reduced order systems. This approach is both completely automatic once an error tolerance is specified and yields an error bound. This is to be contrasted with existing projection methods, namely PVL (Padé via Lanczos) and rational Krylov, which do not satisfy these properties. Our approach is based on the computation and appoximation of certain system grammians and in particular on the cross grammian.

March 2001

An Efficient Algorithm for Calculating the Heat Capacity of a Large-scale Molecular System
C. Yang, D. W. Noid, B. G. Sumpter, D. C. Sorensen, and R. E. Tuzun

We present an efficient algorithm for computing the heat capacity of a large-scale molecular system. The new algorithm is based on a special Gaussian quadrature whose abscissas and weights are obtained by a simple Lanczos iteration. Our numerical results have indicated that this new computational scheme is quite accurate. We have also shown that this method is at least a hundred times faster than the earlier apporach that is based on esitimating the density of states and integrating with a simple quadrature formula.

February 2001

Approximation of large-scale dynamical systems: An overview
A. C. Antoulas and D. C. Sorensen

In this paper we review the state of affairs in the area of approximation of large-scale systems. We distinguish among three basic categories, namely the SVD-based, the Krylov-based and the SVD-Krylov-based approximation methods. The first two were developed independently of each other and have distinct sets of attributes and drawbacks. The third approach seeks to combine the best attributes of the first two.

February 2001

Go to 2000 reports

Go to 2002 reports