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)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.     

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 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.     

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 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.     

Maximally Disjoint Solutions of the Set Covering Problem

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP-complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, extensive computational tests are given demonstrating the nature of these algorithms. These tests are carried out both on randomly generated problems and on problems found in the literature.     

Robust multi-market newsvendor models with interval demand data

We present a robust model for determining the optimal order quantity and market selection for short-life-cycle products in a single period, newsvendor setting. Due to limited information about demand distribution in particular for short-life-cycle products, stochastic modeling approaches may not be suitable. We propose the minimax regret multi-market newsvendor model, where the demands are only known to be bounded within some given interval. In the basic version of the problem, a linear time solution method is developed. For the capacitated case, we establish some structural results to reduce the problem size, and then propose an approximation solution algorithm based on integer programming. Finally, we compare the performance of the proposed minimax regret model against the typical average-case and worst-case models. Our test results demonstrate that the proposed minimax regret model outperformed the average-case and worst-case models in terms of risk-related criteria and mean profit, respectively.     

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

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

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.     

A New Efficient Heuristic for the Minimum Set Covering Problem

We solve approximately the minimum set covering problem by developing a new heuristic, which is essentially based on the flow algorithm originally developed by Ford and Fulkerson. We perform a comparative study of the performances (concerning solution qualities and execution times) of the flow algorithm as well as of the natural greedy heuristic for set covering originally studied by Johnson and Lovász.     

Robust univariate spline models for interpolating interval data

We consider spline interpolation problems where information about the approximated function is given by means of interval estimates for the function values over ranges of x-values instead of specific knots. We propose two robust univariate spline models formulated as convex semi-infinite optimization problems. We present simplified equivalent formulations of both models as finite explicit convex optimization problems for splines of degrees up to 3. This makes it possible to use existing convex optimization algorithms and software.     

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.     

带核箱覆盖问题的在线算法

经典的箱覆盖问题是组合优化中一个著名的问题,并且得到了广泛的研究．本文主要讨论带核元的箱覆盖问题的复杂性和在线条件下的算法．指出了带核的箱覆盖问题是强ＮＰ－ｈａｒｄ的．给出了在不同的在线条件下可行算法渐近比的上界,指出仅在条件三下才存在渐近比好于０的在线算法,并给出了在此条件下一个渐近比为１／２的最好的在线算法。     

The Minimum Covering l pb -Hypersphere Problem

The minimu vering hypersphere problem is defined as to find a hypersphere of minimum radius enclosing a finite set of given points in ⁿ. A hypersphere is a set S(c,r)={x ⁿ : d(x,c) r}, where c is the center of S, r is the radius of S and d(x,c) is the Euclidean distance between x and c, i.e.,d(x,c)=l ₂ (x-c). We consider the extension of this problem when d(x, c) is given by any l _pb -norm, where 1<p and b=(b ₁,...,b _n ) with b _j >0, j=1,...,n, then S(c,r) is called an l _pb -hypersphere, in particular for p=2 and b _j =1, j=1,..., n, we obtain the l ₂-norm. We study some properties and propose some primal and dual algorithms for the extended problem , which are based on the feasible directions method and on the Wolfe duality theory. By computational experiments, we compare the proposed algorithms and show that they can be used to approximate the smallest l _pb -hypersphere enclosing a large set of points in ⁿ.     

On Conditional Covering Problem

The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n ³) algorithm for the same. We also propose an O(n ²) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.     

The Set of Packing and Covering Densities of Convex Disks

For every convex disk $K$ (a convex compact subset of the plane, with non-void interior), the packing density $\delta (K)$ and covering density ${\vartheta (K)}$ form an ordered pair of real numbers, i.e., a point in $\mathbb{R }^2$ . The set $\varOmega $ consisting of points assigned this way to all convex disks is the subject of this article. A few known inequalities on $\delta (K)$ and ${\vartheta (K)}$ jointly outline a relatively small convex polygon $P$ that contains $\varOmega $ , while the exact shape of $\varOmega $ remains a mystery. Here we describe explicitly a leaf-shaped convex region $\Lambda $ contained in $\varOmega $ and occupying a good portion of $P$ . The sets $\varOmega _T$ and $\varOmega _L$ of translational packing and covering densities and lattice packing and covering densities are defined similarly, restricting the allowed arrangements of $K$ to translated copies or lattice arrangements, respectively. Due to affine invariance of the translative and lattice density functions, the sets $\varOmega _T$ and $\varOmega _L$ are compact. Furthermore, the sets $\varOmega , \,\varOmega _T$ and $\varOmega _L$ contain the subsets $\varOmega ^\star , \,\varOmega _T^\star $ and $\varOmega _L^\star $ respectively, corresponding to the centrally symmetric convex disks $K$ , and our leaf $\Lambda $ is contained in each of $\varOmega ^\star , \,\varOmega _T^\star $ and $\varOmega _L^\star $ .     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

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.