赫拉克勒斯：QUBO 求解器和启发式工具包

赫拉克勒斯是一个 Rust 库，用于分析、寻找 QUBO（二次无约束二进制优化）问题的近似解和精确解。它主要是我在攻读博士学位期间的一个侧项目，所以请理解。

这个库是做什么用的？

赫拉克勒斯被设计成一个简单、易于使用的库，用于解决 QUBO 问题。它不一定是一个前沿的工具，而是一个快速原型设计和测试 QUBO 方法的工具包。尽管如此，赫拉克勒斯被设计成快速，并使用 Rust 编写，这是一种高性能的系统编程语言。

进展

赫拉克勒斯目前处于开发初期。以下功能目前已经实现

• QUBO 数据结构
• QUBO 问题生成
• QUBO 启发式
• 初始分支与界限求解器

在提及求解器时，从原始实现到实际应用实现之间有巨大的差异。我正在尝试逐步将求解器转向对实际问题的有用性，而不是过多地将责任推给依赖项。这一点在我的 个人博客 上有非常高级的文档。目前，它可以一般地解决低于 80 个二进制的密集和稀疏问题。但我希望将能力扩展到更大的问题规模，并更快地解决问题。

• 初始分支与界限
• 初始预处理器
• 热启动
• 变量分支规则
• 多线程 B&B 求解器
• 问题重构
• 现代预处理器
• 热启动子问题
• Beck 优化证明

简单：读取和解决 QUBO 示例

这可以用来生成获取和生成（根据搜索启发式）高质量（取决于搜索启发式）的 QUBO 问题解决方案。例如，以下代码演示了如何使用增益标准搜索找到 QUBO 问题的局部最小值。

use hercules::qubo::Qubo;
use hercules::local_search::simple_gain_criteria_search;
use hercules::initial_points::generate_central_starting_points;

// read in a QUBO problem from a file
let p = Qubo::read_qubo("test.qubo");

// generate an initial point of 0.5 for each variable
let x_0 = generate_central_starting_points(&p);

// use the gain criteria search to find a local minimum with an upper bound of 1000 iterations
let x_1 = simple_gain_criteria_search(&p, &x_0, 1000);

高级：混合两种局部搜索启发式

赫拉克勒斯的子组件可以独立且可互换地使用，这使得我们能够即时创建新的启发式方法。例如，以下代码展示了如何根据1-opt和增益搜索创建一个新的局部搜索函数。算法的每一次迭代都被定义为在当前点的邻域中找到能量最低的点，然后进行大规模翻转操作，根据函数的增益翻转位。这使得局部搜索算法（以及其他一些想法）简单、易于理解且易于实现。

use hercules::qubo::Qubo;
use hercules::local_search::*;
use hercules::local_search_utils::*;
use ndarray::Array1;
use rayon::prelude::*;
use hercules::initial_points;
use smolprng::{PRNG, JsfLarge};

// A simple local search heuristic that uses 1-opt and gain-criteria search
pub fn simple_mixed_search(qubo: &Qubo, x_0: &Array1<f64>, max_steps:usize) -> Array1<f64>{
    // create a mutable copy of the initial point
    let mut x = x_0.clone();
    // flip the bits maximize the 1D gains
    let mut x_1 = get_gain_criteria(qubo, &x);
    let mut steps = 0;
    
    // run the local search until we reach a local minimum or we reach the maximum number of steps
    while x_1 != x && steps <= max_steps {
        x = x_1.clone();
        // find the lowest energy point in the neighborhood of x (can be x itself)
        x_1 = one_step_local_search(qubo, &x, &(0..qubo.num_x()).collect());
        // flip the bits to better satisfy the stationary conditions
        x_1 = get_gain_criteria(qubo, &x_1);
        // increment the number of steps
        steps += 1;
    }
    // return the best point found
    x_1
}

// create a random QUBO problem
let mut prng = PRNG {
    generator: JsfLarge::default(),
};
let p = Qubo::make_random_qubo(1000, &mut prng, 0.1);

// generate 8 random starting points
let mut x_s = initial_points::generate_random_starting_points(&p, 8, &mut prng);

// solve each initial point, in parallel
let x_sols: Vec<_> = x_s
    .par_iter()
    .map(|x| simple_mixed_search(&p, &x, 1000))
    .collect();

// find the best solution
let min_obj = x_sols
    .iter()
    .map(|x| p.eval(&x))
    .min_by(|a, b| a.partial_cmp(b).unwrap())
    .unwrap();

这实际上是一个非常有效的简单局部搜索启发式方法，可以作为更复杂启发式方法的起点。在这里，我们可以在一个笔记本电脑上，在约15毫秒内将随机生成的1000x1000稀疏QUBO问题的解优化到最优解的0.5%以内。

Python接口：使用Python中的赫拉克勒斯

可以通过Py03 crate从Python中使用赫拉克勒斯。这目前还在进行中，目前还没有独立的包。可以通过运行maturin develop命令通过maturin构建。然而，以下代码展示了如何从Python使用赫拉克勒斯。

在这里，我们可以使用我们开发的简单混合搜索启发式方法来使用Python接口解决一个随机生成的QUBO问题。这是一个1000x1000的QUBO问题，有1000个非零项，我们从一个随机初始点迭代50次来解决问题。这需要的时间与纯Rust版本相当，并且我们得到了相同的解。

import hercules
import random
import time

# set a random seed
random.seed(time.time())

# read in the qubo problem
problem = hercules.read_qubo('test_large.qubo')
num_x = problem[-1]

# create a random initial point
x_0 = [random.randint(0, 1) for i in range(num_x)]

# start timing
start = time.time()

# solve the QUBO problem via the mixed local search heuristic with, initial point x_0, for 50 iterations
x_soln, obj = hercules.mls(problem, x_0, 50)

# stop timing
end = time.time()

# print the objective value of the solution
print('Solution: ', obj, ' in ', end - start, ' seconds')

Docker

这里有一个Docker镜像在这里。要运行此镜像，请拉取图像并运行以下命令

docker run --platform linux/amd64 dkenefake/hercules:test python pyhercules.py