On one method of solving the partial covering problem

We propose and analyze a method for exact solution of the partial covering problem, which has numerous applications. Results of a numerical experiment indicate that the method is efficient.Translated from Kibernetika, No. 1, pp. 96–98, January–February, 1989.     

On the abstraction method for the container relocation problem

The container relocation problem or the blocks relocation problem is a classic combinatorial optimisation problem that occurs in day-to-day operations for facilities that use block stacking systems. A typical place where this problem arises is a container terminal where containers can be stacked vertically in order to utilise the scarce resource of yard surface, thus at times resulting in the unproductive reshuffling moves for containers stacked above the target container for retrieval. Due to the problem class being NP-hard, a number of studies on this topic propose heuristic approaches to solve this problem. There are a few exact methods (search-based algorithms or mathematical programming) proposed for this problem but the feasible problem size of such methods is quite restricted, limiting their practical significance. In this paper, we propose a new insight into reducing the search space of this problem by the abstraction method. Our main contribution to the existing literature is two-fold: the reduction in the search space by the abstraction method and the bidirectional search using the pattern database. Our computational results confirm that our approach enables instances of a near-practical size to be solved optimally within a reasonable computation time.     

On the scaled newton method for the symmetric eigenvalue problem

For solving symmetric eigenvalue problems the scaled Newton method is proposed. The new algorithm is equivalent to the Rayleigh quotient iteration and its rate of convergence is cubic. Numerical experiments indicate that the scaled Newton method is very competitive with the projected Newton method, and produces, in the main, insignificantly smaller residua than the Rayleigh quotient iteration.     

System concepts in Kron's polyhedron model and the scattering problem

Kron's polyhedron model based on a sequence of transformations related to the orthogonal electrical network problem was proposed for a wide range of system problems. The scattering formulation for a flow process introduces a similar sequence of ‘ obstacles ’ and can form an analytical basis for many of the concepts discussed by Kron. It can be associated with the system problems incorporating an optimality condition and the updating of a priori information, and can also be identified in the sweep method of solution of the two-point boundary-value problems for optimal control and estimation, which would appear to be related to the concept of wave propagation in Kron's model. The sequential networks in the polyhedron model and the scattering problem thus provide a basic analytical structure which has important applications in general systems theory.     

On an exact method for the constrained shortest path problem

The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.     

On the convergence of Uzawa's method for the solution of biharmonic problem

The convergence of Uzawa's method for the solution of biharmonic problem in the mixed finite element method had been proved in [2] and [3]. In this paper, we obtained an asymptotic rate of convergence. Furthermore, in order to keep the same order of error between the solutions of Uzawa's iteration and biharmonic problem, as the order of error between the solutions of the mixed finite element method and biharmonic problem, we estimated the timesn of Uzawa's iteration as follows:n≥≥?(75/vσ ²)h ^?1 lnh for 2-degree Lagrange elements, andn≥?(18/vσ ²)h ^?1 lnh?(12/vσ ²)h ^?1 ln(?lnh) for linear elements.     

On the discovery of mathematical concepts

The Graph Theorist (GT) is a system intended to perform mathematical research in graph theory. This paper focuses upon GT's ability to discover new mathematical concepts by varying the definitions in its input knowledge base. Each new definition is a correct and complete generator for a class of graphs. the new concepts arise from the specialization of an existing concept, the generalization of an existing concept, and the merger of two or more existing concepts. Discovery is driven both by examples (specific graphs) and by definitional form (algorithms). GT explores new concepts either to develop an area of knowledge or to link a newly-acquired concept into a pre-existing knowledge base. From an initial knowledge base containing only the definition of “graph,” GT discovers such concepts as acyclic graphs, connected graphs and bipartite graphs. Given an input concept, such as “star,” GT discovers “trees” while searching for the appropriate links to integrate star into its knowledge base. the discovery processes construct a semantic net linking frames for all of GT's concepts together.     

试论传统教学理念和CAI的结合

随着多媒体课件在课堂教学过程中的大量使用,和完善了几十上百年的传统教学相比,总是显得稚嫩和不尽人意。分析其原因的文章有很多,也提出了不少有建设性的意见,但总体而言很少有从CAI定位层面上来分析和解决这一问题。本文尝试从还CAI的本来面目入手,将多媒体辅助教学拉下神坛,重新归入到粉笔、录音机一样的工具的地位,扶师生交互,情感交流于主流。从而实现CAI和传统教学有机的结合。     

Modelling the Stereovision-Correspondence-Analysis task by Lateral Inhibition in Accumulative Computation problem-solving method

Recently, the Algorithmic Lateral Inhibition (ALI) method and the Accumulative Computation (AC) method have proven to be efficient in modelling at the knowledge level for general-motion-detection tasks in video sequences. More precisely, the task of persistent motion detection has been widely expressed by means of the AC method, whereas the ALI method has been used with the objective of moving objects detection, labelling and further tracking. This paper exploits the current knowledge of our research team on the mentioned problem-solving methods to model the Stereovision-Correspondence-Analysis (SCA) task. For this purpose, ALI and AC methods are combined into the Lateral Inhibition in Accumulative Computation (LIAC) method. The four basic subtasks, namely “LIAC 2D Charge-Memory Calculation”, “LIAC 2D Charge-Disparity Analysis” and “LIAC 3D Charge-Memory Calculation” in our proposal of SCA are described in detail by inferential CommonKADS schemes. It is shown that the LIAC method may perfectly be used to solve a complex task based on motion information inherent to binocular video sequences.     

Modelling the Stereovision-Correspondence-Analysis task by Lateral Inhibition in Accumulative Computation problem-solving method

Recently, the Algorithmic Lateral Inhibition (ALI) method and the Accumulative Computation (AC) method have proven to be efficient in modelling at the knowledge level for general-motion-detection tasks in video sequences. More precisely, the task of persistent motion detection has been widely expressed by means of the AC method, whereas the ALI method has been used with the objective of moving objects detection, labelling and further tracking. This paper exploits the current knowledge of our research team on the mentioned problem-solving methods to model the Stereovision-Correspondence-Analysis (SCA) task. For this purpose, ALI and AC methods are combined into the Lateral Inhibition in Accumulative Computation (LIAC) method. The four basic subtasks, namely “LIAC 2D Charge-Memory Calculation”, “LIAC 2D Charge-Disparity Analysis” and “LIAC 3D Charge-Memory Calculation” in our proposal of SCA are described in detail by inferential CommonKADS schemes. It is shown that the LIAC method may perfectly be used to solve a complex task based on motion information inherent to binocular video sequences.     

On the concepts of controllability and observability of linear systems

The objectives of this paper are to give a self-contained presentation of the subject of "controllability" and "observability" (concepts due to Kalman) developed in a simple yet general and rigorous way; to introduce these concepts in terms of the output as well as in terms of the state; and to point out and illustrate some of the subtleties which exist in the time-varying case.     

On error estimates of the fully discrete penalty method for the viscoelastic flow problem

In this paper, a fully discrete finite element penalty method is presented for the two-dimensional viscoelastic flow problem arising in the Oldroyd model, in which the spatial discretization is based on the finite element approximation and the time discretization is based on the backward Euler scheme. Moreover, we provide the optimal error estimate for the numerical solution under some realistic assumptions. Finally, some numerical experiments are shown to illustrate the efficiency of the penalty method.     

On numeric solution of linear-quadratic optimal control problem by dual method

An iterative numerical solution method is proposed for the general linear quadratic optimal control problem with phase constraints. The method is based on the extension principle. Realization features of the method are described for Matlab environment.     

On the Aizerman problem

The method of harmonic linearization in degenerate cases is stated and strictly mathematically justified. This method is applied to the search for periodic oscillations for systems satisfying the generalized Routh-Hurwitz condition.     

On the calibration problem

First we consider estimating a constantn-dimensional parameter vectorxusing anm-dimensional observation vectory = Hxform < n. Unless H is time-varying,xcannot be estimated. This is the case addressed. It is shown that the Kalman filtering approach yields an estimation algorithm equivalent to a direct deterministic approach which may be more practical to implement. Using Friedland's "separate bias" algorithm [1], we extend the analysis to the problem of indirect observations, i.e., fordot{z}= Az + Hxwithy = Cz + Dx+upsilon(upsilon=observation noise), and show that the results reduce to those for the first problem as observation noiseupsilontends to zero. As an illustration, the application to the calibration of four parameters in a two-axis gyro is presented.     

On the semi-convergence of preconditioned GLHSS iteration method for non-Hermitian singular saddle point problem

Recently, Fan and Zheng studied the preconditioned generalized local Hermitian and skew-Hermitian splitting (GLHSS) iteration method for non-Hermitian singular saddle point problem, and given its semi-convergence conditions; see Fan and Zheng (2014). In this note, we prove the semi-convergence of preconditioned GLHSS method by another method. The obtained result shows that the conditions for guaranteeing its semi-convergence are easy to check and more weaker.     

The effects of Logo and CAI problem-solving environments on problem-solving abilities and mathematics achievement

The purpose of the present study was to investigate the effects of Logo programming and CAI problem-solving software on problem solving that is dependent on specialized conceptual and procedural knowledge, problem solving that is dependent on specific executive-level cognitive skills, and mathematics achievement. No significant differences were found on mathematics achievement or knowledge-dependent problem solving. However, significant differences were found on the test of executive-level problem solving, with the Logo group improving more than the CAI and control groups.     

Sub-optimal solutions to track detection problem using graph theoretic concepts

This paper demonstrates how the problem of tracking targets, which appear as either straight or curved lines in two-dimensional display images (or data images) can be formulated in terms of a directed weighted graph model and how dynamic programming techniques can be efficiently applied to reach an optimal or sub-optimal solution. In general, track detection algorithms providing optimal solutions have good detective ability, but most of them suffer from the inability to detect discontinuous lines or to resolve efficiently pairs of crossing lines. A sub-optimal solution is provided that efficiently overcomes these weaknesses. We focus on modeling the track detection problem in terms of a graph, formulating fast sequential/parallel sub-optimal track detection algorithms and testing them on simulated data in order to show their detective ability. Moreover, we specify the conditions under which sub-optimal algorithms can perform at least as well as their corresponding optimal algorithms. This is significant for the track detection problem where fast, accurate and real-time detection is considered a necessity.