Stability criteria in vector combinatorial bottleneck problems in terms of binary relations

The paper considers a vector (multiobjective) path problem with minimax partial criteria. Solving this problem means finding a Pareto set. Binary relations on a set of paths are used to formulate the necessary and sufficient conditions for five types of problem stability against perturbations of the parameters of a vector criterion. Some sufficient stability conditions in terms of Pareto, Smale, and Slater sets are obtained as corollaries. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 103–111, May–June 2008.     

Stability and regularization of the lexicographic vector problem of quadratic discrete programming

The paper studies the bounds of variation of input parameters for a vector quadratic discrete optimization problem, which do not expand the set of lexicographic optima. A stability criterion is described and a regularization method is presented, which makes it possible to pass from a possibly unstable problem to a series of perturbed stable problems with a previous set of lexicographic optima. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 54–62, March–April, 2000.     

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.     

划分测试用例选择的风险决策方法*

研究了划分测试中划分方案确定情形下,如何在各个子域中合理选择测试用例问题。在充分利用测试者对待测软件导致错误输入分布信息了解的基础上,提出了一种基于风险决策的测试用例选择模型,给出测试用例选择的期望风险准则,并证明了该方法选择的测试用例集具有较高的缺陷检测能力。最后采用蒙特卡罗方法进行仿真模拟,结果表明该方法明显优于划分测试用例的其他选择策略。     

Postoptimal analysis of a vector minimax combinatorial problem

This paper considers a vector combinatorial problem with minimax criteria that provide the greatest uniformity of the parameters of efficient solutions. The necessary and sufficient conditions are obtained for five well-known types of stability of the problem against perturbations of parameters of the vector objective function.     

Tissue P systems with cell separation: attacking the partition problem

Tissue P systems are distributed parallel and non-deterministic computing models in the framework of membrane computing, which are inspired by intercellular communication and cooperation between neurons. Recently, cell separation is introduced into tissue P systems, which enables systems to generate an exponential workspace in a polynomial time. In this work, the computational power of tissue P systems with cell separation is investigated. Specifically, a uniform family of tissue P systems with ce...     

序列折半划分问题的形式化推导

形式化推导是在程序正确性证明理论下所进行的程序开发,最终得到完全正确的算法程序。针对序列折半划分问题,现有的形式化推导方法将推导与证明交替进行,推导过程繁琐且大多无法直接获得可执行程序。为解决上述问题,提出了一种新的序列折半划分问题的形式化推导方法。该方法基于分划递推的核心思想,应用规约变换技术对问题规约进行变换并严格保证一致性,使得在推导过程中无需交替证明,进而导出递推关系式并得到高可靠性抽象算法程序Apla,最终通过转换工具自动生成可执行程序。实现了从程序规约到具体可执行程序的完整程序求精过程。以2个序列算法为例,验证了该方法的有效性和可行性,对相关问题的形式化推导具有指导意义。     

Stability criterion for a lexicographic Boolean optimization problem

A vector Boolean sequential minimization problem for absolute values of linear functions is considered. Necessary and sufficient condition for stability of this type that is a discrete analogue of the upper Hausdorff semicontinuity of a point-to-set mapping is established. This mapping associates a set of lexicographic optima with each set of problem parameters. The study was sponsored by the Fundamental and Applied Research Interuniversity Program of the Republic of Belarus (Grant 492/28). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 127–132, July–August 2007.     

A Continuous problem of optimal partition with a nondifferentiable functional

A continuous problem of decomposition of an optimal set into disjoint subsets is considered. This problem is characterized by a non-differentiable performance criterion, the availability of a boundary-value problem for a parabolic type equation, and dependence of the initial condition function on the partition of some flat set. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 115–125, July–August, 2000.     

Comparative Analysis of Different Types of Stability with Respect to Constraints of a Vector Integer-Optimization Problem

The problem of finding the Pareto set among integer points of a convex polyhedron is considered in the paper. Various types of stability of this multicriterion problem to changes of initial data under constraints are analyzed. Necessary and sufficient conditions for different types of stability with respect to constraints are obtained.     

Minimum common string partition: on solving large‐scale problem instances

Minimum common string partition is an NP‐hard combinatorial optimization problem from the bioinformatics field. The current state‐of‐the‐art algorithm is a hybrid technique known as construct, merge, solve, and adapt (CMSA). This algorithm combines two main algorithmic components: generating solutions in a probabilistic way and solving reduced subinstances obtained from the tackled problem instances, if possible, to optimality. However, the CMSA algorithm was not intended for application to very large problem instances. Therefore, in this paper we present a technique that makes CMSA, and other available algorithms for this problem, applicable to problem instances that are about one order of magnitude larger than the largest problem instances considered so far. Moreover, a reduced variable neighborhood search (RVNS) for solving the tackled problem, based on integer programming, is introduced. The experimental results show that the modified CMSA algorithm is very strong for problem instances based on rather small alphabets. With growing alphabet size, it turns out that RVNS has a growing advantage over CMSA.     

Stability, pseudostability, and quasistability of a multicriterion problem on a system of subsets

Stability, pseudostability, and quasistability, and the stability kernel of a multicriterion problem are considered on a system of subsets with Σ-minimax and Σ-minimin criteria for perturbations of the parameters of a vector criterion. Lower attainable estimates are found for the radii of stability, quasi stability, and pseudostability and the stability kernel of such a problem in the space of perturbed parameters for the case of the Chebyshev norm. This work has been carried out with financial support from the Fundamental Research Fund of the Republic of Belorussia and the German Fund of Academic Exchanges (DAAD), FRG. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 111–124, September–October, 1999.     

Stability of a vector integer quadratic programming problem with respect to vector criterion and constraints

The paper analyzes five types of stability against perturbations of initial data in criterion functions and constraints of vector integer quadratic optimization problems. Necessary and sufficient conditions are proved for all the types of stability. The relationship among stability with respect to changes of vector criterion coefficients, stability with respect to changes of initial data in constraints, and stability with respect to vector criterion and constraints is established. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 63–72, September–October 2006.     

用遗传算法求解最优QoS 划分与路由问题*

未来的通信网将充分支持各种QoS业务,QoS划分与路由问题研究针对QoS业务的最优化问题.首次提出了求解最优QoS划分和路由问题的遗传算法.该算法以K条最短路径来代替全网最优路径,大大加快了算法的运行速度.仿真结果证明了该算法的合理性和有效性.     

The vectorization of the partition problem

This paper describes a vectorized algorithm for the partition problem, a famous NP-complete problem. A set of partition problems that required 518 seconds to be solved on a VAX/8550 computer would require only 2 seconds on the Cyber 205 under the vector mode. A partition problem with n equal to 1000 was solved in only 6.34 seconds.     

采用双交叠模糊分划的T-S模糊系统的稳定性分析

研究前件变量采用双交叠模糊分划的T-S模糊系统的稳定性问题．首先针对自由系统,将连续时间系统的、基于最大交叠规则组的稳定性分析方法推广应用于离散时间系统,并采用模糊Lyapunov方法得到了稳定性的新结论．采用非并行分布补偿控制律,针对受控系统也得到了相应的结论．这些结论比已有的结果更加宽松．仿真例子验证了该稳定性结论．     

基于模糊分割和邻近对的支持向量机分类器

支持向量机算法对噪声点和异常点是敏感的,为了解决这个问题,人们提出了模糊支持向量机,但其中的模糊隶属度函数需要人为设置。提出基于模糊分割和邻近对的支持向量机分类器。在该算法中,首先根据聚类有效性用模糊c-均值聚类算法分别对训练集中的正负类数据聚类;然后,根据聚类结果构造c个二分类问题,求解得c个二分类器;最后,用邻近对策略对样本点进行识别。用4个著名的数据集进行了数值实验,结果表明该算法能有效提高带噪声点和异常点数据集分类的预测精度。     

用双种群混合遗传算法求解最优QoS划分问题

在取决于性能的价格机制下,最优QoS划分用于沿路由路径最优化地分配QoS参数值,以使得通信总费用最小。提出了求解最优QoS划分问题(OPQ问题)的双种群混合遗传算法。该算法充分利用了遗传算法的全局搜索优势和模拟退火算法的局部搜索优势,并且两个相互独立的子群体周期性的交流最优染色体,进一步提高了性能。仿真结果表明了该算法的有效性。     

Stability radius of an efficient solution of a vector problem of integer linear programming in the Gölder metric

A vector (multicriterion) problem of integer linear programming is considered on a finite set of feasible solutions. A metric l_p, 1 ≤ p ≤ ∞, is defined on the parameter space of the problem. A formula of the maximum permissible level of perturbations is obtained for the parameters that preserve the efficiency (Pareto optimality) of a given solution. Necessary and sufficient conditions of two types of stability of the problem are obtained as corollaries. This work has been carried out with financial support from the Belgosuniversity within the framework of the Intercollegiate Program “Fundamental and Applied Investigations” (project No. 492/28). __________ Translated from Kibernetika I Sistemnyi Analiz, No. 4, pp. 175–181, July–August 2006.