Multithreaded branch and bound search in Rust

Question

I am trying to solve a mathematical minimization problem using a branch and bound algorithm, in Rust. For simplicity, let's say that we're trying to find the objective value only.

Functional

Solving the problem requires solving an easier version ("the relaxation"), which then may give rise to precisely two subproblems. Solving a relaxation takes a long time and needs to happen on a separate thread.

The difficulty is that a problem's subproblems are known only after the problem is solved. As such, the binary tree in which the problem and its subproblems live, grows during the computation. Moreover, the solving of a relaxation might result in nodes of the tree getting pruned. For each known problem, a sizable table has to be stored. Because of limited memory capacity, I want to search this tree in a depth-first order.

Non-functional

Performance of the tree doesn't matter as much; the vast majority of the time will be spent solving the relaxations. I would like to avoid using manual relative references and similar constructs, and instead use Rust's toolbox of references to solve this problem. As a bonus, I'd like to capture the life-cycle of the problem-nodes in the type system:

1. The problem is known
2. It is being solved
3. The relaxation is solved and
   • If the problem turns out to be feasible:
     • If the objective value of the relaxation below a global maximum, the subproblems are computed
     • If not, the problem is marked suboptimal, further subproblems are irrelevant
   • If not, the problem is marked infeasible, further subproblems are irrelevant
4. Both subproblems are solved and only the objective value of this problem is stored

Example of attempt

I've attempted several approaches, but I keep running into problems. My latest approach is best summarized by the definition of the node in the tree. The problem data is stored in the 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
}

I tried to manage the tree with the main thread, while providing worker threads with an Arc to the problem data. The sender_to_active_thread field on the ActiveCalculation variant is used to terminate a calculation, when newly found information determines that the calculation could only yield a suboptimal result.

The problem with the above attempt is that I don't know how to update the tree once a solution is found. See below the code that fetches the next problem from the tree, hands it off to a thread, and processes the result:

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`.") };
    }

The compiler tells me that just moving an Arc<Node> to the thread (and sending it to the main thread again) requires that Node and all its fields are Sync.

The code can be found here.