multithreading - Rust 中的多线程分支定界搜索

Question

我正在尝试在 Rust 中使用分支定界算法解决数学最小化问题。为简单起见，假设我们只试图找到目标值。

功能性

解决问题需要解决一个更简单的版本（“松弛”），这可能会导致恰好两个子问题。解决放松需要很长时间，并且需要在单独的线程上进行。

困难在于问题的子问题只有在问题解决后才能知道。因此，问题及其子问题所在的二叉树会在计算过程中增长。此外，松弛的解决可能会导致树的节点被修剪。对于每个已知问题，必须存储一个相当大的表。由于内存容量有限，我想以深度优先的顺序搜索这棵树。

非功能性

树的性能并不重要。绝大多数时间将花在解决松弛问题上。我想避免使用手动的相对引用和类似的结构，而是使用 Rust 的引用工具箱来解决这个问题。作为奖励，我想捕获类型系统中问题节点的生命周期：

1. 问题已知
2. 正在解决
3. 松弛问题解决了
   • 如果问题证明是可行的：
     • 如果松弛的目标值低于全局最大值，则计算子问题
     • 如果不是，则问题被标记为次优，进一步的子问题无关紧要
   • 如果不是，则问题被标记为不可行，进一步的子问题是不相关的
4. 两个子问题都解决了，只存储了这个问题的目标值

尝试示例

我尝试了几种方法，但我一直遇到问题。我的最新方法最好通过树中节点的定义来概括。问题数据存储在Tableau.

enum Node<'a, T, TP> {
    /// The problem to solve. Nothing is known.
    Undecided {
        parent: Option<rc::Weak<Self>>,
        depth: u64,
        tableau: Tableau<'a, T, TP>,
    },
    /// Being calculated
    ActiveCalculation {
        parent: Option<rc::Weak<Self>>,
        depth: u64,
        tableau: Arc<Mutex<Tableau<'a, T, TP>>>,
        sender_to_active_thread: Sender<PruneReason>,
    },
    /// The problem is solved, and the children (if any) should be created while this variant is
    /// being instantiated.
    NodeOptimal {
        parent: Option<Weak<Self>>,
        relaxation_value: f64,
        best_lower_bound: Cell<Option<f64>>,
        lower: Rc<Self>,
        upper: Rc<Self>,
    },
    /// This problem and all generated subproblems are solved.
    SubTreeOptimal {
        lower_bound: f64,
    },
    /// Pruned.
    Pruned(PruneReason), // e.g. SubOptimal, Infeasible
}

我尝试用主线程管理树，同时为工作线程提供Arc问题数据。当新发现的信息确定计算只能产生次优结果时，变体上的sender_to_active_thread字段用于终止计算。ActiveCalculation

上述尝试的问题是，一旦找到解决方案，我不知道如何更新树。请参阅下面的代码，该代码从树中获取下一个问题，将其交给线程并处理结果：

let (solution_sender, solution_receiver) = channel();

    // Stop condition
    while !tree.finished() {

        let mut possible_next_problem = tree.next_problem();
        // Wait condition
        while active_threads == max_threads || possible_next_problem.is_some() {
            // Wait for a signal, block until a thread has terminated
            let (solved_problem, result) = solution_receiver.recv().unwrap();
            active_threads -= 1;

            let new_node = match result {
                None => Node::Pruned(PruneReason::Infeasible),
                Some((solution, objective_value)) => {
                    unimplemented!()
                }
            };
            tree.update(solved_problem, new_node);
            possible_next_problem = tree.next_problem();
        }
        // Assumed to be of `Undecided` variant
        let next_problem = possible_next_problem.unwrap();

        let solution_sender_clone = solution_sender.clone();
        let (termination_sender, termination_receiver) = channel();
        *next_problem = next_problem.undecided_to_active_calculation(termination_sender);
        let pointer_to_problem_in_tree = next_problem.clone();
        if let Node::ActiveCalculation { tableau, .. } = *next_problem {
            thread::spawn(move || {
                let result = solve_in_separate_thread(&mut *tableau.lock().expect("Should be of variant `Undecided`"),
                                                      termination_receiver);
                solution_sender_clone.send((pointer_to_problem_in_tree, result)).unwrap();
            });
        } else { panic!("Should be of variant `ActiveCalculation`.") };
    }

编译器告诉我，只需将 an 移动Arc<Node>到线程（并再次将其发送到主线程）就需要它，Node并且它的所有字段都是Sync.

代码可以在这里找到。

标签： multithreadingrustdynamic-programminglifetime