Hybridizations of GRASP with path relinking for the far from most string problem

Among the sequence selection and comparison problems, the far from most string problem (FFMSP) is one of the computationally hardest with applications in several fields, including molecular biology where one is interested in creating diagnostic probes for bacterial infections or in discovering potential drug targets. In this paper, we describe several heuristics that hybridize GRASP with different path‐relinking strategies, such as forward, backward, mixed, greedy randomized adaptive forward, and evolutionary path relinking. Experiments on a large set of both real‐world and randomly generated test instances indicate that these hybrid heuristics are both effective and efficient. In particular, the hybrid GRASP with evolutionary path relinking finds slightly better quality solutions compared to the other variants when running for the same number of iterations, while the hybrid with backward path relinking finds better quality solution within a fixed running time.     

Regularization of a lexicographic vector problem of integer programming

A stability criterion for a vector integer linear problem of lexicographic optimization is obtained. A regularization method is proposed that allows us to reduce a possible unstable output problem to a sequence of perturbed stable equivalent problems. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 125–130, November–December, 1999.     

Remarks on the relationship between stability and internal stability of nonlinear systems

In this paper, we investigate the relationship between stability and internal stability of nonlinear systems. It is shown that under certain conditions, stability implies attractivity of the equilibrium and that local stability with finite gain implies local asymptotic stability of the origin. Copyright © 2012 John Wiley & Sons, Ltd.     

A polyhedral approach to solving multicriterion combinatorial optimization problems over sets of polyarrangements

Multicriterion discrete optimization problems over feasible combinatorial sets of polyarrangements are considered. Structural properties of feasible domains and different types of efficient solutions are investigated. Based on the ideas of Euclidean combinatorial optimization and the major criterion method, a polyhedral approach to the solution of the problems is developed and substantiated. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 118-126, May-June 2009.     

Remarks on three types of asymptotic stability

In this note, three types of asymptotic stability (Liapunov stability, Poincaré stability, and Zhukovkij stability) of motion in continuous autonomous dynamical systems are discussed. It is shown that each type of asymptotic stability can be geometrically characterized by omega limit set of an orbit of this type of stability.     

A note on the quadratic assignment problem

The quadratic assignment problem （QAP） is one of the most interesting and challenging combinatorial optimization problems in existence and one of the most difficult problems in the NP-hard class. Many real-life problems in several areas such as facilities location parallel and distributed computing, combinatorial data analysis and combinatorial optimization problems which have many application in computer engineering and industry can be formulated as a QAP. In this paper, the author give a short note on the QAP, giving our rounding approach with the survey of other algorithms that used to solve this important problem.     

On the computational complexity of combinatorial flexibility problems

The concept of flexibility – originated in the context of heat exchanger networks design – is associated with a substructure which allows the same optimal value on the substructure (for example an optimal flow) as in the whole structure, for all the costs in a given range of costs. In this work, we extend the concept of flexibility to general combinatorial optimization problems, and prove several computational complexity results in this new framework. Under some monotonicity conditions, we prove that a combinatorial optimization problem can be polynomially reduced to its associated flexibility problem. However, the minimum cut, maximum weighted matching and shortest path problems have NP-complete associated flexibility problems. In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids.     

Approximate algorithms for the container loading problem

In this paper we develop several algorithms for solving three–dimensional cutting/packing problems. We begin by proposing an adaptation of the approach proposed in Hifi and Ouafi (1997) for solving two–staged unconstrained two–dimensional cutting problems. We show how the algorithm can be polynomially solved for producing a constant approximation ratio. We then extend this algorithm for developing better approximate algorithms. By using hill–climbing strategies, we construct some heuristics which produce a good trade–off between the computational time and the solution quality. The performance of the proposed algorithms is evaluated on different problem instances of the literature, with different sizes and densities (a total of 144 problem instances).     

A heuristic for the skiving and cutting stock problem in paper and plastic film industries

This paper investigates the skiving and cutting stock problem (SCSP) encountered in the paper and plastic film industries, in which a set of nonstandard reels generated from previous cutting processes are used to produce finished rolls through the skiving and cutting process. First, reels are skived together lengthwise to form a reel‐pyramid (a polygon), and then the reel‐pyramid is cut into finished rolls of small widths. Depending on if a reel can be divided lengthwise into subreels to form the reel‐pyramid, the problem can be classified into divisible SCSP (DSCSP) and indivisible SCSP (ISCSP). In this paper, two integer programming (IP) models are proposed for DSCSP and ISCSP, respectively. A sequential value correction procedure combined with the two IP models (SVCTIP) is developed to solve the two SCSPs. The effectiveness of the SVCTIP is demonstrated through extensive computational tests.     

Development of neurofuzzy architecture for solving the N-Queens problem

Neural networks are dynamic systems consisting of highly interconnected and parallel nonlinear processing elements that are shown to be extremely effective in computation. This paper presents an architecture of recurrent neural networks for solving the N-Queens problem. More specifically, a modified Hopfield network is developed and its internal parameters are explicitly computed using the valid-subspace technique. These parameters guarantee the convergence of the network to the equilibrium points, which represent a solution of the considered problem. The network is shown to be completely stable and globally convergent to the solutions of the N-Queens problem. A fuzzy logic controller is also incorporated in the network to minimize convergence time. Simulation results are presented to validate the proposed approach.     

基于DEA混合算法的模糊车间作业计划问题的研究*

针对以最小化制造跨度为目标,具有模糊加工时间的车间作业计划问题,采用梯形模糊数来表征时间参数,并应用可能性理论,在此基础上构建车间作业计划问题目标函数。为了对模糊环境下的车间作业计划问题进行有效求解,给出了一种DEA-GA混合求解算法,混合算法采用了DNA进化算法的分裂、变异和水平选择算子,然后利用遗传算法的交叉算子实现个体之间的交互,避免早熟收敛。仿真实验表明,该算法高效可行,与GA等优化算法相比,具有更快的收敛速度。     

Determining the K-best solutions of knapsack problems

It is well-known that knapsack problems arise as subproblems of a number of large-scale integer optimization problems. In order to solve these large problems, it is necessary to solve the subproblems efficiently, and for many of them it can be useful to determine the K-best solutions. In this paper, a branch-and-bound method for the unbounded knapsack problem described in the literature is extended to determine the K-best solutions of unbounded and bounded knapsack problems. We show that the proposed extension determines exactly the K-best solutions and we solve important classical instances using high values of K.     

Design and analysis of stochastic local search for the multiobjective traveling salesman problem

Stochastic local search (SLS) algorithms are typically composed of a number of different components, each of which should contribute significantly to the final algorithm's performance. If the goal is to design and engineer effective SLS algorithms, the algorithm developer requires some insight into the importance and the behavior of possible algorithmic components. In this paper, we analyze algorithmic components of SLS algorithms for the multiobjective travelling salesman problem. The analysis is done using a careful experimental design for a generic class of SLS algorithms for multiobjective combinatorial optimization. Based on the insights gained, we engineer SLS algorithms for this problem. Experimental results show that these SLS algorithms, despite their conceptual simplicity, outperform a well-known memetic algorithm for a range of benchmark instances with two and three objectives.     

Multicriteria combinatorial optimization problems on a set of polypermutations

The studies on multicriteria combinatorial optimization are continued. A possible approach to solving multicriterion problems is developed and substantiated. An algorithm is developed and implemented. Some peculiarities of efficient solutions to multicriterion problems are described. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 152–160, March–April 2008.     

On characterizations of the input-to-state stability property

We show that the well-known Lyapunov sufficient condition for “input-to-state stability” (ISS) is also necessary, settling positively an open question raised by several authors during the past few years. Additional characterizations of the ISS property, including one in terms of nonlinear stability margins, are also provided.     

Subclasses of solvable problems from classes of combinatorial optimization problems

Well-known subclasses of solvable problems from classes of combinatorial optimization are reviewed. For solvable problems such as the traveling salesman problem, location problem, assignment problem, and clustering problem, the changes in the objective function on a given ordering of combinatorial configurations are analyzed. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 97–105, March–April 2009.     

A self-stabilizing distributed algorithm for the bounded lattice domination problems under the distance-2 model

The domination problem is one of the fundamental graph problems, and there are many variations. In this article, we propose a new problem called the minus -domination problem where , and are integers such that , , and . The problem is to assign a value from for each vertex in a graph such that the local summation of values is greater than or equal to . We also propose a framework named the bounded lattice domination for a class of domination problems, including the minus -domination problem. Then, we present a self-stabilizing distributed algorithm under the distance-2 model for the bounded lattice domination. Here, self-stabilization is a class of fault-tolerant distributed algorithms that tolerate transient faults. The time complexity for convergence is $$, where $$ is the number of processes in a network if the cardinality of the domain of process values is finite and constant. Otherwise, the time complexity for convergence is $$.