Computational study of a nonhierarchical decomposition algorithm

Optimizing the design of complex ground and flight vehicles involves multiple disciplines and multilayered computer codes stitched together from mostly incompativle disciplinary codes. The application of established, large-scale, optimization algorithms to the complete model is nearly impossible. Hierarchical decompositions are inappropriate for these types of problems and do not parallelize well. Sobieszczanski-Sobieski has proposed a nonhierarchical decomposition strategyfor nonlinear constrained optimization that is naturally parallel. Despite some successes on engineering problems, the algorithm as originally proposed fails on simple two-dimensional quadratic programs. This paper demonstrates the failure of the algorithm for quadratic programs and suggests a number of possible modifications.     

对偶算法的进一步研究

The dual algorithm for minimax problems is further studied in this paper. The resulting theoretical analysis shows that the condition number of the corresponding Hessian of the smooth modified Lagrange function with changing parameter in the dual algorithm is proportional to the reciprocal of the parameter,which is very important for the efficiency of the dual algorithm. At last ,the numerical experiments are reported to validate the analysis results.     

Computational experience with a globally convergent primal—dual predictor—corrector algorithm for linear programming

Kojima, Megiddo, and Mizuno proved global convergence of a primal—dual algorithm that corresponds to methods used in practice. Here, the numerical efficiency of a predictor—corrector extension of that algorithm is tested. Numerical results are extremely positive, indicating that the safety of a globally convergent algorithm can be obtained at little computational cost. The algorithm is tested on infeasible problems with less success. Finally, the algorithm is applied to a warm started problem, with very encouraging preliminary results.Corresponding author. The research of this author is sponsored by the Air Force Office of Scientific Research, Air Force System Command under Grant AFOSR-92-J0046. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notations thereon.     

A dual decomposition algorithm

Suppose that a large-scale block-diagonal linear programming problem has been solved by the Dantzig—Wolfe decomposition algorithm and that an optimal solution has been attained. Suppose further that it is desired to perform a post-optimality analysis or a complete parametric analysis on the cost-coefficients or the RHS of the linking constraints. Efficient techniques for performing these analyses for the ordinary simplex case have not been easily applied to this case as one operation involves doing a minimizing ratio between all columns of two rows of the tableau. As the columns are not readily known in Dantzig—Wolfe decomposition, other techniques must be used. To date, suggested methods involve solving small linear programs to find these minimizing ratios. In this paper a method is presented which requires solving no linear programs (except possibly in the case of degeneracy of a subproblem) using and utilizing only the information typically stored for Dantzig—Wolfe decomposition.     

Computational experience with the Chow—Yorke algorithm

The Chow—Yorke algorithm is a nonsimplicial homotopy type method for computing Brouwer fixed points that is globally convergent. It is efficient and accurate for fixed point problems. L.T. Watson, T.Y. Li, and C.Y. Wang have adapted the method for zero finding problems, the nonlinear complementarity problem, and nonlinear two-point boundary value problems. Here theoretical justification is given for applying the method to some mathematical programming problems, and computational results are presented.This work was partially supported by NSF Grant MCS 7821337.     

Computational experience with Davidon's least-square algorithm

Computational results are presented for Davidon's new least-square algorithm. Computational experience with this algorithm is reported which motivated the development of a production code version of the algorithm. Several heuristic modifications, which have been added, are described. Fifteen zero-residual test problems have been used in comparing the new production code version with two established versions of the Levenberg-Marquardt algorithm. The production code version of Davidon's least-square algorithm performed faster and used less function evaluations than the Levenberg-Marquardt algorithm in almost every case of the test problems.It is a pleasure to acknowledge and thank M. Thomas, R. & I. Consultant, Western Illinois University Computer Center, for writing the timing routine and taking the time to run the comparison tests on the IBM 360/50. Part of this work was also performed at the Applied Mathematics Division of Argonne National Laboratory under the auspices of the US Energy Research and Development Administration.     

Computational implementation of Fujishige's graph realizability algorithm

Fujishige's PQ-graph algorithm is one of the most computationally efficient algorithms for testing the graph realizability of a (0,1) matrix E. This paper reports the first computational implementation of the algorithm. Computational testing, carried out on randomly generated matrices with up to 500 rows and 9000 columns, validates the almost linear time computational complexity of Fujishige's algorithm.     

A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

Computational study of a column generation algorithm for bin packing and cutting stock problems

This paper reports on our attempt to design an efficient exact algorithm based on column generation for the cutting stock problem. The main focus of the research is to study the extend to which standard branch-and-bound enhancement features such as variable fixing, the tightening of the formulation with cutting planes, early branching, and rounding heuristics can be usefully incorporated in a branch-and-price algorithm. We review and compare lower bounds for the cutting stock problem. We propose a pseudo-polynomial heuristic. We discuss the implementation of the important features of the integer programming column generation algorithm and, in particular, the implementation of the branching scheme. Our computational results demonstrate the efficiency of the resulting algorithm for various classes of bin packing and cutting stock problems. Received October 18, 1996 / Revised version received May 14, 1998?Published online July 19, 1999     

A dual algorithm for minimization of the LLT model

We apply the dual algorithm of Chambolle for the minimization of the LLT model. A convergence theorem is given for the proposed algorithm. The algorithm overcomes the numerical difficulties related to the non-differentiability of the LLT model. The dual algorithm is faster than the original gradient descent algorithm. Numerical experiments are supplied to demonstrate the efficiency of the algorithm.     

On the discrete-time system with server breakdowns: Computational algorithm and optimization algorithm

This paper analyzes a discrete-time Geo/Geo/1 queueing system with the server subject to breakdowns and repairs, in which two different possible types of the server breakdowns are considered. In Type 1, the server may break down only when the system is busy, while in Type 2, the server can break down even if the system is idle. The server lifetimes are assumed to be geometrical and the server repair times are also geometric distributions. We model this system by the level-dependent quasi-birth-death (QBD) process and develop computation algorithms of the stationary distribution of the number of customers in the system using the matrix analytic method. The search algorithm for parameter optimization based on a cost model is developed and performed herein.     

A dual algorithm for minimax problems

In this paper, a dual algorithm, based on a smoothing function of Bertsekas (1982), is established for solving unconstrained minimax problems. It is proven that a sequence of points, generated by solving a sequence of unconstrained minimizers of the smoothing function with changing parametert, converges with Q-superlinear rate to a Kuhn-Tucker point locally under some mild conditions. The relationship between the condition number of the Hessian matrix of the smoothing function and the parameter is studied, which also validates the convergence theory. Finally the numerical results are reported to show the effectiveness of this algorithm.     

Yet another geometric programming dual algorithm

We describe an algorithm for the geometric programming dual problem which uses an adaptation of the generalized LP algorithm, proposed by Dantzig et al. twenty-five years ago for the chemical equilibrium problem, and show the slack primal constraints pose no numerical difficulties for this algorithm as they do for previous dual-based algorithms.     

Computational complexity of a piecewise linear homotopy algorithm

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices. This research has been partially supported by the grant MCS 80-05154 from the National Science Foundation.     

A sixth-order dual preserving algorithm for the Camassa-Holm equation

The paper presents a sixth-order numerical algorithm for studying the completely integrable Camassa-Holm (CH) equation. The proposed sixth-order accurate method preserves both the dispersion relation and the Hamiltonians of the CH equation. The CH equation in this study is written as an evolution equation, involving only the first-order spatial derivatives, coupled with the Helmholtz equation. We propose a two-step method that first solves the evolution equation by a sixth-order symplectic Runge-Kutta method and then solves the Helmholtz equation using a three-point sixth-order compact scheme. The first-order derivative terms in the first step are approximated by a sixth-order dispersion-relation-preserving scheme that preserves the physically inherent dispersive nature. The compact Helmholtz solver, on the other hand, allows us to use relatively few nodal points in a stencil, while achieving a higher-order accuracy. The sixth-order symplectic Runge-Kutta time integrator is preferable for an equation that possesses a Hamiltonian structure. We illustrate the ability of the proposed scheme by examining examples involving peakon or peakon-like solutions. We compare the computed solutions with exact solutions or asymptotic predictions. We also demonstrate the ability of the symplectic time integrator to preserve the Hamiltonians. Finally, via a smooth travelling wave problem, we compare the accuracy, elapsed computing time, and rate of convergence among the proposed method, a second-order two-step algorithm, and a completely integrable particle method.     

A simple dual algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The dual-type algorithm uses a simple heuristic derived from a relaxation of the problem. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach. Computational results look promising in terms of speed and solution quality.     

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Recently, É. Tardos gave a strongly polynomial algorithm for the minimum-cost circulation problem and solved the open problem posed in 1972 by J. Edmonds and R.M. Karp. Her algorithm runs in O(m ² T(m, n) logm) time, wherem is the number of arcs,n is the number of vertices, andT(m, n) is the time required for solving a maximum flow problem in a network withm arcs andn vertices. In the present paper, taking an approach that is a dual of Tardos's, we also give a strongly polynomial algorithm for the minimum-cost circulation problem. Our algorithm runs in O(m ² S(m, n) logm) time and reduces the computational complexity, whereS(m, n) is the time required for solving a shortest path problem with a fixed origin in a network withm arcs,n vertices, and a nonnegative arc length function. The complexity is the same as that of Orlin's algorithm, recently developed by efficiently implementing the Edmonds-Karp scaling algorithm.     

A sequential dual simplex algorithm for the linear assignment problem

We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski [3,4] and Goldfarb [8]: O(n²) pivots, O(n² log n + nm) time. Our algorithm works with the (dual) strongly feasible trees and can handle rectangular systems quite naturally.     

Computational approach to the cost analysis of dual machine interference model with general arrival distribution

In this paper, a fresh attempt has been made to apply a computational approach to obtain the optimal total cost of the system as an important performance measure for the machine interference model with general arrival distribution. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)