Computational experience with general cutting planes for the Set Covering problem

In this paper we present a cutting plane algorithm for the Set Covering problem. Cutting planes are generated by running an “exact” separation algorithm over the subproblems defined by suitably small subsets of the formulation constraints. Computational results on difficult small-medium size instances are reported.     

覆盖下近似算子的拓扑性质

在不限制U为有限论域的情况下,研究了覆盖下近似算子XL和CL的拓扑性质。证明了覆盖下近似算子XL是内部算子,而且由XL生成的拓扑TXL为包含由覆盖C本身作为子基生成的拓扑TC的最小Alexandrov拓扑。特别地,当U为有限论域时,TXL=TC.然而,覆盖下近似算子CL不是内部算子。当覆盖C为某拓扑的基时,CL是内部算子,且此时由CL生成的拓扑TCL与TC是同一个拓扑。若进一步要求U为有限论域,则TCL=TXL=TC,进而CL=XL.     

覆盖S-粗集模型的性质

讨论基于覆盖理论的S-粗集模型的性质,给出了S-粗集生成的拓扑结构,证明了覆盖S-粗集模型与自反、传递关系下的S-粗集模型是等价的。     

完全分配格上的覆盖粗糙集模型

将集合论中的覆盖概念抽象到完全分配格L上,利用它定义格L上关于覆盖的上(下)近似算子,给出格L上覆盖粗糙集模型.文中先讨论格L上覆盖的相关性质,进而研究了覆盖上(下)近似算子的性质,得到若干结果.     

基于覆盖粗糙集理论中的约简与求核

提出基于分辨矩阵的求覆盖粗糙集约简与核的方法,在Zakowski提出的覆盖粗糙集模型的基础上,利用分辨矩阵的一些性质,把文献[10]中的粗糙集理论中的约简与求核方法应用到基于覆盖的粗糙集理论中,既简化了覆盖粗糙集理论中的约简与求核过程,又推广了文献[10]的方法,最后举例说明此方法的有效性。     

区间粗糙数覆盖粗糙集模型

现有覆盖粗糙集仅讨论了属性值为实数、区间数或有限集值的情况,对属性值为区间粗糙数的讨论尚未见到。为此,文章提出了基于区间粗糙数的覆盖粗糙集模型。在定义了区间粗糙数距离的基础上,结合参数α和γ定义了相容度的概念,提出了相容关系和相容类的定义;然后定义了集合离散度的概念,对以相容类作为近似算子的上下近似进行了改进,提出了基于ξ阈值的集合离散度的上下近似和基于最小集合离散度的上下近似,证明了这两种上下近似的定义均提高了原有模型的精确度;最后讨论了基于最小集合离散度覆盖粗糙集模型的一些性质。     

覆盖粗糙集模型增值算子及其性质

为了给不断发生变化的数据库的知识发现提供新的数学工具,本文引进覆盖粗糙集模型的确定增值算子ZX(Y)和不确定增值算子ZX(Y),并讨论了它们的有关性质,即通过研究两个新集合hX(x)、lX(x)的性质(定理2.1和定理2.2),给出并证明了两个增值算子的性质(定理2.3和定理2.4)。     

覆盖广义粗糙集的模糊性

在研究覆盖广义粗糙集的基础上,利用两个距离函数Hamming和Euclidean距离函数,结合模糊集的最近寻常集,引入了覆盖广义粗糙集模糊度的概念,给出了一种模糊度计算方法,并证明了该模糊度的一些重要性质。这些结果在覆盖广义粗糙集的理论研究和应用都发挥着一定作用。     

一个基于模糊随机集的粗糙近似算子的性质及应用

利用贴近度（或相似度）N（B,A）提出了模糊随机近似空间里的一种基于模糊随机集的粗糙近似算子,讨论了该种近似算子的一些主要性质;成功地探讨其在Fuzzy模式识别中的应用;最后给出了具体的例子说明了该算子用于Fuzzy模式识别的可行性。     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

Reformulation of the support set selection problem in the logical analysis of data

The paper is concerned with the problem of binary classification of data records, given an already classified training set of records. Among the various approaches to the problem, the methodology of the logical analysis of data (LAD) is considered. Such approach is based on discrete mathematics, with special emphasis on Boolean functions. With respect to the standard LAD procedure, enhancements based on probability considerations are presented. In particular, the problem of the selection of the optimal support set is formulated as a weighted set covering problem. Testable statistical hypothesis are used. Accuracy of the modified LAD procedure is compared to that of the standard LAD procedure on datasets of the UCI repository. Encouraging results are obtained and discussed.     

Approximation algorithms for constrained generalized tree alignment problem

In generalized tree alignment problem, we are given a set S of k biologically related sequences and we are interested in a minimum cost evolutionary tree for S. In many instances of this problem partial phylogenetic tree for S is known. In such instances, we would like to make use of this knowledge to restrict the tree topologies that we consider and construct a biologically relevant minimum cost evolutionary tree. So, we propose the following natural generalization of the generalized tree alignment problem, a problem known to be MAX-SNP Hard, stated as follows:

Constrained Generalized Tree Alignment Problem [S. Divakaran, Algorithms and heuristics for constrained generalized alignment problem, DIMACS Technical Report 2007-21, 2007]: Given a set S of k related sequences and a phylogenetic forest comprising of node-disjoint phylogenetic trees that specify the topological constraints that an evolutionary tree of S needs to satisfy, construct a minimum cost evolutionary tree for S.

In this paper, we present constant approximation algorithms for the constrained generalized tree alignment problem. For the generalized tree alignment problem, a special case of this problem, our algorithms provide a guaranteed error bound of 2−2/k.     

An Inner Approximation Method for Optimization over the Weakly Efficient Set

In this paper, we consider an optimization problem which aims to minimize a convex function over the weakly efficient set of a multiobjective programming problem. To solve such a problem, we propose an inner approximation algorithm, in which two kinds of convex subproblems are solved successively. These convex subproblems are fairly easy to solve and therefore the proposed algorithm is practically useful. The algorithm always terminates after finitely many iterations by compromising the weak efficiency to a multiobjective programming problem. Moreover, for a subproblem which is solved at each iteration of the algorithm, we suggest a procedure for eliminating redundant constraints.     

Approximation of the supply scheduling problem

The supply scheduling problem consists in finding a minimum cost delivery plan from a set of providers to a manufacturing unit, subject to given bounds on the shipment sizes and subject to the demand at the manufacturing unit. We provide a fully polynomial time approximation scheme for this problem.     

基于最小描述交的覆盖广义粗糙集

针对Bonikowski覆盖广义粗糙集模型的不足,给出了基于最小描述史的覆盖上下近似算子.通过和Pawlak经典粗糙集以及Bonikowski的覆盖广义粗糙集比较,发现给出的覆盖上、下近似算子具有了对偶关系,并得到了相关重要性质;进一步讨论了在新定义下覆盖广义粗糙集的约简和公理化问题,丰富了覆盖广义粗糙条理论,并为覆盖广义粗糙集的应用提供了更确切的理论根据.     

基于覆盖的模糊粗糙集模型

讨论基于覆盖理论的模糊粗糙集模型。给出了模糊集的粗糙上、下近似算子,讨论了算子的基本性质,证明了覆盖粗糙集模型下所有模糊集的下近似构成一个模糊拓扑,并得到了覆盖模糊粗糙集模型的公理化描述。