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.     

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).     

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.     

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.     

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.     

Limits of input-to-state stability

The relations between attractors, input-to-state-stability, and controllability properties are discussed. In particular it is shown that loss of the attractor property under perturbations is connected with a qualitative change in the controllability properties due to a ‘merger’ with a control set.     

Growth conditions for exponential stability of time-varying perturbed systems

In this paper, we derive some sufficient conditions for practical uniform exponential stability of time-varying perturbed systems based on Lyapunov techniques, whose dynamics are in general unbounded in time, in the sense that the solutions are uniform stable and converge to a small neighbourhood of the origin. Under quite general assumptions, we first present a new converse stability theorem for a large class of time-varying systems, which will be used to prove certain stability properties of nonlinear systems with perturbation. Therefore, a new Lyapunov function is presented that guarantees practical uniform exponential stability of perturbed systems. Furthermore, some illustrative examples are presented.     

Learning automata-based solutions to the optimal web polling problem modelled as a nonlinear fractional knapsack problem

We consider the problem of polling web pages as a strategy for monitoring the world wide web. The problem consists of repeatedly polling a selection of web pages so that changes that occur over time are detected. In particular, we consider the case where we are constrained to poll a maximum number of web pages per unit of time, and this constraint is typically dictated by the governing communication bandwidth, and by the speed limitations associated with the processing. Since only a fraction of the web pages can be polled within a given unit of time, the issue at stake is one of determining which web pages are to be polled, and we attempt to do it in a manner that maximizes the number of changes detected. We solve the problem by first modelling it as a stochastic nonlinear fractional knapsack problem. We then present an online learning automata (LA) system, namely, the hierarchy of twofold resource allocation automata (H-TRAA), whose primitive component is a twofold resource allocation automaton (TRAA). Both the TRAA and the H-TRAA have been proven to be asymptotically optimal. Finally, we demonstrate empirically that the H-TRAA provides orders of magnitude faster convergence compared to the learning automata knapsack game (LAKG) which represents the state-of-the-art for this problem. Further, in contrast to the LAKG, the H-TRAA scales sub-linearly. Based on these results, we believe that the H-TRAA has also tremendous potential to handle demanding real-world applications, particularly those which deal with the world wide web.     

Different types of stability of vector integer optimization problem: General approach

The paper relates the stability of a vector (multiobjective) integer optimization problem to the stability of optimal and nonoptimal solutions of this problem. It is shown that the analysis of several types of stability of the problem of searching for Pareto optimal solutions can be reduced to the analysis of two sets consisting of points that stably belong and do not stably belong to the Pareto set. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 142–148, May–June 2008.     

On the extension of solutions of linear constant-coefficient PDE

We solve the following over-determined boundary value problem (the “extension problem”): Let R(∂) be a matrix whose entries are linear partial differential operators, with constant coefficients. Let Ω be a non-empty, open, bounded, convex set. We consider the homogeneous system R(∂)f=0 in a neighborhood of , subject to the boundary condition f=g in a neighborhood of ∂Ω. For a given g, we give a criterion for the (unique) existence of a smooth solution f to this problem. There are two obvious necessary conditions: g is smooth and R(∂)g=0 in a neighborhood of ∂Ω. We characterize the class of differential operators R(∂) for which the problem is solvable for any g satisfying the necessary conditions. Finally, in the case where the solution is non-unique, we consider the possibility of obtaining uniqueness by fixing several components of the desired solution.     

Remarks on -input bounded-state stability of linear controllable infinite-dimensional systems

It is shown that every eP-input bounded-state stable linear (infinite-dimensional) system x_k+1=A_kx_k+B_ku_k is uniformly power equistable, if it is uniformly equicontrollable.     

A hospital facility layout problem finally solved

This paper presents a history of a difficult facility layout problem that falls into the category of the Koopmans–Beckmann variant of the quadratic assignment problem (QAP), wherein 30 facilities are to be assigned to 30 locations. The problem arose in 1972 as part of the design of a German University Hospital, Klinikum Regensburg. This problem, known as the Krarup 30a upon its inclusion in the QAP library of QAP instances, has remained an important example of one of the most difficult to solve. In 1999, two approaches provided multiple optimum solutions. The first was Thomas Stützles analysis of fitness–distance correlation that resulted in the discovery of 256 global optima. The second was a new branch-and-bound enumeration that confirmed 133 of the 256 global optima found and proved that Stützles 256 solutions were indeed optimum solutions. We report here on the steps taken to provide in-time heuristic solutions and the methods used to finally prove the optimum.