单纯形上二次型函数的最值搜索算法

由于单纯形域上的二次型函数往往是多峰函数,当函数形式较为复杂时难以求得全局最值.构造了两类适用于单纯形上二次型函数优化的算法,分别是单纯形上的Newton-Raphson算法与随机搜索算法.经过实例验证,这两种算法都是有效的.     

Optimal search paths for random variables

Let X be a real random variable, distributed according to some symmetric distribution F. A searcher starts at the origin and moves with an upper bound on his speed until he finds X. Which search path does he have to choose in order to minimize the expected searching time (or equivalently, to minimize the expected path length)? By means of numerical methods the solution is calculated for the normal, Student, logistic and Laplace distributions.     

A theoretical comparison between the simplex method and the basic line search algorithm

A theoretical comparison between the simplex method (SM) and the basic line search method (BLSA) is presented. The explicit formulae for the upper and lower bounds in the BLSA are provided using SM. Further, it is shown that both methods are operationally equivalent.     

Parallel asynchronous label-correcting methods for shortest paths

We develop parallel asynchronous implementations of some known and some new label-correcting methods for finding a shortest path from a single origin to all the other nodes of a directed graph. We compare these implementations on a shared-memory multiprocessor, the Alliant FX/80, using several types of randomly generated problems. Excellent (sometimes superlinear) speedup is achieved with some of the methods, and it is found that the asynchronous versions of these methods are substantially faster than their synchronous counterparts.The authors acknowledge the director and the staff of CERFACS, Toulouse, France for the use of the Alliant FX/80.This research was supported by the National Science Foundation under Grants 9108058-CCR, 9221293-INT, and 9300494-DMI.     

New criteria for the simplex algorithm

The standard linear programming problem with a finite optimum value is considered. We derive new criteria which guarantee that(i) a non-basic variable of a basic feasible solution will remain a non-basic variable of an optimal basic solution; (ii) a basic variable of a basic feasible solution will remain a basic variable of an optimal basic solution.     

Parallel local search

We present a survey of parallel local search algorithms in which we review the concepts that can be used to incorporate parallelism into local search. For this purpose we distinguish between single-walk and multiple-walk parallel local search and between asynchronous and synchronous parallelism. Within the class of single-walk algorithms we differentiate between multiple-step and single-step parallelism. To describe parallel local search we introduce the concepts of hyper neighborhood structures and distributed neighborhood structures. Furthermore, we present templates that capture most of the parallel local search algorithms proposed in the literature. Finally, we discuss some complexity issues related to parallel local search.     

Dynamic trees as search trees via euler tours, applied to the network simplex algorithm

Thedynamic tree is an abstract data type that allows the maintenance of a collection of trees subject to joining by adding edges (linking) and splitting by deleting edges (cutting), while at the same time allowing reporting of certain combinations of vertex or edge values. For many applications of dynamic trees, values must be combined along paths. For other applications, values must be combined over entire trees. For the latter situation, an idea used originally in parallel graph algorithms, to represent trees by Euler tours, leads to a simple implementation with a time of O(logn) per tree operation, wheren is the number of tree vertices. We apply this representation to the implementation of two versions of the network simplex algorithm, resulting in a time of O(logn) per pivot, wheren is the number of vertices in the problem network. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office of Naval Research, Contract No. N0014-91-J-1463. Work during a visit to M.I.T. partially supported by ARPA Contract No. 14-95-1-1246.     

Parallel solver for trajectory optimization search directions

A key algorithmic element of a real-time trajectory optimization hardware/software implementation is presented, the search step solver. This is one piece of an algorithm whose overall goal is to make nonlinear trajectory optimization fast enough to provide real-time commands during guidance of a vehicle such as an aeromaneuvering orbiter or the National Aerospace Plane. Many methods of nonlinear programming require the solution of a quadratic program (QP) at each iteration to determine the search step. In the trajectory optimization case, the QP has a special dynamic programming structure, an LQR-like structure. The algorithm exploits this special structure with a divide-and-conquer type of parallel implementation. A hypercube message-passing parallel machine, the INTEL iPSC/2, has been used. The algorithm solves a (p·N)-stage problem onN processors inO(p + log₂ N) operations. The algorithm yields a factor of 8 speed-up over the fastest known serial algorithm when solving a 1024-stage test problem on 32 processors.This research was supported in part by the National Aeronautics and Space Administration under Grant No. NAG-1-1009.     

Parallel distributed-memory simplex for large-scale stochastic LP problems

We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.     

Optimizing the system of virtual paths by tabu search

In an asynchronous transfer mode (ATM) network, given the network topology and traffic demands, the establishment of the system of virtual paths (VPs), and the assignment of connections to them so that the network performance is optimized, entails a number of computationally hard subproblems. The optimization problem discussed here focuses on finding a system of VP routes for a given set of VP terminators and VP capacity demands. Although it has been proven that the existing random path algorithm yields the worst case time bound, the solution performance still depends highly on the number of iterations. In this paper, an exact solution procedure and a heuristic method based on a simple tabu search have been developed for optimizing the system of VPs. Computational results show that the proposed tabu search algorithm is effective in obtaining high quality solutions, and the performance of the proposed algorithm is increasingly attractive as the problem size becomes larger.     

A largest-distance pivot rule for the simplex algorithm

We propose a new pivot rule for the simplex algorithm, which is demonstrative in the dual space intuitively. Although it is based on normalized reduced costs, like the steepest-edge rule and its variants, the rule is much simpler and cheaper than the latter. We report computational results obtained with the 47 largest Netlib problems in terms of the number of rows and columns, all of the 16 Kennington problems, and the 17 largest BPMPD problems. Over the total 80 problems, a variant of the rule outperformed the Devex rule with iterations and time ratio 1.43 and 3.24, respectively.     

Special simplex algorithm for multi-sector problems

This paper describes a proposed special algorithm for a certain class of partionable linear programming problems. The matrix defining such a linear programming problem consists of a number of non-zero diagonal blocks, plus some entirely filled rows and dito columns.     

On the length of simplex paths: The assignment case

This paper reports on an experimental study of the distribution of the length of simplex paths for the Optimal Assignment Problem. We study the distribution of the pivot counts for a version of the simplex method that with essentially equal probabilities introduces any variable with negative reduced cost into the basis. In this situation the distribution of the pivot counts turns out to be normally distributed and independent of the actual cost coefficients, provided these are sufficiently spread out. Further, the mean and standard deviation grow only moderately with the size of the problem, namely asd ^1.8, andd ^1.5 respectively for ad×d problem, implying in particular that the pivot counts concentrate around the mean with growingd. The usual simplex method on the other hand gives a growth ofd ^1.6. Hence a large part of the favourable polynomial growth experienced on practical problems may be attributed to the fact that the simplex paths are rather short on the average, at least for assignment problems.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

A recognition algorithm for the intersection graphs of paths in trees

Let F be a finite family of non-empty sets. An undirected graph G is an intersection graph for F if there is a one-to-one correspondence between the vertices of G and the sets of F such that two sets have a non-empty intersection exactly when the corresponding vertices are adjacent in G. If this is the case then F is said to be an intersection model for the graph G. If F is a family of paths within a tree T, then G is called a path graph. This paper proves a characterization for the path graphs and then gives a polynomial time algorithm for their recognition. If G is a path graph the algorithm constructs a path intersection model for G.     

A linear-time algorithm for edge-disjoint paths in planar graphs

In this paper we discuss the problem of finding edge-disjoint paths in a planar, undirected graph such that each path connects two specified vertices on the boundary of the graph. We will focus on the “classical” case where an instance additionally fulfills the so-calledevenness-condition. The fastest algorithm for this problem known from the literature requiresO (n ^5/3(loglogn)^1/3) time, wheren denotes the number of vertices. In this paper now, we introduce a new approach to this problem, which results in anO(n) algorithm. The proof of correctness immediately yields an alternative proof of the Theorem of Okamura and Seymour, which states a necessary and sufficient condition for solvability.     

An overview on the simplex algorithm

In this paper, the simplex algorithm and its variants are investigated. First, we define a new concept called formal tableau, which leads to derive easily the dual solution from the latest primal table; without any distinction between the original variables and the slack ones. Second, we propose a new method for initializing the simplex algorithm. Unlike the two-phase and the big-M methods, our technique does not involve artificial variables. The computational results reveal that this new method is very favorable especially when the number of artificial variables is significant. Finally, this method will be combined with the notion of formal tableau leading naturally to a second new approach.     

A novel hybrid algorithm combining hunting search with harmony search algorithm for training neural networks

Neural networks (NNs) are one of the most widely used techniques for pattern classification. Owing to the most common back-propagation training algorithm of NN being extremely computationally intensive and it having some drawbacks, such as converging into local minima, many meta-heuristic algorithms have been applied to training of NNs. This paper presents a novel hybrid algorithm which is the integration of Harmony Search (HS) and Hunting Search (HuS) algorithms, called h_HS-HuS, in order to train Feed-Forward Neural Networks (FFNNs) for pattern classification. HS and HuS algorithms are recently proposed meta-heuristic algorithms inspired from the improvisation process of musicians and hunting of animals, respectively. Harmony search builds up the main structure of the hybrid algorithm, and HuS forms the pitch adjustment phase of the HS algorithm. The performance proposed algorithm is compared to conventional and meta-heuristic algorithms. Empirical tests are carried out by training NNs on nine widely used classification benchmark problems. The experimental results show that the proposed hybrid harmony-hunting algorithm is highly capable of training NNs.     

Parallel algorithm for linear diophantine equations

We consider a parallel-sequential algorithm to find all the solution of a linear Diophantine equation a_nx_n + a_n — 1x_n — 1 + +a₁x₁ = b, a_i, b, x_i Z⁺ by the method of dynamic upper bounds. Parallel processing and dichotomizing search are responsible for logarithmic time complexity of the algorithm. The auxiliary table memory requirements are 3n words. The algorithm can be applied in linear integer programming problems.Simferopol' University. Translated from Dinamicheskie Sistemy, No. 10, pp. 111–117, 1992.