A Meta-heuristic with Orthogonal Experiment for the Set Covering Problem

This paper reports an evolutionary meta-heuristic incorporating fuzzy evaluation for some large-scale set covering problems originating from the public transport industry. First, five factors characterized by fuzzy membership functions are aggregated to evaluate the structure and generally the goodness of a column. This evaluation function is incorporated into a refined greedy algorithm to make column selection in the process of constructing a solution. Secondly, a self-evolving algorithm is designed to guide the constructing heuristic to build an initial solution and then improve it. In each generation an unfit portion of the working solution is removed. Broken solutions are repaired by the constructing heuristic until stopping conditions are reached. Orthogonal experimental design is used to set the system parameters efficiently, by making a small number of trials. Computational results are presented and compared with a mathematical programming method and a GA-based heuristic.     

基于改进遗传算法的集合覆盖问题

集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.     

Computing Approximate Solutions of the Maximum Covering Problem with GRASP

We consider the maximum covering problem, a combinatorial optimization problem that arises in many facility location problems. In this problem, a potential facility site covers a set of demand points. With each demand point, we associate a nonnegative weight. The task is to select a subset of p > 0 sites from the set of potential facility sites, such that the sum of weights of the covered demand points is maximized. We describe a greedy randomized adaptive search procedure (GRASP) for the maximum covering problem that finds good, though not necessarily optimum, placement configurations. We describe a well-known upper bound on the maximum coverage which can be computed by solving a linear program and show that on large instances, the GRASP can produce facility placements that are nearly optimal.     

一类覆盖问题的组合学分析

从组合学的角度研究了一类随机选取集合中元素的覆盖问题,得到了重复性地、随机独立地、等概地选取某个有限集合中的元素,不遗漏地取遍所有元素所需的次数的期望,给出了理论和实验的数据结果.并且分析了该问题在现实世界中的一些实例.而且对于该问题的扩展模型—每次抽取集合中t个不同元素—进行了一些探讨.     

On Infinite Disjoint Congruence Covering Systems

In this paper we show that for any α∈(0,l] there exists an infinite disjoint covering system {a1(modni)}i=1∞ such that     

Two-phase method and Lagrangian relaxation to solve the Bi-Objective Set Covering Problem

This paper deals with the Bi-Objective Set Covering Problem, which is a generalization of the well-known Set Covering Problem. The proposed approach is a two-phase heuristic method which has the particularity to be a constructive method using the primal-dual Lagrangian relaxation to solve single objective Set Covering problems. The results show that this algorithm finds several potentially supported and unsupported solutions. A comparison with an exact method (up to a medium size), shows that many Pareto-optimal solutions are retrieved and that the other solutions are well spread and close to the optimal ones. Moreover, the method developed compares favorably with the Pareto Memetic Algorithm proposed by Jaszkiewicz.     

Robust Algorithms for the Stable Set Problem

The stable set problem is to find in a simple graph a maximum subset of pairwise non-adjacent vertices. The problem is known to be NP-hard in general and can be solved in polynomial time on some special classes, like cographs or claw-free graphs. Usually, efficient algorithms assume membership of a given graph in a special class. Robust algorithms apply to any graph G and either solve the problem for G or find in it special forbidden configurations. In the present paper we describe several efficient robust algorithms, extending some known results.     

Algorithms for the Set Covering Problem

The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.     

图论中独立支配集的求解问题并未解决

用反例证明了文[1]中的最大独立集算法和最小支配集算法的结论都是错误的,因而图论中独立支配集的求解问题并没有解决．     

Solution techniques for the Large Set Covering Problem

Given a finite set E and a family F={E₁,…,E_m} of subsets of E such that F covers E, the famous unicost set covering problem (USCP) is to determine the smallest possible subset of F that also covers E. We study in this paper a variant, called the Large Set Covering Problem (LSCP), which differs from the USCP in that E and the subsets E_i are not given in extension because they are very large sets that are possibly infinite. We propose three exact algorithms for solving the LSCP. Two of them determine minimal covers, while the third one produces minimum covers. Heuristic versions of these algorithms are also proposed and analysed. We then give several procedures for the computation of a lower bound on the minimum size of a cover. We finally present algorithms for finding the largest possible subset of F that does not cover E. We also show that a particular case of the LSCP is to determine irreducible infeasible sets in inconsistent constraint satisfaction problems. All concepts presented in the paper are illustrated on the k-colouring problem which is formulated as a constraint satisfaction problem.     

A Note on the Set Covering Problem

A previously published work on a ‘probabilistic’ formulation of the set covering problem is discussed. Attention is drawn to the dependence of the feasible locations of facilities on the way the continuous space of incidents is divided into subregions when using either the above formulation or the standard deterministic formulation of the set covering problem.     

A Covering Problem for Tori

The problem of covering an n-dimensional torus with n-dimensional grid graphs is studied. This is the dual problem of a packing problem concerning the capacity of a graph, which has been studied in information theory. It is related to several other problems as well, including weighted coverings, Kellers cube-tiling problem, and the recreational problem of how to obtain zero correct predictions in the football pools. Motivated by the last problem, bounds on the minimum size of such coverings are tabulated for q = 3, p = 2, and small n.AMS Subject Classification: 05C70, 94B25.     

用基础解系解某些条件极值问题

通过对线性的目标函数在线性的约束条件下的极值问题的分析,得到这类极值问题一般是不能用拉格朗日乘数法求解.通过用基础解系的方法进行求解这类问题,实例表明,这种方法是可行有效的.     

AT-free图的配对控制集算法

本文给出了配对控制集在AT-free图的BFS-树上分布的结构性质．利用这些性质，我们给出了求解AT-free图类最小配对控制集的多项式时间算法．     

有关拓扑学与覆盖粗糙集的一些结论

引入了拓扑覆盖的概念,并结合最小描述元对有限论域上的拓扑覆盖加于研究,得出了拓扑覆盖的最简覆盖和基与最小描述元之间的关系.介绍了在基于有限论域U上的覆盖,构造U上的一个拓扑的方法.并且在最小描述元的基础上将划分下的粗糙隶属函数推广至一般覆盖下的粗糙隶属函数,而后介绍了其相关运用.     

带参在线箱覆盖问题

我们考虑在线箱覆盖问题,其中所有被装元素的尺寸不超过1／k（k是正整数）．我们给出了该问题的紧上界并证明简单算法NextFit即是最好的．这个结果推广了Csirik与Totik1988年的工作．最后,我们还给出了二维情形的一个非平凡的上界．     

A Genetic Algorithm for the Set Covering Problem

In this paper, the set covering problem (SCP) is considered. Several algorithms have been suggested in the literature for solving it. We propose a new algorithm for solving the SCP which is based on the genetic technique. This algorithm has been implemented and tested on various standard and randomly generated test problems. Preliminary results are encouraging, and are better than the existing heuristics for the problem.     

Using Homogeneous Weights for Approximating the Partial Cover Problem

In this paper we consider the natural generalizations of two fundamental problems, the Set-Cover problem and the Min-Knapsack problem. We are given a hypergraph, each vertex of which has a nonnegative weight, and each edge of which has a nonnegative length. For a given threshold , our objective is to find a subset of the vertices with minimum total cost, such that at least a length of of the edges is covered. This problem is called the partial set cover problem. We present an O(|V|² + |H|)-time, Δ_E-approximation algorithm for this problem, where Δ_E ≥ 2 is an upper bound on the edge cardinality of the hypergraph and |H| is the size of the hypergraph (i.e., the sum of all its edges cardinalities). The special case where Δ_E = 2 is called the partial vertex cover problem. For this problem a 2-approximation was previously known, however, the time complexity of our solution, i.e., O(|V|²), is a dramatic improvement.We show that if the weights are homogeneous (i.e., proportional to the potential coverage of the sets) then any minimal cover is a good approximation. Now, using the local-ratio technique, it is sufficient to repeatedly subtract a homogeneous weight function from the given weight function.     

箱覆盖问题的半定松驰算法

箱覆盖问题是NP困难问题中的经典问题，得到了广泛地研究，九十年代以来，半定松驰策略被用来求解组合优化问题，取得了很好的结果[13]，本文首次给箱覆盖问题的半定松驰算法，算法的理论分析结果表明它适合于求解大规模的箱覆盖问题。     

决策模糊集覆盖系数的实用计算方法

研究了经济学中广泛应用的决策模糊理论中模糊集覆盖系数的性质,并据此提出了无须通过繁杂的统计实验就能够计算覆盖系数的实用方法,进而提出了模糊集交并运算算子.用两个算例说明了该方法和算子与实际情形相符,具有可行性.