Reoptimization in Interior-Point Methods with Application to Integer Programming

This thesis examines current reoptimization techniques for interior-point methods available in the literature and studies their efficacy in a branch-and-bound framework for 0/1 mixed integer programming problems. This work is motivated by the observation that there are instances of integer programming problems where each individual linear program generated in a branch-and-bound tree can be solved much faster by an interior-point algorithm than by a simplex algorithm, in spite of the fact that effective "warm-start" techniques are available for the latter but not for the former. Because of many unresolved issues surrounding effective reoptimization techniques for interior-point methods, interior-point algorithms have not been commonly used as linear programming solvers in a branch-and-bound framework.

In this work, we identify and examine a number of key factors that may affect and even preclude effective reoptimization for interior-point algorithms in the branch-and-bound framework, including change in optimal partition, distance to optimality, and primal infeasibility. We conclude that even though various "warm-start" techniques are capable of reducing the reoptimization cost to some extent, for certain problem instances a rapid reoptimization cannot always be expected from interior-point methods due to their inherent limitations.

Continued research is needed in the direction of the present study in order to provide comprehensive guidelines for the most effective utilization of interior-point algorithms in a branch-and-bound algorithm.

May 1999

Interior-Point Algorithms for Semidefinite Programming Based on A Nonlinear Programming Formulation

Recently, the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n × n matrix function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed interior point algorithms for solving a special class of linear semidefinite programs.

In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose interior-point algorithms for this type of nonlinear program and establish their global convergence.

December 1999

A Trust-Region Approach to the Regularization of Large-Scale Discrete Ill-Posed Problems

We consider the solution of large-scale least squares problems where the coefficient matrix comes from the discretization of an ill-posed operator and the right-hand size contains noise. Special techniques known as regularization methods are needed to treat these problems in order to control the effect of the noise on the solution. We pose the regularization problem as a trust-region subproblem and solve it by means of a recently developed method for the large-scale trust-region subproblem. We present numerical results on test problems, an inverse interpolation problem with real data, and a model seismic inversion problem with real data.

December 1999

An Overview of HCL 1.0

The Hilbert Class Library (HCL) is a collection of C++ classes which apply object-oriented programming principles to implement mathematical objects such as vectors, linear and nonlinear operators, and functions. HCL provides a convenient environment for implementing algorithms for optimization and linear algebra at a natural, abstract level, without reference to the implementations of data structures, simulators, and other complex, application-specific details. Because coordinate representations, data storage formats, and other domain-specific idiosyncrasies are not entangled in these implementations, the resulting code is reusable across applications of widely varying size and structure.

The design of HCL also results in several very important capabilities, such as the ability to treat very large out-of-core data sets as vector objects, and to manipulate linear operators not defined explicitly by matrices, which distinguish HCL from other object oriented numerics libraries.

October 1999

Implementing Functionals in HCL

(Abstract not available)

October 1999

Solving Semidefinite Programs via Nonlinear Programming, Part II: Interior Point Methods for a Subclass of SDPs

In Part I of this series of papers, we have introduced transformations which convert a large class of linear and nonlinear semidefinite programs (SDPs) into nonlinear optimization problems over "orthants" of the form (R^n)++ × R^N, where n is the size of the matrices involved in the problem and N is a nonnegative integer dependent upon the specific problem. In doing so, we have effectively reduced the number of variables and constraints. In this paper, we develop interior point methods for solving a subclass of the transformable linear SDP problems where the diagonal of a matrix variable is given. These new interior point methods have the advantage of working entirely within the space of the transformed problem while still maintaining close ties with the original SDP. Under very mild and reasonable assumptions, global convergence of these methods is proved.

October 1999

Implementing Nonlinear Operators in HCL

(Abstract not available)

September 1999

Concavity Cuts for Disjoint Bilinear Programming

We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linear maxmin reformulations, leading to two sets of concavity cuts. We first examine the depth of these cuts by considering the assumptions on the boundedness of the feasible regions of both maxmin and bilinear formulations. We next propose a branch and bound algorithm which makes use of concavity cuts. We also present a procedure that eliminates degenerate solutions. Extensive computational experiences are reported. Sparse problems with up to 500 variables in each disjoint set and 100 constraints, and dense problems with up to 60 variables again in each set and 60 constraints are solved in reasonable computing times.

September 1999

Selective Search for Global Optimization of Zero or Small Residual Least-Squares Problems: A Numerical Study

In this paper, we consider searching for global minima of zero or small residual, nonlinear least-squares problems. We propose a selective search approach based on the concept of selective minimization recently introduced in Zhang et al[14]. To test the viability of the proposed approach, we construct a simple implementation using a Levenberg-Marquardt type method combined with a multi-start scheme, and compare it with several existing global optimization techniques. Numerical experiments were performed on zero residual nonlinear least-squares problem chosen from structural biology applications as well as from the literature. On the problems of larger sizes, the performance of the new approach compared favorably with the other tested methods, indicating that the new approach is promising for the intended class of problems.

September 1999

A New Matrix-Free Algorithm for the Large-Scale Trust-Region Subproblem

We present a matrix-free algorithm for the large-scale trust-region subproblem. Our algorithm relies on matrix-vector products only and does not require matrix factorizations. We recast the trust-region subproblem as a parameterized eigenvalue problem and compute an optimal value for the parameter. We then find the optimal solution of the trust-region subproblem from the eigenvectors associated with two of the smallest eigenvalues of the parameterized eigenvalue problem corresponding to the optimal parameter. The new algorithm uses a different interpolating scheme than existent methods and introduces a unified iteration that naturally includes the so-called hard case. We show that the new iteration is well defined and convergent at a superlinear rate. We present computational results to illustrate convergence properties and robustness of the method.

September 1999

Analysis of Inexact Trust-Region SQP Algorithms

In this paper we study the global convergence behavior of a class of composite-step trust-region SQP methods that allow inexact problem information. The inexact problem information can result from iterative linear systems solves within the trust-region SQP method or from approximations of first-order derivatives. Accuracy requirements in our trust-region SQP methods are adjusted based on feasibility and optimality of the iterates. In the absence of inexactness our global convergence theory is equal to that of Dennis, El-Alem, Maciel (SIAM J. Optim. 7 (1997), 177-207). If all iterates are feasible, i.e., if all iterates satisfy the equality constraints, then our results are related to the known convergence analyses for trust-region methods with inexact gradient information for unconstrained optimization.

September 1999

[SIAM J. Optim. 12 (2001), no. 2, 283-302.]

Solving Semidefinite Programs via Nonlinear Programming, Part I: Transformations and Derivatives

In this paper, we introduce transformations that convert a large class of linear and/or nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems over "orthants" of the form (R^n)++ × R^N, where n is the size of the matrices involved in the problem and N is a nonnegative integer dependent upon the specific problem. For example, in the case of the SDP relaxation of a MAXCUT problem, N is zero and n, the number of variables of the resulting nonlinear optimization problem, is the number of vertices in the underlying graph. The class of transformable problems includes most, if not all, instances of SDP relaxations of combinatorial optimization problems with binary variables, as well as other important SDP problems. We also derive formulas for the first and second derivatives of the objective function of the resulting nonlinear optimization problem, hence enabling the effective application of existing nonlinear optimization techniques to the solution of large-scale SDP problems.

September 1999

Properties of A Class of Preconditioners for Weighted Least Squares Problems

A sequence of weighted linear least squares problems arises from interior-point methods for linear programming where the changes from one problem to the next are the weights and the right hand side. One approach for solving such a weighted linear least squares problem is to apply a preconditioned conjugate gradient method to the normal equations where the preconditioner is based on a low-rank correction to the Cholesky factorization of a previous coefficient matrix. In this paper, we establish theoretical results for such preconditioners that provide guidelines for the construction of preconditioners of this kind. We also present preliminary numerical experiments to validate our theoretical results and to demonstrate the effectiveness of this approach.

April 1999 (revised July 1999)

The Sphere of Convergence of Newton's Method on Two Equivalent Systems from Nonlinear Programming

We study a local feature of a Newton logarithmic barrier function method and a Newton primal-dual interior-point method. In particular, we study the radius of the sphere of convergence of Newton's method on two equivalent systems associated with the two aforementioned interior-point methods for nondegenerate problems in inequality contrained optimization problems. Our theoretical and numerical results are clearly in favor of using Newton primal-dual methods for solving the optimization problem. This work is an extension of the authors' earlier work [10] on linear programming problems.

April 1999

A Fast Newton's Algorithm for Entropy Maximization in Phase Determination

A long-standing problem in X-ray crystallography, known as the phase problem, is to determine the phases for a large set of complex variables, called the structure factors of the crystal, given their magnitudes obtained from X-ray diffraction experiments. We introduce a statistical phase estimation approach to the problem. This approach requires solving a special class of entropy maximization problems repeatedly to obtain the joint probability distribution of the structure factors. The entropy maximization problem is a semi-infinite convex program, which can be solved in a finite dual space by using a standard Newton's method. The Newton's method converges quadratically, but is costly in general, requiring O(n³) floating point operations in every iteration, where n is the number of variables. We present a fast Newton's algorithm for solving the entropy maximization problem. The algorithm requires only O(n log n) floating point operations for each of its iterates, yet has the same convergence rate as the standard Newton. We describe the algorithm and discuss related computational issues. Numerical results on simple test cases will also be presented to demonstrate the behavior of the algorithm.

Key words: X-ray crystallography, protein structure determination, entropy maximization, Newton's method, Fourier transform and convolution.

May 1999 (revised July 2000)

The Bayesian Statistical Approach to the Phase Problem in Protein X-ray Crystallography

We review a Bayesian statistical approach to the phase problem in protein X-ray crystallography. We discuss the mathematical foundations and the computational issues. The introduction to the theory and the algorithms does not require strong background in X-ray crystallography and related physical disciplines.

April 1999

On Convergence of Minimization Methods: Attraction, Repulsion and Selection

In this paper, we introduce a rather straightforward but fundamental observation concerning the convergence of the general iteration process

x^(k+1) = x^k - alpha(x^k) [B(x^k)]^(-1) grad­f(x^k)

for minimizing a function f(x). We give necessary and sufficient conditions for a stationary point of f(x) to be a point of strong attraction of the iteration process. We will discuss various ramifications of this fundamental result, particularly for nonlinear least squares problems.

March 1999 (revised August 1999)

A Computational Study of Vehicle Routing Applications

This thesis examines three specific routing applications. In the first model, the scheduling of home health care providers from their homes, to a set of patients, and then back to their respective homes, is performed both heuristically and optimally for very small instances. The problem is complicated by the presence of multiple depots, time windows, and the scheduling of lunch breaks. It is shown that the problem can be formulated as a mixed integer programming problem and, in very small instances, solved to optimality with a branch-and-cut procedure. To obtain solutions for larger instances, though, a heuristic is shown to have more success.

The second application considers the vehicle routing problem with time windows, or VRPTW. The vehicle routing problem involves finding a set of routes starting and ending at a single depot that together visit a set of customers. In the VRPTW there is an additional constraint requiring that each customer must be visited within a given time window. The best known solution procedures for solving the VRPTW use a set partitioning model with column generation. Within this framework, we present a new approach for generating valid inequalities, specifically k-path cuts, to improve the linear programming relaxation. Computational results are given for the standard library of test instances. In particular, the results include solutions for ten previously unsolved instances.

The final application concerns the less-than-truckload, or LTL, trucking industry. An LTL carrier primarily handles shipments that are significantly smaller than the size of a tractor-trailer. Savings are achieved by consolidating shipments into loads at regional terminals and transporting these loads from terminal to terminal. The strategic load plan determines how to route the flow of consolidated loads from origin terminals to destination terminals cost effectively and allowing for certain service standards. To find good solutions to this problem, we apply a dual-ascent procedure to a related uncapacitated network design problem to obtain computational results for three different companies.

May 1999

Remarks on Compactness in the Formation of Fine Structures

(Abstract not available)

1999

All Stationary Points of Differential Semblance Are Asymptotic Global Minimizers: Layered Acoustics

Differential semblance velocity estimators have well-defined and smooth high frequency asymptotics. A version appropriate for analysis of CMP gathers and layered acoustic models has no secondary minima. Its structure suggests an approach to optimal parametrization of velocity models.

1999

Coherent Noise Suppression in Velocity Inversion

Data components with well-defined moveout other than primary reflections are sometimes called coherent noise. Coherent noise makes velocity analysis ambiguous, since no single velocity function explains incompatible moveouts simultaneously. Contemporary data processing treats the control of coherent noise influence on velocity as an interpretive step. Dual regularization theory suggests an alternative, automatic inversion algorithm for suppression of coherent noise when primary reflection phases dominate the data. Experiments with marine data illustrate the robustness and effectiveness of the algorithm.

1999

Extremal Regularization

Extremal regularization finds a model fitting the data to a specified tolerance, and additionally minimizing an auxiliary criterion. It provides relative model/data space weights when no statistical information about the model or data is available other than an estimate of noise level. A version of the More¢-Hebden algorithm using conjugate gradients to solve the various linear systems implements extremal regularization for large scale inverse problems. A deconvolution application illustrates the possibilities and pitfalls of extremal regularization in the linear case.

1999

An Adaptive Finite Difference Method for Traveltime and Amplitude

The eikonal equation with point source is difficult to solve with high order accuracy because of the singularity of the solution at the source. All the formally high order schemes turn out to be first order accurate without special treatment of this singularity. Adaptive upwind finite difference methods based on high order ENO (Essentially NonOscillatory) Runge-Kutta difference schemes for the paraxial eikonal equation overcome this difficulty. The method controls error by automatic grid refinement and coarsening based on an a posteriori error estimation. It achieves prescribed accuracy at far lower cost than fixed grid methods. Reliable auxiliary quantities, such as take-off angle and geometrical spreading factor, are by-products.

1999

Finding Tours in the TSP

The traveling salesman problem, or TSP for short, is easy to state: given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. The travel costs are symmetric in the sense that traveling from city X to city Y costs just as much as traveling from Y to X; the "way of visiting all the cities" is simply the order in which the cities are visited. In this report we consider the relaxed version of the TSP where we ask only for a tour of low cost. This is a preliminary version of a chapter of planned monograph on the TSP.

May 1999

A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows

In the vehicle routing problem with time windows a number of identical vehicles must be routed to and from a depot to cover a given set of customers, each of whom has a specified time interval indicating when they are available for service. Each customer also has a known demand, and a vehicle may only serve the customers on a route if the total demand does not exceed the capacity of the vehicle. The most effective solution method proposed to date for this problem is due to Kohl, Desrosiers, Madsen, Solomon, and Soumis. Their algorithm uses a cutting-plane approach followed by a branch-and-bound search with column generation, where the columns of the LP relaxation represent routes of individual vehicles. We describe a new implementation of their method, using Karger's randomized minimum-cut algorithm to generate cutting planes. The standard benchmark in this area is a set of 87 problem instances generated in 1984 by M. Solomon; making use of parallel processing in both the cutting-plane generation and the branch-and-bound search, we solve 80 of these examples, including 10 that were previously unsolved in the literature. Our parallel implementation utilizes the Tread Marks distributed shared memory system.

May 1999

Strategic Load Planning for Less-Than-Truckload Trucking

Less-than-truckload trucking represents a portion of the motor carrier industry in which the shipments to be sent on trucks do not completely fill a 45,000 lb. volume tractor-trailer. Typically, the freight in each shipment weighs under 10,000 lbs., with a large majority falling under 1000 lbs. Since each shipment does not fill a truck, significant savings can be achieved by consolidating shipments into loads at regional terminals and transporting these loads from terminal to terminal. The goal of the strategic load planning problem is to determine how to route the flow of consolidated loads from origin terminals to destination terminals cost effectively and allowing for certain service standards. The actual gathering of these shipments at the origin terminal and the distribution of them from the destination terminal is handled in a separate problem commonly referred to as the pick-up and delivery problem. This overall method of distribution requires a network of terminals, the design of which is closely related to many classic network design problems. We have built a software system which, when given the appropriate data concerning a company's needs and past routing decisions, will build a network to solve the strategic load planning problem. The empirical results, based on real data from trucking companies, indicate that our system does a very credible job of building an efficient network.

June 1999

Pattern Search Algorithms for Mixed Variable Programming

Many engineering optimization problems involve a special kind of discrete variable that can be represented by a number, but this representation has no significance. Such variables arise when a decision involves some situation like a choice from an unordered list of categories. This has two implications: The standard approach of solving problems with continuous relaxations of discrete variables is not available, and the notion of local optimality must be defined through a user-specified set of neighboring points. We present a class of direct search algorithms to provide limit points that satisfy some appropriate necessary conditions for local optimality for such problems. We give a more expensive, version of the algorithm that guarantees additional necessary optimality conditions. A small example illustrates the differences between the two versions. A real thermal insulation system design problem illustrates the efficacy of the user controls for this class of algorithms.

Key words: pattern search algorithm, convergence analysis, bound constrained optimization, mixed variable programming, derivative-free optimization.

May 1999 (revised February 2000)

A Branch and Cut Algorithm for Nonconvex Quadratically Constrained Quadratic Programming

We present a branch and cut algorithm that yields in finite time, a globally epsilon-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node of the tree is flexible enough to be used at other nodes. Computational results are reported. Some problems of the literature are solved, for the first time with a proof of global optimality.

January 1999

Go to 1998 reports

Go to 2000 reports