An Efficient Branch-and-Bound Solver for Hitting Set

Implementation of the Minimum Hitting Set solver described in the An Efficient Branch-and-Bound Solver for Hitting Set research paper. Also included is the code used for the evaluation section of the paper.

Note: Although the solver is fundamentally the same, a few features have been added compared to the version described in the paper. For reproducing the results from the paper or my earlier master thesis please refer to the Github releases and their respective git tags.

Installing

On the Github release pages you can download binaries for Linux, macOS, and Windows. If you happen to have the Cargo package manager installed, you can use it to install findmins from crates.io using cargo install findmins. Lastly, you can of course build it yourself, using a recent version of Rust. To get started, cargo build --release in a checkout of this repository will create an optimized binary in the target/release directory.

Usage

To run the solver use findminhs solve <hypergraph-file> <settings-file>. The formats for both files are described below. You can pass -s/--solution <file> to write the final hitting set to a file formatted as a JSON array. Similarly, -r/--report <file> can be used to write a JSON formatted report containing statistics about the solving process. For all further details, refer to the included help messages using -h/--help.

Hypergraph format

The solver accepts hypergraphs in two formats: in JSON and in a custom, text-based format. The latter is the default while the former can be enabled by passing -j/--json.

The text-based format must start with an initial line containing the number of vertices followed by the number of hyperedges. It must then contain one line per hyperedge. Each line must first contain the size of the hyperedge followed by the zero-based indices of the nodes contained in the hyperedge, in arbitrary order. As an example, the hypergraph of four vertices and the two hyperedges {0, 1, 2} and {2, 3} could be encoded as such:

4 2
3 0 1 2
2 2 3

The JSON format only contains the number of nodes as well as an array of hyperedges, each represented as an array. The hypergraph from above could be encoded as

{
  "num_nodes": 4,
  "edges": [
    [0, 1, 2],
    [2, 3]
  ]
}

Settings format

The settings file is a JSON file in the same format as this example:

{
    "enable_local_search": false,
    "enable_max_degree_bound": true,
    "enable_sum_degree_bound": false,
    "enable_efficiency_bound": true,
    "enable_packing_bound": true,
    "enable_sum_over_packing_bound": true,
    "packing_from_scratch_limit": 3,
    "greedy_mode": "Once"
}

Refer to the paper for a detailed description of these options. The above example represents the default settings we used in the paper. The possible values for greedy_mode are: Never, Once, AlwaysBeforeBounds, and AlwaysBeforeExpensiveReductions.

Additionally, there are two optional settings that can be used. The first, initial_hitting_set, initializes the solver with a given hitting set. It must be specified as an array containing zero-based node indices. The second is stop_at, which must be given an integer value. It instructs the solver to stop once a hitting set of the given size or smaller is found. These can be used to speed up the solver in situations where finding a minimum hitting set is not the objective, for example when verifying that a given hitting set is minimum.

Evaluation

The code for the evaluation section of the paper is in the evaluation directory. Refer to its readme for details.