Analysis of mathematical models and methods of solving combinatorial optimization problems on game-type permutations

The paper is concerned with an optimization problem on game-type permutations, where one or both players have combinatorial constraints on their strategies. A mathematical model of such problems is constructed and analyzed. A modified graphical method is proposed to solve (2xn)-and (mx2)-dimensional problems. High-dimensional problems are reduced to linear programming and combinatorial optimization problems. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 103–114, November–December 2007.     

Algorithmic soluyion of two parametric optimization problems on a set of complete combinations

Algorithmic solutions of parametric problems of two types with a parameter in the objective function and with a parameter in the system of constraints are considered in a Euclidean combinatorial set of combinations with repetitions. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 160–165, November–December, 1999.     

New means of cybernetics,informatics, computer engineering,and systems analysis

The class of combinatorial problems equivalent to the problem of determination of relative positions of n interval sequences is formulated. It is shown that an adequate mathematical model of solving a stated problem is a finite dynamic memoryless automaton and that the adequate mathematical apparatus is continuous logic. Algorithms that solve the problem are constructed. Misc  Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 173–181, May-June 2009. Original article submitted July 4, 2007.     

Combinatorial properties of noninteger vertices of a polytope in a three-index axial assignment problem

It is proved that, for any r ∈ { 2n, 2n + 1,…, 3n−2} and only for such r, the polytope of a three-index axial assignment problem of order n, n ≥ 2, contains completely r-noninteger vertices (r-CNVs), i.e., vertices such that all their positive components are fractional and their number equals r. For each r ∈ {2n, 2n + 1,…, 3n −2}, all the types of r-CNVs are characterized and the combinatorial properties of completely r-noninteger vertices of the polytope are studied. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 33–44, January–February 2007.     

An approach to solving discrete vector optimization problems over a combinatorial set of permutations

Complex discrete multicriteria problems over a combinatorial set of permutations are analyzed. Some properties of an admissible domain for a combinatorial multicriteria problem embedded into an arithmetic Euclidian space are considered. Optimality conditions are obtained for different types of effective solutions. A new approach to solving the problems formulated is constructed and substantiated. This work was supported by the Fundamental Research Fund of Ukraine (project Φ251/094). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 158–172, May–June 2008.     

An approach to determining Shor’s dual quadratic estimates

For a general quadratic problem, an analog is formulated as a homogeneous quadratic problem. The estimates ψ* constructed based on Shor’s dual quadratic estimates for these problems are proved to be equal. It is shown that, for the case of a homogeneous quadratic problem, finding ψ* is reduced to an unconstraint minimization problem for a convex function. The study was partially sponsored by the grant UKM2-2812-KV-06 (CRDF Cooperative Grants Program). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 89–99, March–April 2008.     

Antibody-based computing

An application of the antibody’s flexible recognition (i.e. multi-reactivity) to antigenic epitopes to a combinatorial computing is just getting started. The present study discusses an antibody-based computation algorithm to solve a combinatorial problem: the stable marriage problem. The stable marriage problem supposes n men and n women, and each person ranks all members of the opposite sex in a strict order of preference. Under given preference lists, to detect all of “stable” n couples including no affair pairs means to solve this problem. Our algorithm replaces a man and a woman with an antigenic epitope and an antibody respectively, and re-scales a man (woman)’s preference to a woman (man) as strength of a binding affinity between an epitope to the man and an antibody to the woman. Under these settings, we demonstrate a parallel progression of immune reactions can solve the stable marriage problem. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Combinatorial optimization under uncertainty

In this paper, the general problem of Euclidean combinatorial optimization under uncertainty is formulated for the first time and the concepts of a stochastic multiset, a multiset of fuzzy numbers, a stochastic Euclidean combinatorial set, and general Euclidean combinatorial set of fuzzy stochastic numbers that combines the properties of both types of uncertainty are introduced. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 35–44, September–October 2008.     

A study on a quantum-inspired evolutionary algorithm based on pair swap

A quantum-inspired evolutionary algorithm (QEA) is proposed as a stochastic algorithm to perform combinatorial optimization problems. The QEA is evolutionary computation that uses quantum bits and superposition states in quantum computation. Although the QEA is a coarse-grained parallel algorithm, it involves many parameters that must be adjusted manually. This paper proposes a new method, named pair swap, which exchanges each best solution information between two individuals instead of migration in the QEA. Experimental results show that our proposed method is a simpler algorithm and can find a high quality solution in the 0-1 knapsack problem. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

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.     

Construction of convex continuations for functions defined on a hypersphere

Construction of convex continuations for functions defined on the vertices of some combinatorial polyhedra, in particular the permutation polyhedron and the arrangement polyhedron, has been studied in [1, 2]. Subsequently this result has been generalized to functions defined at the extreme points of an arbitrary polyhedron [3]. For purposes of combinatorial optimization [4-6] it is relevant to consider the existence and construction of convex continuations from continua, in particular, when the function is defined on a hypersphere in thek-dimensional space. Unfortunately, passage to the limit from discrete sets to continua does not produce positive results in this case. We are thus forced to develop special approaches to investigating the existence of convex continuations of functions defined on continua. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 27–36, March–April, 1998.     

Water wave optimization for combinatorial optimization: Design strategies and applications

Although the community of nature-inspired computing has witnessed a wide variety of metaheuristics, it often requires considerable effort to adapt them to different combinatorial optimization problems (COPs), and few studies have been devoted to reducing this burden. This paper proposes a systematic approach that consists of a set of basic steps and strategies for adapting water wave optimization (WWO), a simple and generic metaheuristic, to concrete heuristic algorithms for different COPs. Taking advantages of the generic algorithmic framework, designers can only focus on adapting the prorogation operator and the wavelength calculation method according to the combinatorial properties of the given problem, and thus easily derive efficient problem-solving algorithms. We illustrate and test our approach on the flow-shop scheduling problem (FSP), the single-objective multidimensional knapsack problem (MKP), and the multi-objective MKP, and then present an application to a machine utilization optimization problem for a large manufacturing enterprise. The results demonstrate that our approach can derive concrete algorithms that are competitive to the state-of-the-arts. Our approach also provides insights into the adaptation of other metaheuristics and the development of new metaheuristics for COPs.     

A class of inverse problems for discontinuous systems

We analyze a class of inverse parametric problems for dynamic processes described by systems of ordinary differential equations whose form and piecewise-constant parameters depend on what subdomain in the state space the state of the process belongs to. The study was supported by the INTAS (Project No. 06-1000017-8909). Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 142–152, November–December 2008.     

Tailoring IT support to communities of practice

Many organizations have benefited from recognizing communities of practice (COPs) operating in their midst. By identifying a group as a COP, an organization has made a critical skill area visible. Without this awareness it would be more likely, for example, that the corporate talent in auditing software processes could quietly disappear. With the importance of COPs established, organizations can now turn their attention to ensuring that their IT and knowledge management systems enable COPs to flourish. A simple folder on a corporate server to share documents is an example of such support. More comprehensive support to a COP may include virtual space on the corporate intranet for synchronous and asynchronous collaboration, expertise location, and content structuring (B. Lewis, "On-Demand KM: A Two-Tier Architecture", IT Professional, Jan.-Feb. 2002, pp. 27-33). As organizations decide how to support COPs, they should know that COPs are not in any way uniform entities. There is wide variation among COPs and understanding these differences can go a long way toward providing support that is truly well matched to the needs of each one. Two observations are keys to understanding the variety of COPs that are candidates for organizational support: The number of potential COPs is great, and, there are many kinds of groups and communities; not all of them are COPs.     

Finding Total Unimodularity in Optimization Problems Solved by Linear Programs

A popular approach in combinatorial optimization is to model problems as integer linear programs. Ideally, the relaxed linear program would have only integer solutions, which happens for instance when the constraint matrix is totally unimodular. Still, sometimes it is possible to build an integer solution with the same cost from the fractional solution. Examples are two scheduling problems (Baptiste and Schieber, J. Sched. 6(4):395–404, 2003; Brucker and Kravchenko, J. Sched. 11(4):229–237, 2008) and the single disk prefetching/caching problem (Albers et al., J. ACM 47:969–986, 2000). We show that problems such as the three previously mentioned can be separated into two subproblems: (1) finding an optimal feasible set of slots, and (2) assigning the jobs or pages to the slots. It is straigthforward to show that the latter can be solved greedily. We are able to solve the former with a totally unimodular linear program, from which we obtain simple combinatorial algorithms with improved worst case running time.     

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.     

An approach to solution uniqueness in game problems

A new concept of strong conflict equilibrium is proposed that supplements the well-known fundamental system of conflict equilibria and considerably increases the possibility of finding a unique strongest equilibrium (solution) in any game problem. The efficiency of this new equilibrium is illustrated by static and dynamic game problems. This work was carried out under the program “Basic foundations of information technologies and systems” of the Russian Academy of Science (Project No. 1–3). Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 116–127, March–April 2009.     

On the theory of realization of quasilinear systems described by differential equations in a Hilbert space

We consider a system-theoretic methodology of mathematical modeling involved in the structural identification of continuous nonlinear dynamic systems with programmable position control. We present various functional-analytical modifications of a characteristic criterion for exogenous (“input-output”) behavior of these systems that permit, by virtue of this criterion, model realizations in the class of quasilinear nonstationary ordinary differential equations describing states in a separable Hilbert space. The study was sponsored by the Russian Foundation for Basic Research (Grant No. 05-01-00623), Basic Research Program No. 22 of the Presidium of the Russian Academy of Sciences, Grant of the President of the Russian Federation for the Governmental Support of Scientific Schools of the Russian Federation (No. NSh-1676.2008). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 82–95, September–October 2008.     

Stability of a combinatorial vector partition problem

The vector variant of the partition problem is considered. It is shown that the coincidence of the Pareto and Slater sets is the necessary and sufficient condition of stability of the problem with respect to its functional. __________ Translated from Kibernetika i Sistemny i Analiz, No. 3, pp. 177–181, May–June 2007.     

On Parabolic Boundary Layers for Convection–Diffusion Equations in a Channel: Analysis and Numerical Applications

In this article we discuss singularly perturbed convection–diffusion equations in a channel in cases producing parabolic boundary layers. It has been shown that one can improve the numerical resolution of singularly perturbed problems involving boundary layers, by incorporating the structure of the boundary layers into the finite element spaces, when this structure is available; see e.g. [Cheng, W. and Temam, R. (2002). Comput. Fluid. V.31, 453–466; Jung, C. (2005). Numer. Meth. Partial Differ. Eq. V.21, 623–648]. This approach is developed in this article for a convection–diffusion equation. Using an analytical approach, we first derive an approximate (simplified) form of the parabolic boundary layers (elements) for our problem; we then develop new numerical schemes using these boundary layer elements. The results are performed for the perturbation parameter ε in the range 10⁻¹–10⁻¹⁵ whereas the discretization mesh is in the range of order 1/10–1/100 in the x-direction and of order 1/10–1/30 in the y-direction. Indications on various extensions of this work are briefly described at the end of the Introduction.Dedicated to David Gottlieb on his 60th birthday.