击中集的高效分支定界求解器

实现了《击中集的高效分支定界求解器》研究论文中描述的最小击中集求解器。还包括用于论文评估部分的代码。

注意：尽管求解器本质上是相同的，但与论文中描述的版本相比，增加了一些功能。要重现论文或我早期硕士论文的结果，请参阅 Github 发布版及其相应的 git 标签。

安装

在 Github 发布页面中，您可以下载适用于 Linux、macOS 和 Windows 的二进制文件。如果您已经安装了 Cargo 包管理器，则可以使用它从 crates.io 使用 cargo install findmins 安装 findmins。最后，当然可以使用最新版本的 Rust 自己构建它。要开始，请在仓库中执行 cargo build --release，将在 target/release 目录中创建一个优化后的二进制文件。

用法

要运行求解器，请使用 findminhs solve <hypergraph-file> <settings-file>。下面描述了两个文件的格式。您可以通过传递 -s/--solution <file> 将最终击中集写入格式为 JSON 数组的文件。同样，可以使用 -r/--report <file> 将包含求解过程统计信息的 JSON 格式报告写入文件。有关所有其他详细信息，请参阅包含的帮助信息，使用 -h/--help。

超图格式

求解器接受两种格式的超图：JSON格式和基于文本的自定义格式。后者是默认格式，而前者可以通过传递以下命令启用：-j/--json。

基于文本的格式必须以一个初始行开始，该行包含顶点的数量，然后是超边的数量。然后必须包含每一行的超边。每一行必须首先包含超边的大小，然后是包含在超边中的节点的零索引，顺序任意。例如，四个顶点和两个超边{0, 1, 2}和{2, 3}的图可以编码如下

4 2
3 0 1 2
2 2 3

JSON格式只包含节点数以及超边的数组，每个超边表示为一个数组。上面的超图可以编码为

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

设置格式

设置文件是一个与这个例子相同的JSON文件

{
    "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"
}

有关这些选项的详细描述，请参阅论文。上面的例子代表了我们在论文中使用的默认设置。`greedy_mode`的可能值包括：`Never`、`Once`、`AlwaysBeforeBounds`和`AlwaysBeforeExpensiveReductions`。

此外，还有两个可选设置可以使用。第一个是`initial_hitting_set`，它使用给定的命中集初始化求解器。它必须指定为一个包含零索引节点索引的数组。第二个是`stop_at`，它必须给出一个整数值。它指示求解器在找到给定大小或更小的命中集时停止。这些可以在找到最小命中集不是目标的情况下使用，例如在验证给定的命中集是否为最小命中集时。

评估

论文中评估部分的代码位于evaluation目录。请参阅其readme文件以获取详细信息。