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.     

Solution of Optimization Problems with Fractional-Linear Objective Functions and Additional Linear Constraints on Permutations

The statement of a problem of Euclidean combinatorial optimization with a fractional-linear objective function on a common set of permutations and with additional linear constraints is formulated. A problem with a fractional-linear objective function is transformed into that with a linear objective function. An approach is proposed to the solution of such problems, and a method of combinatorial truncation of solutions of problems of combinatorial type with fractional-linear objective functions on permutations is developed.     

The values of a linear form on a set of permutations

Cybernetics and Systems Analysis -     

Systems of generators of automaton permutations groups

Systems of induced generating actions of automaton permutations groups on words of length r are investigated. A family of irreducible systems of generators is constructed, and the cardinality of such systems is found to be related with r. The infinite generativity (even in the topological sense) of groups of all automaton permutations, finite automaton permutations, and finitary automaton permutations is established; the well-known proof of this fact contained an error. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 121–133, May–June, 2000.     

A linear kernel for a planar connected dominating set

We provide polynomial time data reduction rules for Connected Dominating Set on planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.     

Calculation of the number of complete mappings for permutations

The computation time for counting “good” permutations rapidly grows as the length of permutations increases. The paper presents algorithms for enumeration of “good” permutations. Algorithms reducing twice the number of “good” permutations that should be counted are considered along with the algorithm employing the concept of weight of a “good” permutation. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 106–110, March–April, 2000.     

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.     

Analysis of an algorithm for solution of conditional optimization problems with linear-fractional objective functions over permutations

A method is considered to solve a conditional optimization problem with a linear-fractional objective function over permutations. The performance of sub algorithms to solve this problem is evaluated. The practical efficiency of the algorithm is analyzed by conducting numerical experiments. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 133–146, July–August 2007.     

Fast algorithms for the dominating set problem on permutation graphs

AnO(n log logn) (resp.O(n² log² n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FÄrber and Keil, where they use dynamic programming to get anO(n² (resp.O(n³)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.This research was supported in part by the National Science Foundation under Grant CCR-8905415 to Northwestern University.     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).     

基于粗糙集的多维关联规则挖掘方法

海量的数据使得关联规则挖掘非常耗时,而并非所有的规则都是用户感兴趣的,应用传统的挖掘方法会挖掘出许多无关信息。此外,目前大部分算法是针对单维规则的。因此,定义了一种挖掘语言使得用户可以指定感兴趣的项以及关联规则的参数（如支持度,置信度等）,并提出一种基于粗糙集理论的多维关联规则挖掘方法,动态生成频繁集和多维关联规则,减少频繁项集的生成搜索空间。实例分析验证该算法的可行性与有效性。     

置换矩阵算法在粗糙集属性约简中的应用

介绍了粗糙集的布尔矩阵表示和置换矩阵的概念,导出了属性约简与置换矩阵之间的关系,讨论了逻辑关系方程组解的理论,提出了基于置换矩阵的粗糙集属性约简的新算法,通过实例分析证明了该方法的有效性,表明该算法在粗糙集属性约简中具有参考价值,对粗糙集理论的应用具有一定的实际意义。     

On the independence number and Hamiltonicity of uniform random intersection graphs

In the uniform random intersection graphs model, denoted by G_n,m,λ, to each vertex v we assign exactly λ randomly chosen labels of some label set M of m labels and we connect every pair of vertices that has at least one label in common. In this model, we estimate the independence number α(G_n,m,λ), for the wide range m=⌊n^α⌋,α<1 and λ=O(m^1/4). We also prove the Hamiltonicity of this model by an interesting combinatorial construction. Finally, we give a brief note concerning the independence number of G_n,m,p random intersection graphs, in which each vertex chooses labels with probability p.     

Properties of the reachable set of control systems

We investigate some properties of the reachable set of a control system. Representing the system as a differential inclusion and using proximal Hamilton–Jacobi equation we describe its graph. We work in infinitely dimensional Hilbert space and use one sided Lipschitz approach. The funnel equation is considered in the last section. That equation describes the reachable set in arbitrary Banach space. We consider also the autonomous case and prove the existence of a limit of the reachable set.     

属性集重要性的研究

在决策表中,不同的属性和属性集可能具有不同的重要性。通过分析单一属性重要性和属性集重要性,得出单一属性不重要而包含它的属性集不一定不重要以及单一属性重要而包含它的属性集一定重要的结论。因此,研究属性集重要性具有重要意义,与单一属性重要性相比,属性集重要性更加可信。     

OOESAlgorithm.jl: a julia package for optimizing a linear function over the set of efficient solutions for biobjective mixed integer linear programming

We present OOESAlgorithm.jl , a package for optimizing a linear function over the efficient set of biobjective mixed integer linear programs. The proposed package extends our recent study (see Sierra‐Altamiranda and Charkhgard [INFORMS Journal on Computing, https://doi.org/10.1287/ijoc.2018.0851]) by adding two main features: (a) in addition to CPLEX, the package allows employing any single‐objective solver supported by MathProgBase.jl , for example, GLPK, CPLEX, and SCIP; (b) the package supports execution on multiple processors and is compatible with the JuMP modeling language. An extensive computational study shows the efficacy of the package and its features.     

一种耦合功能集割裂解耦方法

以设计矩阵表示的耦合功能集为研究对象,针对耦合功能集中功能耦合的程度,给出了一种度量的方法;使用混沌思想改进了粒子群算法,以参数可行解的减少量为目标函数,实现了耦合功能的顺序规划。最后通过某汽车停车档的设计实例验证了算法的有效性。     

Fuzzy model tuning based on a training set with fuzzy model output values

The paper considers the training of a fuzzy model with the help of a training set with fuzzy model output values. Two ways are proposed for constructing fuzzy rule-based multifactor models that produce fuzzy numbers at their outputs. The problem of tuning such fuzzy models on the basis of a fuzzy training set is formulated, methods of its solution are considered, and relevant examples are presented. Computational experiments showed that training based on fuzzy data improves the modeling accuracy for both crisp and fuzzy test sets. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 26–32, May–June 2007.