Direct shooting method,linearization, and nonlinear algebraic equations

The direct shooting method for the solution of boundary-value problems for ordinary, nonlinear differential equations is analyzed from the point of view of linearization. Some relations between this method and perturbation methods are established. The relations between the direct shooting algorithm and Whittaker's algorithm are also established, considering the problem from the point of view of solving nonlinear algebraic equations.     

Using Gauss-Jordan elimination to compute the index,generalized nullspaces,and Drazin inverse

We develop and analyze a new algorithm that computes bases for the null spaces of all powers of a given matrix, as well as its index. The algorithm uses row operations and “shuffling” steps in which rows of pairs of matrices are interchanged. In particular, the new algorithm may be viewed as an extension of the classic Gauss-Jordan elimination method for inverting a nonsingular matrix. It is also shown that the Drazin inverse has a simple representation in terms of the output of the algorithm and the original matrix.     

Multi-Item, Multi-Facility Supply Chain Planning: Models, Complexities, and Algorithms

We propose a planning model for products manufactured across multiple manufacturing facilities sharing similar production capabilities. The need for cross-facility capacity management is most evident in high-tech industries that have capital-intensive equipment and a short technology life cycle. We propose a multicommodity flow network model where each commodity represents a product and the network structure represents manufacturing facilities in the supply chain capable of producing the products. We analyze in depth the product-level (single-commodity, multi-facility) subproblem when the capacity constraints are relaxed. We prove that even the general-cost version of this uncapacitated subproblem is NP-complete. We show that there exists an optimization algorithm that is polynomial in the number of facilities, but exponential in the number of periods. We further show that under special cost structures the shortest-path algorithm could achieve optimality. We analyze cases when the optimal solution does not correspond to a source-to-sink path, thus the shortest path algorithm would fail. To solve the overall (multicommodity) planning problem we develop a Lagrangean decomposition scheme, which separates the planning decisions into a resource subproblem, and a number of product-level subproblems. The Lagrangean multipliers are updated iteratively using a subgradient search algorithm. Through extensive computational testing, we show that the shortest path algorithm serves as an effective heuristic for the product-level subproblem (a mixed integer program), yielding high quality solutions with only a fraction (roughly 2%) of the computer time.     

Memetic algorithms, domain knowledge, and financial investing

How might domain knowledge constrain a genetic algorithm and systematically impact the algorithm’s traversal of the search space? In particular, in this paper the hypothesis is advanced that a semantic tree of financial knowledge can be used to influence the results of a genetic algorithm for financial investing problems. An algorithm is described, called the “Memetic Algorithm for Domain Knowledge”, and is instantiated in a software system. In mutation experiments, this system chooses financial ratios to use as inputs to a neural logic network which classifies stocks as likely to increase or decrease in value. The mutation is guided by a semantic tree of financial ratios. In crossover experiments, this system solves a portfolio optimization problem in which components of an individual represent weights on stocks; knowledge in the form of a semantic tree of industries determines the order in which components are sorted in individuals. Both synthetic data and real-world data are used. The experimental results show that knowledge can be used to reach higher fitness individuals more quickly. More interestingly, the results show how conceptual distance in the human knowledge can correspond to distance between evolutionary individuals and their fitness. In other words, knowledge might be dynamically used to at times increase the step size in a search algorithm or at times to decrease the step size. These results shed light on the role of knowledge in evolutionary computation and are part of the larger body of work to delineate how domain knowledge might usefully constrain the genetic algorithm.     

A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres

Summary. The algorithm proved here solves the problem of orthogonal distance regression for the maximum norm with hyperplanes and hyperspheres. For each finite set of points in a Euclidean space of any dimension, the algorithm determines – through finitely many arithmetic operations – all the hyperplanes and hyperspheres that minimize the maximum Euclidean distance measured perpendicularly from the data. The algorithm finds all the slabs (bounded by parallel hyperplanes) and all the spherical shells (bounded by concentric hyperspheres) that contain all the data and are “rigidly supported” by the data (for which there does not exist any other pair of parallel hypersurfaces of the same type that intersect the data at the same points.) The computational complexity of the algorithm increases as the number of data points raised to the dimension of the ambient space. The solutions are then the midrange hyperplanes in the thinnest slabs, and the midrange hyperspheres in the thinnest shells. Their sensitivity to perturbations of the data is of the order of a power of the reciprocal of the smallest angle between two median hyperplanes separating two pairs of data points. The methods of proof consist in showing that if a pair of parallel hyperplanes or hyperspheres is not rigidly supported but encompasses all the data, then there exists a projective shift of their common projective center producing a thinner slab or shell that still contains all the data. Received December 14, 1999 / Revised version received August 30, 2000 / Published online September 19, 2001     

Makespan minimization for two parallel machines scheduling with a periodic availability constraint: Mathematical programming model,average-case analysis,and anomalies

A mathematical programming model is proposed for the two parallel machines scheduling problem where one machine is periodically unavailable, jobs are non-preemptive, and the objective is minimizing the makespan. The model is established by transforming the two parallel machine setting into a single machine setting. Average-case analyses of the classical Longest Processing Time first (LPT) algorithm and the List Scheduling (LS) are presented. Computational experiments show that the LPT algorithm beats the LS algorithm in all the 96 combinations of two main parameters from an average-case error point of view and that the average-case error of the LPT algorithm is less than 2% when the number of jobs is greater than twenty. Unexpectedly, there also exist instances showing that the LS algorithm may beat the LPT algorithm from the average-case error point of view.     

Reflections on nondifferentiable optimization,part 2, convergence

This paper is concerned with the minimization of nondifferentiable functions. Three main results are obtained: (i) convergence of the ball-gradient algorithm, introduced by Dixon, for convex functions; (ii) convergence of the generalized gradient algorithm, as implemented by Shor and Ermol'ev, to a stationary point; and (iii) convergence of an algorithm introduced by Goldstein to a local minimum.This research was carried out while the second author was being supported by the National Research Council of Italy at the Numerical Optimization Center of the Hatfield Polytechnic.     

Matching,Euler tours and the Chinese postman

The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed.     

Single machine scheduling with release times,deadlines and tardiness objectives

A polynomial time algorithm is developed to minimize maximum tardiness on a single machine in the presence of deadlines. The possibility of extending the total tardiness pseudopolynomial algorithm to the cases where release times or deadlines are in place is also investigated. It is concluded that the aforementioned pseudopolynomial algorithm can be extended only when deadlines and due dates are compatible and all job release times are equal.     

Gauss codes,planar hamiltonian graphs,and stack-sortable permutations

In this paper the following three recognition problems are considered: (1) Test whether a given sequence is the Gauss code of a planar self-intersecting curve; (2) test whether a given graph with a known Hamiltonian cycle is planar; and (3) test whether a given permutation can be sorted using two stacks in parallel. These three problems are closely related: A simple linear-time algorithm that solves all three is described. The heart of the algorithm is a data structure, previously used in general planarity testing, called a pile of twin stacks.     

An implementable algorithm for the optimal design centering,tolerancing, and tuning problem

An implementable master algorithm for solving optimal design centering, tolerancing, and tuning problems is presented. This master algorithm decomposes the original nondifferentiable optimization problem into a sequence of ordinary nonlinear programming problems. The master algorithm generates sequences with accumulation points that are feasible and satisfy a new optimality condition, which is shown to be stronger than the one previously used for these problems.This research was sponsored by the National Science Foundation (RANN), Grant No. ENV-76-04264, and by the Joint Services Electronic Program, Contract No. F44620-76-C-0100.     

An approximate subgradient algorithm for unconstrained nonsmooth,nonconvex optimization

In this paper a new algorithm for minimizing locally Lipschitz functions is developed. Descent directions in this algorithm are computed by solving a system of linear inequalities. The convergence of the algorithm is proved for quasidifferentiable semismooth functions. We present the results of numerical experiments with both regular and nonregular objective functions. We also compare the proposed algorithm with two different versions of the subgradient method using the results of numerical experiments. These results demonstrate the superiority of the proposed algorithm over the subgradient method.      

Simulating Argon,Helium, and Nitrogen Shock Waves

We simulate the structure of the shock wave front in the range of Mach numbers from 1.5 to 10 using quasigasdynamic (QGD) equations and Navier - Stokes (NS) equations. The numerical results are compared with published experimental data. QGD and NS calculations produce close results that tightly fit the experimental data, especially for the monatomic argon and helium. The QGD algorithm is found to be more stable than the NS algorithm. __________ Translated from Prikladnaya Matematika i Informatika, No. 18, pp. 66–82, 2004.     

An Algorithm for Non-Linear Network Programming: Implementation,Results and Comparisons

This paper evaluates an algorithm for solving network flow optimization problems with quadratic cost functions. Strategies for fast implementation are discussed and the results of extensive numerical tests are given. The performance of the algorithm measured by CPU time is compared with that of the convex simplex method specialized for quadratic network programming. Performance of the two methods is analysed with respect to network size and density, and other parameters of interest. The algorithm is shown to perform significantly better on the majority of problems. We also show how the algorithm may be used to solve non-linear convex network optimization problems by the use of sequential quadratic programming.     

Clifford algebra method for network expression,computation, and algorithm construction

Clifford algebra is introduced as a theoretical foundation for network topology expression and algorithm construction. Network nodes are coded with basis vectors in a vector space , and the edges and k‐walk routes can be expressed by 2‐blades and k‐blades, respectively, in the Clifford algebra Cl(n,0). The topologies among nodes, edges, and routes of networks can be directly calculated, and the network routes can be extended and traversed with oriented join products. The network algorithm construction processes based on Clifford algebra are instantiated by the single source shortest path algorithm. The experimental results on different scale random networks suggest that Clifford algebra is suited for network expression and relation computation. The Clifford algebra‐based shortest path algorithm is vivid and clear in geometric meaning and has great advantage on temporal and spatial complexity. Copyright © 2013 John Wiley & Sons, Ltd.     

Single-machine serial-batching scheduling with a machine availability constraint,position-dependent processing time,and time-dependent set-up time

This article considers the single-machine serial-batching scheduling problem with a machine availability constraint, position-dependent processing time, and time-dependent set-up time. The objective of this problem is to make the decision of batching jobs and sequencing batches to minimize the makespan. To solve the problem, three cases of machine non-availability periods are considered, and the structural properties of the optimal solution are derived for each case. Based on these structural properties, an optimization algorithm is developed and an example is proposed to illustrate this algorithm.     

Parallel lightweight wavelet tree,suffix array and FM-index construction

We present parallel lightweight algorithms to construct wavelet trees, rank and select structures, and suffix arrays in a shared-memory setting. The work and depth of our first parallel wavelet tree algorithm match those of the best existing parallel algorithm while requiring asymptotically less memory and our second algorithm achieves the same asymptotic bounds for small alphabet sizes. Our experiments show that they are both faster and more memory-efficient than existing parallel algorithms. We also present an experimental evaluation of the parallel construction of rank and select structures, which are used in wavelet trees. Next, we design the first parallel suffix array algorithm based on induced copying. Our induced copying requires linear work and polylogarithmic depth for constant alphabets sizes. When combined with a parallel prefix doubling algorithm, it is more efficient in practice both in terms of running time and memory usage compared to existing parallel implementations. As an application, we combine our algorithms to build the FM-index in parallel.     

Sparse polynomials, redundant bases, gauss periods, and efficient exponentiation of primitive elements for small characteristic finite fields

Gauss periods give an exponentiation algorithm that is fast for many finite fields but slow for many other fields. The current paper presents a different method for construction of elements that yield a fast exponentiation algorithm for finite fields where the Gauss period method is slow or does not work. The basic idea is to use elements of low multiplicative order and search for primitive elements that are binomial or trinomial of these elements. Computational experiments indicate that such primitive elements exist, and it is shown that they can be exponentiated fast.     

Primal-Dual Splitting Algorithm for Solving Inclusions with Mixtures of Composite, Lipschitzian, and Parallel-Sum Type Monotone Operators

We propose a primal-dual splitting algorithm for solving monotone inclusions involving a mixture of sums, linear compositions, and parallel sums of set-valued and Lipschitzian operators. An important feature of the algorithm is that the Lipschitzian operators present in the formulation can be processed individually via explicit steps, while the set-valued operators are processed individually via their resolvents. In addition, the algorithm is highly parallel in that most of its steps can be executed simultaneously. This work brings together and notably extends various types of structured monotone inclusion problems and their solution methods. The application to convex minimization problems is given special attention.     

Symplectic Householder transformations for a QR-like decomposition,a geometric and algebraic approaches

The aim of this paper is to show how geometric and algebraic approaches lead us to a new symplectic elementary transformations: the 2-D symplectic Householder transformations. Their features are studied in details. Their interesting properties allow us to construct a new algorithm for computing a SR factorization. This algorithm is based only on these 2-D symplectic Householder transformations. Its new features are highlighted. The study shows that, in the symplectic case, the new algorithm is the corresponding one to the classical QR factorization algorithm, via the Householder transformations. Some numerical experiments are given.