Trait Subproblem

pub trait Subproblem {
    type Score: Ord;

    // Required methods
    fn branch_or_evaluate(&self) -> SubproblemResolution<Self, Self::Score>;
    fn bound(&self) -> Self::Score;
}

A problem (subproblem) to be solved with branch-and-bound

Required Associated Types

type Score: Ord

Required Methods

fn branch_or_evaluate(&self) -> SubproblemResolution<Self, Self::Score>

Evaluates a problem space.

If the space is to be broken further into subproblems, returns a sequence of subproblems (may be empty, which discards the current subspace).

If the space consists of just one feasible solution to be solved directly, returns the score, which is the value of the objective function at the solution.

fn bound(&self) -> Self::Score

Value of the boundary function at the problem space.

The boundary function gives an upper-boundary of the best solution that could potentially be found in this subproblem space. The value of the boundary function must be greater than or equal to every value of the objective score of any subproblem reachable through consecutive .branch_or_evaluate calls.

If at some point in the search process a subproblem’s .bound() value is less than or equal to the current best solution, the subproblem is discarded (because no better solution will be found in its subtree).

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors