The linear ordering problem: Instances,search space analysis and algorithms

The linear ordering problem is an NP-hard problem that arises in a variety of applications. Due to its interest in practice, it has received considerable attention and a variety of algorithmic approaches to its solution have been proposed. In this paper we give a detailed search space analysis of available benchmark instance classes that have been used in various researches. The large fitness-distance correlations observed for many of these instances suggest that adaptive restart algorithms like iterated local search or memetic algorithms, which iteratively generate new starting solutions for a local search based on previous search experience, are promising candidates for obtaining high performing algorithms. We therefore experimentally compared two such algorithms and the final experimental results suggest that, in particular, the memetic algorithm is a new state-of-the-art approach to the linear ordering problem.     

Efficient solution of two-stage stochastic linear programs using interior point methods

Solving deterministic equivalent formulations of two-stage stochastic linear programs using interior point methods may be computationally difficult due to the need to factorize quite dense search direction matrices (e.g., AA ^T ). Several methods for improving the algorithmic efficiency of interior point algorithms by reducing the density of these matrices have been proposed in the literature. Reformulating the program decreases the effort required to find a search direction, but at the expense of increased problem size. Using transpose product formulations (e.g., A ^T A) works well but is highly problem dependent. Schur complements may require solutions with potentially near singular matrices. Explicit factorizations of the search direction matrices eliminate these problems while only requiring the solution to several small, independent linear systems. These systems may be distributed across multiple processors. Computational experience with these methods suggests that substantial performance improvements are possible with each method and that, generally, explicit factorizations require the least computational effort.     

Modeling and analysis of system reliability using phase‐type distribution closure properties

Phase‐type distribution closure properties are utilized to devise algorithms for generating reliability functions of systems with basic structures. These structures include series, parallel, K‐out‐of‐N, and standby structures with perfect/imperfect switch. The algorithms form a method for system reliability modeling and analysis based on the relationship between the system lifetime and component lifetimes for general structures. The proposed method is suitable for functional system reliability analysis, which can produce reliability functions of systems with independent components instead of only system reliability values. Once the system reliability function is obtained, other reliability measures such as the system's hazard function and mean time to failure can be obtained efficiently using only matrix algebra. Dimensional and numerical comparisons with computerized symbolic processing are also presented to show the superiority of the proposed method.     

Incomplete oblique projections for solving large inconsistent linear systems

The authors introduced in previously published papers acceleration schemes for Projected Aggregation Methods (PAM), aiming at solving consistent linear systems of equalities and inequalities. They have used the basic idea of forcing each iterate to belong to the aggregate hyperplane generated in the previous iteration. That scheme has been applied to a variety of projection algorithms for solving systems of linear equalities or inequalities, proving that the acceleration technique can be successfully used for consistent problems. The aim of this paper is to extend the applicability of those schemes to the inconsistent case, employing incomplete projections onto the set of solutions of the augmented system Ax − r = b. These extended algorithms converge to the least squares solution. For that purpose, oblique projections are used and, in particular, variable oblique incomplete projections are introduced. They are defined by means of matrices that penalize the norm of the residuals very strongly in the first iterations, decreasing their influence with the iteration counter in order to fulfill the convergence conditions. The theoretical properties of the new algorithms are analyzed, and numerical experiences are presented comparing their performance with several well-known projection methods. Dedicated to Clovis Gonzaga on the occassion of his 60th birthday.     

Entropy solutions for linearly degenerate hyperbolic systems of rich type

Consider a linearly degenerate hyperbolic system of rich type. Assuming that each eigenvalue of the system has a constant multiplicity, we construct a representation formula of entropy solutions in L^∞ to the Cauchy problem. This formula depends on the solution of an autonomous system of ordinary differential equations taking x as parameter. We prove that for smooth initial data, the Cauchy problem for such an autonomous system admits a unique global solution. By using this formula together with classical compactness arguments, we give a very simple proof on the global existence of entropy solutions. Moreover, in a particular case of the system, we obtain an another explicit expression and the uniqueness of the entropy solution. Applications include the one-dimensional Born–Infeld system and linear Lagrangian systems.     

On Bounded Solutions of Systems of Linear Functional Differential Equations

Sufficient conditions of the existence and uniqueness of bounded on real axis solutions of systems of linear functional differential equations are established.     

On stationarity of stochastic retarded linear equations with unbounded drift operators

This article continues the study of Liu [Statist. Probab. Lett. 78(2008): 1775–1783; Stoch. Anal. Appl. 29(2011): 799–823] for stationary solutions of stochastic linear retarded functional differential equations with the emphasis on delays which appear in those terms including spatial partial derivatives. As a consequence, the associated stochastic equations have unbounded operators acting on the point or distributed delayed terms, while the operator acting on the instantaneous term generates a strongly continuous semigroup. We present conditions on the delay systems to obtain a unique stationary solution by combining spectrum analysis of unbounded operators and stochastic calculus. A few instructive cases are analyzed in detail to clarify the underlying complexity in the study of systems with unbounded delayed operators.     

Cauchy problem for quasilinear hyperbolic systems of shallow water equations

This article investigates the Cauchy problem for two different models (modified and classical), governed by quasilinear hyperbolic systems that arise in shallow water theory. Under certain reasonable hypotheses on the initial data, we obtain the global smooth solutions for both the systems. The bounds on simple wave solutions of the modified system are shown to depend on the parameter H characterizing the advective transport of impulse. Similarly the bounds on simple wave solutions of the classical system describing the flow over a sloping bottom with profile b(x) are shown to depend on the bottom topography. On the other hand, if the initial data are specified differently, then it is shown that solutions for both the systems exhibit finite time blow-up from specific smooth initial data. Moreover, we show that an increase in H and convexity of b would reduce the time taken for the solutions to blow up.     

NECESSARY AND SUFFICIENT CONDITIONS FOR EXISTENCE AND UNIQUENESS OF PERIODIC SOLUTIONS OF NEUTRAL LINEAR FUNCTIONAL DIFFERENTIAL EQUATIONS WITH CONSTANT COEFFICIENTS：A METHOD BY FOURIER SERIESES

ＮＥＣＥＳＳＡＲＹＡＮＤＳＵＦＦＩＣＩＥＮＴＣＯＮＤＩＴＩＯＮＳＦＯＲＥＸＩＳＴＥＮＣＥＡＮＤＵＮＩＱＵＥＮＥＳＳＯＦＰＥＲＩＯＤＩＣＳＯＬＵＴＩＯＮＳＯＦＮＥＵＴＲＡＬＬＩＮＥＡＲＦＵＮＣＴＩＯＮＡＬＤＩＦＦＥＲＥＮＴＩＡＬＥＱＵＡＴＩＯＮＳＷＩＴ...     

Existence and uniqueness of positive solutions for some singular boundary value problems with linear functional boundary conditions

By using the upper and lower solution method and fixed point theory, we investigate some nonlinear singular second-order differential equations with linear functional boundary conditions. The nonlinear term f(t, u) is nonincreasing with respect to u, and only possesses some integrability. We obtain the existence and uniqueness of the C[0,1] positive solutions as well as the C ¹[0, 1] positive solutions.     

Superposition principle and composite solutions to coupled nonlinear Schrödinger equations

We show that the superposition principle applies to coupled nonlinear Schrödinger equations with cubic nonlinearity where exact solutions may be obtained as a linear combination of other exact solutions. This is possible due to the cancelation of cross terms in the nonlinear coupling. First, we show that a composite solution, which is a linear combination of the two components of a seed solution, is another solution to the same coupled nonlinear Schrödinger equation. Then, we show that a linear combination of two composite solutions is also a solution to the same equation. With emphasis on the case of Manakov system of two-coupled nonlinear Schrödinger equations, the superposition is shown to be equivalent to a rotation operator in a two-dimensional function space with components of the seed solution being its coordinates. Repeated application of the rotation operator, starting with a specific seed solution, generates a series of composite solutions, which may be represented by a generalized solution that defines a family of composite solutions. Applying the rotation operator to almost all known exact seed solutions of the Manakov system, we obtain for each seed solution the corresponding family of composite solutions. Composite solutions turn out, in general, to possess interesting features that do not exist in the seed solution. Using symmetry reductions, we show that the method applies also to systems of N-coupled nonlinear Schrödinger equations. Specific examples for the three-coupled nonlinear Schrödinger equation are given.     

A numerical evaluation of solvers for the periodic Riccati differential equation

Efficient and accurate structure exploiting numerical methods for solving the periodic Riccati differential equation (PRDE) are addressed. Such methods are essential, for example, to design periodic feedback controllers for periodic control systems. Three recently proposed methods for solving the PRDE are presented and evaluated on challenging periodic linear artificial systems with known solutions and applied to the stabilization of periodic motions of mechanical systems. The first two methods are of the type multiple shooting and rely on computing the stable invariant subspace of an associated Hamiltonian system. The stable subspace is determined using either algorithms for computing an ordered periodic real Schur form of a cyclic matrix sequence, or a recently proposed method which implicitly constructs a stable deflating subspace from an associated lifted pencil. The third method reformulates the PRDE as a convex optimization problem where the stabilizing solution is approximated by its truncated Fourier series. As known, this reformulation leads to a semidefinite programming problem with linear matrix inequality constraints admitting an effective numerical realization. The numerical evaluation of the PRDE methods, with focus on the number of states (n) and the length of the period (T) of the periodic systems considered, includes both quantitative and qualitative results.     

Solving a nonlinear system of second order boundary value problems

In this paper, a method is presented to obtain the analytical and approximate solutions of linear and nonlinear systems of second order boundary value problems. The analytical solution is represented in the form of series in the reproducing kernel space. In the mean time, the approximate solution un(x) is obtained by the n-term intercept of the analytical solution and is proved to converge to the analytical solution. Some numerical examples are studied to demonstrate the accuracy of the present method. Results obtained by the method indicate the method is simple and effective.     

Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation

We propose a family of retrospective optimization (RO) algorithms for optimizing stochastic systems with both integer and continuous decision variables. The algorithms are continuous search procedures embedded in a RO framework using dynamic simplex interpolation (RODSI). By decreasing dimensions (corresponding to the continuous variables) of simplex, the retrospective solutions become closer to an optimizer of the objective function. We present convergence results of RODSI algorithms for stochastic “convex” systems. Numerical results show that a simple implementation of RODSI algorithms significantly outperforms some random search algorithms such as Genetic Algorithm (GA) and Particle Swarm Optimization (PSO).     

Homoclinic Solutions for A Class of Second Order Neutral Functional Differential Systems

By means of an extension of Mawhin's continuation theorem and some analysis methods, the existence of a set with 2kT-periodic solutions for a class of second order neutral functional differential systems is studied, and then the homoclinic solutions are obtained as the limit points of a certain subsequence of the above set.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

Numerical Solution of Boundary Value Problems for Selfadjoint Differential Equations of 2nth Order

The paper is devoted to solving boundary value problems for self-adjoint linear differential equations of 2nth order in the case that the corresponding differential operator is self-adjoint and positive semidefinite. The method proposed consists in transforming the original problem to solving several initial value problems for certain systems of first order ODEs. Even if this approach may be used for quite general linear boundary value problems, the new algorithms described here exploit the special properties of the boundary value problems treated in the paper. As a consequence, we obtain algorithms that are much more effective than similar ones used in the general case. Moreover, it is shown that the algorithms studied here are numerically stable.     

A remark on sets of determining elements for reaction-diffusion systems

For a class of systems of parabolic equations, conditions represented by a finite set of linear functionals on the phase space that uniquely determine the long-time behavior of solutions are found. The cases in which it is sufficient to define these determining functionals only on a part of the components of the state vector are singled out. As examples, systems describing the Belousov-Zhabotinsky reaction and the two-dimensional Navier-Stokes equations are considered. Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 774–784, May, 1998.     

Number representations of satisfiability

Propositional formulas are represented by real-valued matrices so that their unsatisfiability is proved to be equivalent to the stable nonnegative solvability of linear algebraic systems. The complete calculus for the generation of all nonnegatively solvable linear homogeneous systems is presented as a consequence. Solvability of systems of linear inequalities with real coefficients and Boolean variables is reduced to the satisfiability of some formula. The alternatives theorem is proved concerning the solvability of such systems. The technique of implicit enumeration in the search for solutions both in the systems considered and in a wide range of discrete optimization problems is described. Bibliography: 21 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol 241, 1997, pp. 72–96 Translated by E. A. Hirsch.     

Reid Roundabout Theorem for Symplectic Dynamic Systems on Time Scales

The principal aim of this paper is to state and prove the so-called Reid roundabout theorem for the symplectic dynamic system (S) z ^Δ = \cal S _t z on an arbitrary time scale \Bbb T , so that the well known case of differential linear Hamiltonian systems ( \Bbb T = \Bbb R ) and the recently developed case of discrete symplectic systems ( \Bbb T = \Bbb Z ) are unified. We list conditions which are equivalent to the positivity of the quadratic functional associated with (S), e.g. disconjugacy (in terms of no focal points of a conjoined basis) of (S), no generalized zeros for vector solutions of (S), and the existence of a solution to the corresponding Riccati matrix equation. A certain normality assumption is employed. The result requires treatment of the quadratic functionals both with general and separated boundary conditions. Accepted 28 August 2000. Online publication 26 February 2001.