How to run self defined problem?

[lzy0702]

Hello, I have a research project which finally resulted in solving a set covering problem. I'm trying to use your code to solve it. I tried to run the program with command ./bazel-bin/setcoveringsolver/main -v -i ~/self-problem.txt --unicost -a greedy -c solution.txt -t 2 And it returns me Segment Fault What should I to fix it? The program can solve the problems in the 7z archive as expected. Thank you!

[fontanf]

Can you provide the input file you use so I can try to reproduce?

[lzy0702]

I'm trying to use ORLibrary format, but I'm not sure if I wrote the input file correctly. In my problem, there are 2000 elements in the universal set (U). I tried set the cost of each element to 1.(so they are) Each subset (S_i) is described with two lines. The the odd numbered lines is the total number of elements in the subset, and even numbered lines contains the ordered number of each element in the U. Please let me know if I wrote the input file correctly. SetCover.zip

[lzy0702]

SetCover-Rand08-pH2.8-20_single_1.500000.txt For this file, if I choose "localsearch_rowweighting" algorithm, it will report a segment fault, but it can return a result if I choose greedy.

[lzy0702]

Also, could I limit the maximum number of subset to be chosen in the solution?

[fontanf]

Indeed, at some point, all the sets in the current solution are mandatory sets. So the algorithm crashes when trying to find one to remove. I fixed the localsearch_rowweighting_2 algorithm. I need to think a bit more to fix the other localsearch_rowweighting algorithm. With the last update, this should work:

./bazel-bin/setcoveringsolver/main -v -i SetCover-Rand08-pH2.8-20_single_1.500000.txt -f orlibrary --unicost -a localsearch_rowweighting_2 -c solution.txt -t 2

[lzy0702]

Thank you!

[fontanf]

Also, could I limit the maximum number of subset to be chosen in the solution?

What do you mean? If the costs are all 1, the algorithm will already try to minimize the number of selected sets in the solution. There exists a variant of the problem where the goal is to cover the maximum number of elements with a fixed number of sets, but this is not what this package solves.

[lzy0702]

Also, could I limit the maximum number of subset to be chosen in the solution?

What do you mean? If the costs are all 1, the algorithm will already try to minimize the number of selected sets in the solution. There exists a variant of the problem where the goal is to cover the maximum number of elements with a fixed number of sets, but this is not what this package solves.

emmm, I want to see how the cover increases with increasing the number of subset. My research project is a wet lab experiment. Each subset indicates the samples which can be successfully treated by a specific model of equipments, so we want to see how many samples can be successfully treated when we introduce more and more models of equipments. We may stop increasing the models if the number of successful treatment satisfy us at some point.

[fontanf]

If I understand well, you want to give as input a minimum number of elements to cover, or set a value for each element and give as input the minimum value of covered elements, and then find the minimum number of sets to reach this minimum value (meaning that not all elements will be covered).

If it's this, then it's not the problem that this packages solves. It might be possible to adapt the algorithms for this variant, but I won't have time to do it and maintain it. The easiest solution is certainly to write the problem as a MILP and give it to a MILP solver.

[lzy0702]

If I understand well, you want to give as input a minimum number of elements to cover, or set a value for each element and give as input the minimum value of covered elements, and then find the minimum number of sets to reach this minimum value (meaning that not all elements will be covered).

If it's this, then it's not the problem that this packages solves. It might be possible to adapt the algorithms for this variant, but I won't have time to do it and maintain it. The easiest solution is certainly to write the problem as a MILP and give it to a MILP solver.

Actually I wrote a greedy solver and a MILP solver, but the reviewers want me to use some more advanced solver and compare the difference...

[fontanf]

I'm not aware of articles or algorithms for this variant. If there are none, then I guess you will need to design and implement one yourself. However, if your instances have as few sets as the ones you posted, I would be surprised that the MILP doesn't prove the optimality quickly

[lzy0702]

I'm not aware of articles or algorithms for this variant. If there are none, then I guess you will need to design and implement one yourself. However, if your instances have as few sets as the ones you posted, I would be surprised that the MILP doesn't prove the optimality quickly

I don't know if you have looked at the input files in the zip archive I uploaded in the 3rd post of this thread. MILP is quite slow when sovling the tandem problem (about 2000 columns by 218k rows). The 20-column input file is just to test if the format of input file is correct.

[fontanf]

The tandem problem you put in the zip file has also 20 sets. With 2000 sets, it's indeed not surprising that the MILP solver doesn't terminate. A row weighting local search seems relevant since it's now a standard heuristic for the USCP. But you'll need to work a bit to adapt it and implement it

[hellman]

Hi, I've just cloned the repo and compiled it. I have a crash for localsearch_rowweighting even on simple instances:

$ ./bazel-bin/setcoveringsolver/main -i test.txt -a localsearch_rowweighting
...
terminate called after throwing an instance of 'std::out_of_range'
  what():  Invalid set index: "-1". Set indices should belong to [0, 70335].
fish: “./bazel-bin/setcoveringsolver/m…” terminated by signal SIGABRT (Abort)

I think it's this line:

solution.remove(s_best);

test.txt

[fontanf]

If it's the same issue, it's actually because the instance is too simple. localsearch_rowweighting_2 should work. Let me know if it's not the case. I haven't found a clean fix for localsearch_rowweighting yet.

[hellman]

Ok, sure, thanks! I have a more complex (or just large?) system that also fails. err.gecco.gz

Can't it be fixed in the same way? as in https://github.com/fontanf/setcoveringsolver/blob/master/setcoveringsolver/algorithms/localsearch_rowweighting.cpp#L356 :

        // It may happen that all sets in the solution are mandatory.
        if (s_best == -1)
            return output.algorithm_end(parameters.info);
        // Apply best move
        solution.remove(s_best);

to https://github.com/fontanf/setcoveringsolver/blob/master/setcoveringsolver/algorithms/localsearch_rowweighting.cpp#L144 :

            // Apply best move
            solution.remove(s_best);

[fontanf]

If fixed this way, it could stop too early. The algorithm localsearch_rowweighting_2 works on the whole solution, but localsearch_rowweighting separates the problem by connected components. What happens is that all selected sets of a connected component are marked as mandatory since there exists for each of them an element that only they cover. So no set can be removed from this component. But there might be another connected component for which not all selected sets are mandatory

[fontanf]

Should be fixed in 59de7c1893f7b7360474664496dbb90d3ba356d9 I tested the 4 provided instances with success.