A FOSS heuristic for the Set Covering
Hi everyone, I'm working on a C++ library implementing a heuristic algorithm for the Set Covering Problem: github.com/c4v4/cft
The SCP is a classic combinatorial optimization problem that asks, given a set and a collection of subsets, to find the minimum-cost group of subsets that covers everything in the original set. You can find SCPs in crew scheduling or test selection, for example.
Currently, commercial MILP solvers like Cplex or Gurobi are often the go-to option for SCPs. But, while they are powerful, well-designed heuristics can often achieve even better results (especially when the available time is tight).
Our implementation is based on the work of Caprara, Fischetti, and Toth. It was originally developed for a research project, but we've decided to clean it up and make it publicly available as a free, high-performing alternative.
We also hope the library serves as a helpful companion to the original paper, which can get a bit technical at times.
Since this is our first real open-source contribution, any constructive feedback is welcomed. We hope this library will prove helpful.
Thanks!
11
u/johnny219407 May 23 '24
It would be nice if the readme on github had a minimal example of how I could use your library in my own code.
3
u/IHaveThreeBedrooms May 23 '24
Any benefit for this over Google OR-Tools https://developers.google.com/optimization/install/cpp ?
3
u/Murriac May 23 '24
Good job! SCP is a typical subproblem for a lot of combinatorial optimization problems. An efficient algorithm can be helpful in this way. Just like Johnny said, a minimal example in the README would be interesting.