On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates

The Sequential Ordering Problem (herewith, SOP) with precedence relationships was introduced in Escudero (1988), and extended to cover release and due dates in Escudero and Sciomachen (1993). It has a broad range of applications, mainly in production planning for manufacturing systems. The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the nodes and the arcs, satisfying precedence relationships among the nodes and given lower and upper bounds on the weights of the Hamiltonian subpaths. In this paper we present a model for the constrained minimum weight Hamiltonian path problem with precedences and due dates forcing constraints, and introduce related valid cuts that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation procedure to obtain those cuts, so-called the Lagrangian Relax-and-Cut (LRC) scheme. Computational experience is given for variations of some SOP cases already reported in the literature.     

Eigenvalue problem of a class of fourth-order Hamiltonian operators

The eigenvalue problem of a class of fourth-order Hamiltonian operators is studied. We first obtain the geometric multiplicity, the algebraic index and the algebraic multiplicity of each eigenvalue of the Hamiltonian operators. Then, some necessary and sufficient conditions for the completeness of the eigen or root vector system of the Hamiltonian operators are given, which is characterized by that of the vector system consisting of the first components of all eigenvectors. Moreover, the results are applied to the plate bending problem.     

Car sequencing is NP-hard: a short proof

In this note, a new proof is given that the car sequencing (CS) problem is NP-hard. Established from the Hamiltonian Path problem, the reduction is direct while closing some gaps remaining in the previous NP-hardness results. Since CS is studied in many operational research courses, this result and its proof are particularly interesting for teaching purposes.     

On the general nonlinear self-adjoint spectral problem for differential-algebraic systems

We consider a general self-adjoint spectral problem, nonlinear with respect to the spectral parameter, for linear differential-algebraic systems of equations. Under some assumptions, we present a method for reducing such a problem to a general self-adjoint nonlinear spectral problem for a system of differential equations. In turn, this permits one to pass to a problem for a Hamiltonian system of ordinary differential equations. In particular, in this way, one can obtain a method for computing the number of eigenvalues of the original problem lying in a given range of the spectral parameter.     

The Hamiltonian connectivity of rectangular supergrid graphs

A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.     

On approximating the nearest Ω‐stable matrix

In this paper, we consider the problem of approximating a given matrix with a matrix whose eigenvalues lie in some specific region Ω of the complex plane. More precisely, we consider three types of regions and their intersections: conic sectors, vertical strips, and disks. We refer to this problem as the nearest Ω‐stable matrix problem. This includes as special cases the stable matrices for continuous and discrete time linear time‐invariant systems. In order to achieve this goal, we parameterize this problem using dissipative Hamiltonian matrices and linear matrix inequalities. This leads to a reformulation of the problem with a convex feasible set. By applying a block coordinate descent method on this reformulation, we are able to compute solutions to the approximation problem, which is illustrated on some examples.     

Parametric stability in Robe’s problem

In this work we have given a Hamiltonian formulation to Robe’s problem, obtaining again the classic results. We have computed the resonances existing in the circular case and obtained some information with regard to the linear stability of the central equilibrium of Robe’s problem in the elliptic case. In some critical cases we have constructed, in the parameter plane, the boundary curves that separate the regions of stability and instability.     

A generalization of the Bondy-Chvátal theorem on the k-closure

In this paper two sufficient conditions ensuring that the k-closure of a graph is complete are given, which are improvements of corresponding results due to Bondy and Chvátal. These results are applied to the Hamiltonian problem and other problems, and thus some weaker criteria than those previously obtained are derived.     

大型不正定陀螺系统本征值问题

陀螺动力系统可以导入哈密顿辛几何体系,在哈密顿陀螺系统的辛子空间迭代法的基础上提出了一种能够有效计算大型不正定哈密顿函数的陀螺系统本征值问题的算法．利用陀螺矩阵既为哈密顿矩阵而本征值又是纯虚数或零的特点,将对应哈密顿函数为负的本征值分离开来,构造出对应哈密顿函数全为正的本征值问题,利用陀螺系统的辛子空间迭代法计算出正定哈密顿矩阵的本征值,从而解决了大型不正定陀螺系统的本征值问题,算例证明,本征解收敛得很快．     

Asymptotic stability and associated problems of dynamics of falling rigid body

We consider two problems from the rigid body dynamics and use new methods of stability and asymptotic behavior analysis for their solution. The first problem deals with motion of a rigid body in an unbounded volume of ideal fluid with zero vorticity. The second problem, having similar asymptotic behavior, is concerned with motion of a sleigh on an inclined plane. The equations of motion for the second problem are non-holonomic and exhibit some new features not typical for Hamiltonian systems. A comprehensive survey of references is given and new problems connected with falling motion of heavy bodies in fluid are proposed.      

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian

We consider the spectral and algorithmic aspects of the problem of finding a Hamiltonian cycle in a graph. We show that a sufficient condition for a graph being Hamiltonian is that the nontrivial eigenvalues of the combinatorial Laplacian are sufficiently close to the average degree of the graph. An algorithm is given for the problem of finding a Hamiltonian cycle in graphs with bounded spectral gaps which has complexity of order n ^{cln n} .     

基于二次算子族的无界Hamilton算子根向量组的基性质

利用无界Hamilton算子导出的二次算子族,本文研究了一类无界Hamilton算子根向量组的Schauder基性质.首先,建立了无界Hamilton算子的根向量与相应的二次算子族的根向量之间的关系.其次,借助二次算子族谱的相关性质,刻画了无界Hamilton算子的本征值分布以及本征值的代数指标,并得到了无界Hamilton算子的根向量组是某个Hilbert空间的一个块状Schauder基的充要条件.最后,将所得结果应用于矩形薄板弯曲问题.     

The Liouville integrability of integrable couplings of Volterra lattice equation

A hierarchy of integrable couplings of Volterra lattice equations with three potentials is proposed, which is derived from a new discrete six-by-six matrix spectral problem. Moreover, by means of the discrete variational identity on semi-direct sums of Lie algebra, the two Hamiltonian forms are deduced for each lattice equation in the resulting hierarchy. A strong symmetry operator of the resulting hierarchy is given. Finally, we prove that the hierarchy of the resulting Hamiltonian equations are all Liouville integrable discrete Hamiltonian systems.     

斜对角无穷维Hamilton算子的点谱和特征函数系辛结构的非退化性

本文研究斜对角无穷维Hamilton算子$H=\begin{pmatrix}0&B\\C&0\end{pmatrix}$的点谱和特征函数系辛结构的非退化性, 给出斜对角无穷维Hamilton算子$H$的特征函数系具有非退化辛结构的充分必要条件. 基于此, 进一步刻画了斜对角无穷维Hamilton算子$H$的点谱分别包含于实轴、虚轴以及其它区域的充分必要条件. 最后, 以板弯曲问题和弦振动问题中导出的斜对角无穷维Hamilton算子为例, 验证了所得结论的正确性.     

A dynamical system approach to Heisenberg uniqueness pairs

A canonical system is a kind of first-order system of ordinary differential equations on an interval of the real line parametrized by complex numbers. It is known that any solution of a canonical system generates an entire function of the Hermite-Biehler class. In this paper, we deal with the inverse problem to recover a canonical system from a given entire function of the Hermite-Biehler class satisfying appropriate conditions. This inverse problem was solved by de Branges in 1960s. However his results are often not enough to investigate a Hamiltonian of recovered canonical system. In this paper, we present an explicit way to recover a Hamiltonian from a given exponential polynomial belonging to the Hermite-Biehler class. After that, we apply it to study distributions of roots of self-reciprocal polynomials.     

A Schur decomposition for Hamiltonian matrices

A Schur-type decomposition for Hamiltonian matrices is given that relies on unitary symplectic similarity transformations. These transformations preserve the Hamiltonian structure and are numerically stable, making them ideal for analysis and computation. Using this decomposition and a special singular-value decomposition for unitary symplectic matrices, a canonical reduction of the algebraic Riccati equation is obtained which sheds light on the sensitivity of the nonnegative definite solution. After presenting some real decompositions for real Hamiltonian matrices, we look into the possibility of an orthogonal symplectic version of the QR algorithm suitable for Hamiltonian matrices. A finite-step initial reduction to a Hessenberg-type canonical form is presented. However, no extension of the Francis implicit-shift technique was found, and reasons for the difficulty are given.     

Multiplicity of solutions for second-order Hamiltonian systems with impulses

In this paper, we study the existence of infinitely many solutions for second-order Hamiltonian systems with impulses. By using an infinitely many critical points theorem and Fountain theorem, we obtain some new criteria for guaranteeing that the impulsive Hamiltonian systems have infinitely many solutions. No symmetric condition on the nonlinear term is assumed. Some examples are also given in this paper to illustrate our main results.