On the determination of the potential function from given orbits

The paper deals with the problem of finding the field of force that generates a given (N ? 1)-parametric family of orbits for a mechanical system with N degrees of freedom. This problem is usually referred to as the inverse problem of dynamics. We study this problem in relation to the problems of celestial mechanics. We state and solve a generalization of the Dainelli and Joukovski problem and propose a new approach to solve the inverse Suslov’s problem. We apply the obtained results to generalize the theorem enunciated by Joukovski in 1890, solve the inverse Stäckel problem and solve the problem of constructing the potential-energy function U that is capable of generating a bi-parametric family of orbits for a particle in space. We determine the equations for the sought-for function U and show that on the basis of these equations we can define a system of two linear partial differential equations with respect to U which contains as a particular case the Szebehely equation. We solve completely a special case of the inverse dynamics problem of constructing U that generates a given family of conics known as Bertrand’s problem. At the end we establish the relation between Bertrand’s problem and the solutions to the Heun differential equation. We illustrate our results by several examples.     

Asymptotic expansions of periodic solutions of ordinary differential equations with large high-frequency terms

We consider the problem on the periodic solutions of a system of ordinary differential equations of arbitrary order n containing terms oscillating at a frequency ω ? 1 with coefficients of the order of ω ^n/2. For this problem, we construct the averaged (limit) problem and justify the averaging method as well as another efficient algorithm for constructing the complete asymptotics of the solution.     

A neural network approach to facility layout problems

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N × N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.     

New geometry-inspired relaxations and algorithms for the metric Steiner tree problem

Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; the previous best integrality gap upper bound being 3/2 (Rajagopalan and Vazirani in On the bidirected cut relaxation for the metric Steiner tree problem, 1999). We also obtain a factor \({\sqrt{2}}\) strongly polynomial algorithm for this class of graphs. A key difficulty experienced by researchers in working with the bidirected cut relaxation was that any reasonable dual growth procedure produces extremely unwieldy dual solutions. A new algorithmic idea helps finesse this difficulty—that of reducing the cost of certain edges and constructing the dual in this altered instance—and this idea can be extracted into a new technique for running the primal-dual schema in the setting of approximation algorithms.     

Global regular solutions for the 3D Kawahara equation posed on unbounded domains

An initial boundary value problem for the 3D Kawahara equation posed on a channel-type domain was considered. The existence and uniqueness results for global regular solutions as well as exponential decay of small solutions in the H²-norm were established.     

A class of solutions for the inverse diffusion problem

The close relation between Hermitian wavelets transforms and the diffusion equation is used to derive a one-parameter family of distributed sources as solutions to the inverse diffusion problem in R^N × R_. The class of solutions is interpreted in terms of energetically dominant events in the wavelet representation, where the scale of the event is proportional to its age. The construction procedure is a straightforward extension of the inverse wavelet transform formula. Simple examples illustrate the method.     

Tabu search embedded simulated annealing for the shortest route cut and fill problem

The shortest route cut and fill problem proposed by Henderson et al ¹ is studied in this paper where we extend the model to include multiple vehicles and a makespan objective. A new tabu search embedded simulated annealing algorithm for both models is developed. Computational experiments show that the new approach is robust and achieves better solutions when compared with those found using Henderson et al's algorithm for larger test cases within significantly shorter times.     

A modified greedy analysis pursuit algorithm for the cosparse analysis model

In the past decade, the sparse representation synthesis model has been deeply researched and widely applied in signal processing. Recently, a cosparse analysis model has been introduced as an interesting alternative to the sparse representation synthesis model. The sparse synthesis model pay attention to non-zero elements in a representation vector x, while the cosparse analysis model focuses on zero elements in the analysis representation vector Ωx. This paper mainly considers the problem of the cosparse analysis model. Based on the greedy analysis pursuit algorithm, by constructing an adaptive weighted matrix W _k?1, we propose a modified greedy analysis pursuit algorithm for the sparse recovery problem when the signal obeys the cosparse model. Using a weighted matrix, we fill the gap between greedy algorithm and relaxation techniques. The standard analysis shows that our algorithm is convergent. We estimate the error bound for solving the cosparse analysis model, and then the presented simulations demonstrate the advantage of the proposed method for the cosparse inverse problem.     

Matrix inverse problem and its optimal approximation problem for R-skew symmetric matrices

Let R ∈ C^n×n be a nontrivial involution, i.e., R² = I and R ≠ ±I. A matrix A ∈ C^n×n is called R-skew symmetric if RAR = −A. The least-squares solutions of the matrix inverse problem for R-skew symmetric matrices with R∗ = R are firstly derived, then the solvability conditions and the solutions of the matrix inverse problem for R-skew symmetric matrices with R∗ = R are given. The solutions of the corresponding optimal approximation problem with R∗ = R for R-skew symmetric matrices are also derived. At last an algorithm for the optimal approximation problem is given. It can be seen that we extend our previous results [G.X. Huang, F. Yin, Matrix inverse problem and its optimal approximation problem for R-symmetric matrices, Appl. Math. Comput. 189 (2007) 482-489] and the results proposed by Zhou et al. [F.Z. Zhou, L. Zhang, X.Y. Hu, Least-square solutions for inverse problem of centrosymmetric matrices, Comput. Math. Appl. 45 (2003) 1581-1589].     

A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over

In this paper, the multi-item, single-level, capacitated, dynamic lot sizing problem with set-up carry-over and backlogging, abbreviated to CLSP⁺, is considered. The problem is formulated as a mixed integer programming problem. A heuristic method consisting of four elements: (1) a demand shifting rule, (2) lot size determination rules, (3) checking feasibility conditions and (4) set-up carry-over determination, provides us with an initial feasible solution. The resulting feasible solution is improved by adopting the corresponding set-up and set-up carry-over schedule and re-optimizing it by solving a minimum-cost network flow problem. Then the improved solution is used as a starting solution for a tabu search procedure, with the value of moves assessed using the same minimum-cost network problem. Computational results on randomly generated problems show that the algorithm, which is coded in C++, is able to provide optimal solutions or solutions extremely close to optimal. The computational efficiency makes it possible to solve reasonably large problem instances routinely on a personal computer.     

Optimal multiway split trees

A class of multiway split trees is defined. Given a set of n weighted keys and a node capacity m, an algorithm is described for constructing a multiway split tree with minimum access cost. The algorithm runs in time O(mn⁴) and requires O(mn³) storage locations. A further refinement of the algorithm enables the factor m in the above costs to be reduced to log m.     

Operations policy for a supply chain system with fixed-interval delivery and linear demand

This research addresses a production-supply problem for a supply-chain system with fixed-interval delivery. A strategy that determines the optimal batch sizes, cycle times, numbers of orders of raw materials, and production start times is prescribed to minimize the total costs for a given finite planning horizon. The external demands are time-dependent following a life-cycle pattern and the shipment quantities follow the demand pattern. The shipment quantities to buyers follow various phases of the demand pattern in the planning horizon where demand is represented by piecewise linear model. The problem is formulated as an integer, non-linear programming problem. The model also incorporates the constraint of inventory capacity. The problem is represented using the network model where an optimal characteristic has been analysed. To obtain an optimal solution with N shipments in a planning horizon, an algorithm is proposed that runs with the complexity of Θ(N²) for problems with a single-phase demand and O(N³) for problems with multi-phase demand.     

Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems

A variant of balancing domain decomposition method by constraints (BDDC) is proposed for solving a class of indefinite systems of linear equations of the form (K?σ²M)u=f, which arise from solving eigenvalue problems when an inverse shifted method is used and also from the finite element discretization of Helmholtz equations. Here, both K and M are symmetric positive definite. The proposed BDDC method is closely related to the previous dual–primal finite element tearing and interconnecting method (FETI‐DP) for solving this type of problems (Appl. Numer. Math. 2005; 54 :150–166), where a coarse level problem containing certain free‐space solutions of the inherent homogeneous partial differential equation is used in the algorithm to accelerate the convergence. Under the condition that the diameters of the subdomains are small enough, the convergence rate of the proposed algorithm is established, which depends polylogarithmically on the dimension of the individual subdomain problems and which improves with a decrease of the subdomain diameters. These results are supported by numerical experiments of solving a two‐dimensional problem. Copyright © 2009 John Wiley & Sons, Ltd.     

A unified framework for constructing globally convergent algorithms for multidimensional coefficient inverse problems

We present a unified framework for constructing the globally convergent algorithms for a broad class of multidimensional coefficient inverse problems arising in natural science and industry. Based on the convexification approach, the unified framework substantiates the numerical solution of the corresponding problem of nonconvex optimization. A globally convergent iterative algorithm for an inverse problem of diffuse optical mammography is constructed. It utilizes the contraction property of a nonlinear operator resulting from applying the convexification approach. The effectiveness of this algorithm is demonstrated in computational experiments.     

A linear time algorithm for inverse obnoxious center location problems on networks

For an inverse obnoxious center location problem, the edge lengths of the underlying network have to be changed within given bounds at minimum total cost such that a predetermined point of the network becomes an obnoxious center location under the new edge lengths. The cost is proportional to the increase or decrease, resp., of the edge length. The total cost is defined as sum of all cost incurred by length changes. For solving this problem on a network with m edges an algorithm with running time ${\mathcal{O}(m)}$ is developed.     

A reconstruction method for a two-dimensional inverse eigenvalue problem

In this paper we describe a method for constructing approximate solutions of a two-dimensional inverse eigenvalue problem. Here we consider the problem of recovering a functionq(x, y) from the eigenvalues of — +q(x, y) on a rectangle with Dirichlet boundary conditions. The potentialq(x, y) is assumed to be symmetric with respect to the midlines of the rectangle. Our method is a generalization of an algorithm Hald presented for the construction of symmetric potentials in the one-dimensional inverse Sturm-Liouville problem. Using a projection method, the inverse spectral problem is reduced to an inverse eigenvalue problem for a matrix. We show that if the given eigenvalues are small perturbations of simple eigenvalues ofq=0, then the matrix problem has a solution. This solution is used to construct a functionq which has the same lowest eigenvalues as the unknownq, and several numerical examples are given to illustrate the methods.     

Reducing network and computation complexities in neural based real-time scheduling scheme

Multiprocessor real-time scheduling is an important issue in many applications. A neural network provides a highly effective method to obtain good solutions for real-time scheduling problems. However, multiprocessor real-time scheduling problems include multiple variables; processor, process and time, and the neural networks have to be presented in three dimensions with these variables. Hence, the corresponding neural networks have more neurons, and synaptic weights, and thus associated network and computational complexities increase. Meanwhile, a neural network using the competitive scheme can provide a highly effective method with less network complexity. Therefore, in this study, a simplified two-dimensional Hopfield-type neural network using competitive rule is introduced for solving three-dimensional multiprocessor real-time scheduling problems. Restated, a two-dimensional network is proposed to lower the neural network dimensions and decrease the number of neurons and hence reduce the network complexity; an M-out-of-N competitive scheme is suggested to greatly reduce the computational complexity. Simulation results reveal that the proposed scheme imposed on the derived energy function with respect to process time and deadline constraints is an appropriate approach to solving these class scheduling problems. Moreover, the computational complexity of the proposed scheme is greatly lowered to O(N × T²).