Is it possible to solve general weighted set covering problem?

[martin-ray]

Hi.

I'd like to solve the general weighted set covering problem(not unicost SCP) in which the cost of each sets varies. Is it possible to solve such kind of problem using this soft?

[fontanf]

Yes, it is possible. Only the row weighting local search algorithms are restricted to the unicost variant

[martin-ray]

That's great.

Then, can you tell me the format of the input file ? Is it like for each row weight , element, element, element,,,,

So in the the following example,

number of sets: 3 number of elements: 5 set1 : { 1, 3, 5 } , cost=4 set2: { 2, 4 } cost=5 set3: { 1, 2, 3, 4, 5} cost=10

would be like 5 3 4 1 3 5 5 2 4 10 1 2 3 4 5

in the input text file? Is that correct?

[fontanf]

There are multiple supported formats. You can see how they are parsed here https://github.com/fontanf/setcoveringsolver/blob/master/setcoveringsolver/instance.cpp

For example, the orlibrary format which is also described here http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html

number of rows (m), number of columns (n) the cost of each column c(j),j=1,...,n for each row i (i=1,...,m): the number of columns which cover row i followed by a list of the columns which cover row i

which for your example would be:

5 3
4 5 10
2  1 3
2  2 3
2  1 3
2  2 3
2  1 3

[martin-ray]

It worked as I expected. Thank you very much.

By the way It seems we cannot set a double or float value for the weights, right? or is it possible? In my project, I wanna set double values for the weights... and if it's not possible what should I do? Should I multiple 100 or 1000 to convert double to int value? What's your opinion ?

And this is gonna be the last question. I'd like to solve a weighed set covering problem with 700 elements and 1200 sets. I wanna get a solution as close as possible to the optimal solution. Then which algorithm should I use ?

Thank you very much for answering. It helped me a lot.

[fontanf]

By the way It seems we cannot set a double or float value for the weights, right? or is it possible? In my project, I wanna set double values for the weights... and if it's not possible what should I do? Should I multiple 100 or 1000 to convert double to int value? What's your opinion ?

Allowing double as input might cause numerical issues for some algorithms. I often prefer to avoid them when it's not necessary. If your cost represents money for example, you certainly don't need an accuracy greater than 10e-3. So, I would recommend to multiply your values by a reasonable number which makes sense in your case.

And this is gonna be the last question. I'd like to solve a weighed set covering problem with 700 elements and 1200 sets. I wanna get a solution as close as possible to the optimal solution. Then which algorithm should I use ?

700 elements and 1200 sets is not a large set covering problem. It seems likely that a MILP solver could find the optimal solution and prove its optimality in a reasonable time. In this package, there is the milp_gurobi algorithm, but it requires the commercial solver Gurobi. If you don't have access to it, there is a free MILP solver called Cbc, but I haven't implemented it in this package. It doesn't take long to implement, I can do it next week if you're interested. In the meantime, you can either use the largeneighborhoodsearch_2 algorithm or try to write a MILP model for Cbc yourself.

[martin-ray]

Thanks for the reply

Allowing double as input might cause numerical issues for some algorithms. I often prefer to avoid them when it's not necessary. If your cost represents money for example, you certainly don't need an accuracy greater than 10e-3. So, I would recommend to multiply your values by a reasonable number which makes sense in your case.

Okay. Then I will convert the weights to int value.

In this package, there is the milp_gurobi algorithm, but it requires the commercial solver Gurobi. If you don't have access to it, there is a free MILP solver called Cbc, but I haven't implemented it in this package. It doesn't take long to implement, I can do it next week if you're interested. In the meantime, you can either use the largeneighborhoodsearch_2 algorithm or try to write a MILP model for Cbc yourself.

I don't have access to gurobi sovler. And I have no skill to implement Cbc to your code so I will really appreciate if you do that.

[fontanf]

I added the milp_cbc algorithm in 31859d81e3e396bbe09d9139e64fc9e39ea3e103

To use it, you first need to install the Cbc solver. On Linux, the easiest way is to use coinbrew as explained here https://github.com/coin-or/Cbc#using-coinbrew

Then you need to update in the WORKSPACE file the path to the coinbrew repository to match your installation:

    name = "coinor",
    path = "/home/florian/Programmes/coinbrew/",

You also need to update the LD_LIBRARY_PATH environment variable with something like this:

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/florian/Programmes/coinbrew/dist/lib/

Finally, you need to compile with

bazel build --define coinor=true -- //...

Then it should work. For example:

$ ./bazel-bin/setcoveringsolver/main -v 1 -i data/wedelin1995/a320.dat -f wedelin1995 -a milp_cbc
=====================================
         Set Covering Solver         
=====================================

Instance
--------
Number of elements:                           199
Number of sets:                               6931
Number of arcs:                               31801
Average number of sets covering an element:   159.804
Average number of elements covered by a set:  4.58823
Number of connected components:               5
Average cost:                                 81944.5

Algorithm
---------
MILP (CBC)

       T (s)          UB          LB         GAP     GAP (%)                 Comment
       -----          --          --         ---     -------                 -------
       0.000   567957650           0   567957650         inf                        
       0.034   567957650    12620100   555337550     4400.42                        
       0.448    12620100    12620100           0           0                        

Final statistics
----------------
Value:                         12620100
Bound:                         12620100
Gap:                           0
Gap (%):                       0
Time (s):                      0.450126

[martin-ray]

Thank you very much!