Brian's Digest: Set Covering Problem

1996

SCI.OP-RESEARCH Digest Mon, 14 Dec Volume 5: Issue 50

Date: Fri, 11 Dec 1998 21:07:52 +0000
From: Christoph Frerichs <christoph.frerichs@gmx.de>
Subject: Algorithms for set cover?
What algorithms for the set cover problem are known?

Best regards,

Christoph Frerichs

Christoph Frerichs, Nordstr. 50, 53111 Bonn, Germany phone: ++ 228 96 3 79 39 eMail: christoph.frerichs@gmx.de Date: 12 Dec 1998 09:09:37 GMT
From: jeb1@ic.ac.uk (Dr J.E. Beasley)
Subject: Algorithms for set cover?
See http://mscmga.ms.ic.ac.uk/jeb/jeb.html

SCI.OP-RESEARCH Digest Mon, 30 Jun 97 Volume 4: Issue 26

Date: 27 Jun 1997 13:34:19 GMT
From: palpacel@cli.di.unipi.it (Luigino Palpacelli)
Subject: LOOKING for OPTIMAL SET COVERING algorithm
I'm looking for references (Papers AND/OR Software) on optimal set covering algorithms and in particular references suited for boolean function semplification.

THANK YOU for the attention

SCI.OP-RESEARCH Digest Mon, 28 April 97 Volume 4: Issue 17

Date: 14 Apr 1997 14:10:22 +0200
From: Tuomo Takkula <tuomo@cs.chalmers.se>
Subject: Help! Set Covering Problems...

Patrizio Tassone <tassone@italway.it> writes: > i've a list of job and a list of person who can do this jobs. > Each person may do several job. The number of person is less than the > number of job, of course. > > so, i have a matrix like this > job > 1 2 3 4 5 6 7 8 9 10 ... n > > w 1 1 0 0 1 1 0 1 0 0 0 1 > o 2 0 0 1 0 0 1 0 0 0 1 1 > r 3 > k 4 > e 5 > r 6 > s . > . > > where the i-worker may do the j-job if Aij=1 > and the i-worker cannot do then j-job if Aij=0. > > The soft may produce a matrix where, for each job, there's almost one > worker may do it. > > the numbero of workers is not fixed, but it must been as less as > possible. > > Can you help me? do you have something ready or you can tell me where to > find something interesting? Hello Patrizio.

You can write the whole problem down as a integer program (in fact you wrote it almost completely down) as follows:

min c'x s.t. Ax >= 1 x_j \in {0,1}, j=1,..,n A as your matrix above, and vector c=1 You can directly try to solve the problem with a linear optimization algorithm and hope to find an integer solution (happens frequently in small dimensions) or alternatively use branch&bound techniques (slow, since c_j takes only one value) or heuristics. (Branch&Cut does not work too fine for SC problems).

If you want to avoid overcovers (more than one person assigned to one job, than you have to exchange the '>=' operator by '=' and you have a set-partitioning problem. The above paragraph still holds, just you have to expect more fractional solutions in the soptimal solution of your LP-relaxation (no theorem, just experience on random problems) and Branch&Cut works better.

Check the extensive literature, if you want to solve large problems.

Best regards, Tuomo

SCI.OP-RESEARCH Digest Mon, 7 April 97 Volume 4: Issue 14

Date: Tue, 01 Apr 1997 20:37:10 -0800
From: Patrizio Tassone <tassone@italway.it>
Subject: Help! Set Covering Problems...
Excuse me... i'm an italian student... i've a problem with Set Covering Problems...

i've a list of job and a list of person who can do this jobs.

Each person may do several job. The number of person is less than the number of job, of course.

so, i have a matrix like this

job 1 2 3 4 5 6 7 8 9 10 ... w 1 1 0 0 1 1 0 1 0 0 0 o 2 0 0 1 0 0 1 0 0 0 1 r 3 k 4 e 5 r 6 s .. where the i-worker may do the j-job if Aij=1 and the i-worker cannot do then j-job if Aij=0.

The soft may produce a matrix where, for each job, there's almost one worker may do it.

the numbero of workers is not fixed, but it must been as less as possible.

Can you help me? do you have something ready or you can tell me where to find something interesting?

Thank you for your interesting...

Patrizio Tassone
tassone@italway.it

Date: Wed, 02 Apr 1997 09:12:51 -0800
From: arndt lueder <arndt@hamlet.et.uni-magdeburg.de>
Subject: Help! Set Covering Problems..
Dear Patrizio,

you can translat you problem into a graph theoretical problem. You can generate a biparite graph with one node for each jab, one node for each worker and an arc for each posibility of one worker to do one job (the arc is incident to the nodes belonging to the job and the worker).

Your problem is then the marriage problem. You can find it in nearly each graph theoretical book.

Greatings Arndt

-- <<============ooo000XX000ooo============>> Arndt Lueder Otto-von-Guerike-University of Magdeburg Institute for Automation Technologie PF 4120 39016 Magdeburg e-mail:arndt@hamlet.et.uni-magdeburg.de http://www.et.uni-magdeburg.de/~arndt/ <<============ooo000XX000ooo============>> Date: Wed, 02 Apr 1997 09:06:21 -0800
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: Help! Set Covering Problems...
In a marriage each person get 'assigned' to one other person. But here each person may do more than one job. How do you handle that, using this approach?

I would go for a Set Partitioning formulation, with the jobs as rows, and the possible sets of jobs as columns. You may need some artificial jobs to take care of each person being used exactly once.

Roy Jonker, PhD @ MagicLogic Optimization Inc. tel (604) 535 5133 (BC, Canada) - fax (on request) email roy_jonker@magiclogic.com www http://mindlink.net/magiclogic/magic.html - Date: Thu, 03 Apr 1997 09:48:43 -0800
From: arndt lueder <arndt@hamlet.et.uni-magdeburg.de>
Subject: Help! Set Covering Problems...
The solution of the mariagge problem gives an permissible assignment of workers to jobs. For the solution of the problem of Patrizio you need the minimal number of workers so that for each job permissible solution of the corresponding marriage problem exists. It is not nessesary to generate such a solution because the marriage theorem gives sufficient conditions for the existance of such a solution.

You can find some thing about the marriage problem in the Book of Claude Berge named Graphs published at North-Holland Mathematical Library.

There is a good chapter about matchings in it. And there you can find the marriage problem, the theorem of Hall and the theorem of Koenig. They are not named explicitly, but I am sure you will find it.

Arndt Lueder

SCI.OP-RESEARCH Digest Mon, 24 Feb 97 Volume 4: Issue 8

Date: Wed, 19 Feb 1997 16:19:10 +0100
From: Maurizio Bartoli <Maurizio.Bartoli@cselt.stet.it>
Subject: help on set covering problems
Hi to all,

I am looking for references to algorithms about set covering problems.

Any one can help me? Any help would be appreciated.

Maurizio

SCI.OP-RESEARCH Digest Mon, 20 Jan 97 Volume 4: Issue 3

Date: Mon, 13 Jan 1997 06:45:10 -0800
From: Roy Jonker <roy_jonker@magiclogic.com>
Subject: set covering

Tore Gruenert wrote: > > We are interested in articles/papers for solving large-scale > set-covering problems (about 200 rows and > 10000 columns). Good (and > easy-to-implement) heuristics would be appropriate in our case. To my knowledge, best and fastest results have been obtained by Caprara, Fischetti and Toth in 'A Heuristic Algorithm for the Set Covering Problem'. Alberto Caprara is at alberto@promet4.deis.unibo.it

Date: Tue, 07 Jan 1997 18:00:25 +0100
From: Tore Gruenert <tore@or.rwth-aachen.de>
Subject: set covering
Dear readers,

We are interested in articles/papers for solving large-scale set-covering problems (about 200 rows and > 10000 columns). Good (and easy-to-implement) heuristics would be appropriate in our case.

Best regards,

Tore

-------------------- Tore Gruenert Operations Research RWTH Aachen D-52056 Aachen Germany e-mail: tore@or.rwth-aachen.de Date: 10 Jan 1997 19:13:01 +0100
From: Tuomo Takkula <tuomo@math.chalmers.se>
Subject: set covering
The state of the art are Lagrangian relaxation based techniques, see for exampleM

Sebastian Ceria, Paolo Nobili and Antonio Sassano, A Lagrangian-based Heuristic for Large-scale Set Covering Problems, to appear in Mathematical Programming , (1996).

reporting about good solutions to real-world problems with up to one million variables and 5000 rows and

Dag Wedelin, An algorithm for large scale 0-1 integer programming with application to airline crew scheduling. In Burkard (ed.) Mathematics of Industrial Systems, Annals of Operations Research. Baltzer 1995 and other papers about crew-scheduling. There the largest SC-problems appear and most effort to solve the is taken.

Best regards, Tuomo

SCI.OP-RESEARCH Digest Mon, 1 Jan 96 Volume 3: Issue 1

Date: 28 Dec 1995 13:01:53 GMT
From: ts110@pmms.cam.ac.uk (Tomaz Slivnik)
Subject: Set covering problem
What is the best available technology (I'm looking for either commercial or public domain software or references to published algoritms) for solving the set covering problem (given a cover of a finite set by sets of given weights, find the subcover of minimal weight).

I'm looking both for code producing provably optimal solutions as well as any heuristics claiming to produce good solutions.

Thank you very much.

Tomaz Slivnik

Date: 29 Dec 1995 10:37:21 GMT
From: jeb1@ic.ac.uk (Dr J.E. Beasley)
Subject: Set covering problem
Some relevant references can be found on my WWW page http://mscmga.ms.ic.ac.uk/jeb/jeb.html

Date: Sun, 31 Dec 1995 12:36:17 GMT
From: yash@rakefet.weizmann.ac.il (Wool Avishai)
Subject: Set covering problem
you can find a comparison between 9 set-covering approximation algs in a paper by Grossman and myself (available via my home page)

Avishai Wool ( yash@wisdom.weizmann.ac.il )
Dept. of Applied Mathematics and Computer Science
Weizmann Institute of Science, Rehovot 76100, Israel
WWW: http://www.wisdom.weizmann.ac.il/~yash

SCI.OP-RESEARCH Digest Fri, 17 May 96 Volume 3: Issue 21

Date: 15 May 1996 00:55:43 GMT
From: Steven Spitz <spitz@usc.edu>
Subject: Minimum Clustering Problem?!
Assume a collection of n sets A := {A1, A2, ..., An}. A cluster is a subset of 'A' that has a non-null intersection.

The minimum clustering problem:

Find a minimum number of clusters that cover 'A'.

This problem is NP-Complete. It is easy to show a reduction from the vertex-coloring problem to this problem.

My questions are as follows:

How is this problem referred to in the literature?
Are there any optimization techniques / good heuristics to solve this problem?
I'm interseted in a simple/efficient technique to solve this problem, while finding a reasonably "good" solution. How bad will it be to use a completely randomized algorithm? For example, to find the first cluster:
- shuffle the sets in 'A'
- C := {A1}
- for i := 2 to n
- if intersection( union( C, {Ai} ) ) <> null-set
  C := union( C, {Ai} )
- And continue the process for A-C...
4) pointers to papers/software.

Thanks,

SCI.OP-RESEARCH Digest Mon, 29 Jul 96 Volume 3: Issue 31

Date: 23 Jul 1996 12:46:09 GMT
From: stormark@diku.dk (Thomas Stormark)
Subject: Where to find testbed (standard problems) for WVCP (Weighted Vertex Cover problem)
Does anyone know if there is a testbed (package of standard-problems, with known solutions) for the WVCP (Weighted Vertex Cover Problem) and where it is reachable.

-Thomas Stormark (E-Mail:stormark@diku.dk)

Date: 26 Jul 1996 20:12:26 GMT
From: rubin@msu.edu (Paul A. Rubin)
Subject: Where to find testbed (standard problems) for WVCP (Weighted Vertex Cover problem)
I'm not familiar with the WVCP, but if it is a form of set covering problem, you might find suitable test problems at the Imperial College (London) OR Library: http://mscmga.ms.ic.ac.uk/info.html

Paul

Crawl back to front page.