Многопоточная ветка и связанный поиск в 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`.") };
    }

Компилятор сообщает, что просто перемещает Arc<Node> в поток (иповторная отправка в основной поток) требует, чтобы Node и все его поля были Sync.

Код можно найти здесь .