solverforge_solver/

runtime.rs

use std::fmt::{self, Debug};
use std::hash::Hash;
use std::marker::PhantomData;

use solverforge_config::{ConstructionHeuristicConfig, PhaseConfig, SolverConfig};
use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
use solverforge_core::score::{ParseableScore, Score};

use crate::builder::{build_local_search, LocalSearchStrategy, RuntimeModel};
use crate::descriptor::{
    build_descriptor_construction_from_bindings, scalar_work_remaining_with_frontier,
};
use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
use crate::manager::solve_specialized_list_construction;
use crate::phase::construction::{select_construction_capabilities, ConstructionRoute};
use crate::phase::{sequence::PhaseSequence, Phase};
use crate::scope::{ProgressCallback, SolverScope};

#[path = "runtime/defaults.rs"]
mod defaults;

#[cfg(test)]
mod tests;

#[cfg(test)]
mod list_tests;

pub struct ListVariableMetadata<S, DM, IDM> {
    pub cross_distance_meter: DM,
    pub intra_distance_meter: IDM,
    pub route_get_fn: Option<fn(&S, usize) -> Vec<usize>>,
    pub route_set_fn: Option<fn(&mut S, usize, Vec<usize>)>,
    pub route_depot_fn: Option<fn(&S, usize) -> usize>,
    pub route_metric_class_fn: Option<fn(&S, usize) -> usize>,
    pub route_distance_fn: Option<fn(&S, usize, usize, usize) -> i64>,
    pub route_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
    _phantom: PhantomData<fn() -> S>,
}

pub trait ListVariableEntity<S> {
    type CrossDistanceMeter: CrossEntityDistanceMeter<S> + Clone + fmt::Debug;
    type IntraDistanceMeter: CrossEntityDistanceMeter<S> + Clone + fmt::Debug + 'static;

    const HAS_LIST_VARIABLE: bool;
    const LIST_VARIABLE_NAME: &'static str;
    const LIST_ELEMENT_SOURCE: Option<&'static str>;

    fn list_field(entity: &Self) -> &[usize];
    fn list_field_mut(entity: &mut Self) -> &mut Vec<usize>;
    fn list_metadata() -> ListVariableMetadata<S, Self::CrossDistanceMeter, Self::IntraDistanceMeter>;
}

impl<S, DM, IDM> ListVariableMetadata<S, DM, IDM> {
    #[allow(clippy::too_many_arguments)]
    pub fn new(
        cross_distance_meter: DM,
        intra_distance_meter: IDM,
        route_get_fn: Option<fn(&S, usize) -> Vec<usize>>,
        route_set_fn: Option<fn(&mut S, usize, Vec<usize>)>,
        route_depot_fn: Option<fn(&S, usize) -> usize>,
        route_metric_class_fn: Option<fn(&S, usize) -> usize>,
        route_distance_fn: Option<fn(&S, usize, usize, usize) -> i64>,
        route_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
    ) -> Self {
        Self {
            cross_distance_meter,
            intra_distance_meter,
            route_get_fn,
            route_set_fn,
            route_depot_fn,
            route_metric_class_fn,
            route_distance_fn,
            route_feasible_fn,
            _phantom: PhantomData,
        }
    }
}

pub struct Construction<S, V, DM, IDM>
where
    S: PlanningSolution,
    V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
    DM: Clone + Debug + Send + 'static,
    IDM: Clone + Debug + Send + 'static,
{
    config: Option<ConstructionHeuristicConfig>,
    descriptor: SolutionDescriptor,
    model: RuntimeModel<S, V, DM, IDM>,
}

impl<S, V, DM, IDM> Construction<S, V, DM, IDM>
where
    S: PlanningSolution,
    V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
    DM: Clone + Debug + Send + 'static,
    IDM: Clone + Debug + Send + 'static,
{
    fn new(
        config: Option<ConstructionHeuristicConfig>,
        descriptor: SolutionDescriptor,
        model: RuntimeModel<S, V, DM, IDM>,
    ) -> Self {
        Self {
            config,
            descriptor,
            model,
        }
    }

    fn solve_list<D, ProgressCb>(
        &self,
        config: &ConstructionHeuristicConfig,
        solver_scope: &mut SolverScope<'_, S, D, ProgressCb>,
        list_variables: &[crate::builder::ListVariableSlot<S, V, DM, IDM>],
    ) -> bool
    where
        D: solverforge_scoring::Director<S>,
        ProgressCb: ProgressCallback<S>,
    {
        if list_variables.is_empty() {
            panic!("list construction configured against a scalar-only model");
        }

        solve_specialized_list_construction(
            config.construction_heuristic_type,
            config.k,
            solver_scope,
            list_variables,
        )
    }

    pub(super) fn solve_configured<D, ProgressCb>(
        &self,
        config: Option<&ConstructionHeuristicConfig>,
        solver_scope: &mut SolverScope<'_, S, D, ProgressCb>,
        required_only: bool,
    ) -> bool
    where
        S: PlanningSolution + 'static,
        S::Score: Score + Copy,
        DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
        IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
        D: solverforge_scoring::Director<S>,
        ProgressCb: ProgressCallback<S>,
    {
        let capabilities = select_construction_capabilities(config, &self.descriptor, &self.model);

        match capabilities.route {
            ConstructionRoute::SpecializedList => {
                let Some(config) = config else {
                    panic!("specialized list construction requires explicit configuration");
                };
                self.solve_list(config, solver_scope, &capabilities.list_variables)
            }
            ConstructionRoute::Descriptor => {
                let scalar_remaining = scalar_work_remaining_with_frontier(
                    &self.descriptor,
                    solver_scope.construction_frontier(),
                    solver_scope.solution_revision(),
                    capabilities.entity_class.as_deref(),
                    capabilities.variable_name.as_deref(),
                    solver_scope.working_solution(),
                );
                if scalar_remaining {
                    build_descriptor_construction_from_bindings(
                        config,
                        &self.descriptor,
                        capabilities.scalar_bindings.clone(),
                    )
                    .solve(solver_scope);
                    true
                } else {
                    false
                }
            }
            ConstructionRoute::GroupedScalar => {
                let Some((group_index, group)) = capabilities.scalar_group.as_ref() else {
                    unreachable!("grouped scalar route requires a selected scalar group");
                };
                if !scalar_group_work_remaining(group, solver_scope.working_solution()) {
                    return false;
                }
                record_scalar_assignment_remaining(group, solver_scope);
                let mut phase = crate::phase::construction::build_scalar_group_construction(
                    config,
                    *group_index,
                    group.clone(),
                    capabilities.scalar_bindings.clone(),
                    required_only,
                );
                phase.solve(solver_scope);
                record_scalar_assignment_remaining(group, solver_scope);
                true
            }
            ConstructionRoute::GenericMixed => {
                crate::phase::construction::solve_construction(config, &self.model, solver_scope)
            }
        }
    }
}

fn scalar_group_work_remaining<S>(
    group: &crate::builder::ScalarGroupBinding<S>,
    solution: &S,
) -> bool {
    if let Some(assignment) = group.assignment() {
        return assignment.unassigned_count(solution) > 0;
    }
    group.members.iter().any(|member| {
        (0..member.entity_count(solution))
            .any(|entity_index| member.current_value(solution, entity_index).is_none())
    })
}

fn record_scalar_assignment_remaining<S, D, ProgressCb>(
    group: &crate::builder::ScalarGroupBinding<S>,
    solver_scope: &mut SolverScope<'_, S, D, ProgressCb>,
) where
    S: PlanningSolution,
    D: solverforge_scoring::Director<S>,
    ProgressCb: ProgressCallback<S>,
{
    if let Some(assignment) = group.assignment() {
        let remaining = assignment.remaining_required_count(solver_scope.working_solution());
        solver_scope
            .stats_mut()
            .record_scalar_assignment_required_remaining(group.group_name, remaining);
    }
}

impl<S, V, DM, IDM> Debug for Construction<S, V, DM, IDM>
where
    S: PlanningSolution,
    V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
    DM: Clone + Debug + Send + 'static,
    IDM: Clone + Debug + Send + 'static,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Construction")
            .field("config", &self.config)
            .field("variable_count", &self.model.variables().len())
            .finish()
    }
}

impl<S, V, DM, IDM, D, ProgressCb> Phase<S, D, ProgressCb> for Construction<S, V, DM, IDM>
where
    S: PlanningSolution + 'static,
    S::Score: Score + Copy,
    V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
    DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
    IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
    D: solverforge_scoring::Director<S>,
    ProgressCb: ProgressCallback<S>,
{
    fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
        let ran_child_phase = match self.config.as_ref() {
            None => defaults::solve_default_construction(self, solver_scope),
            Some(config) => self.solve_configured(Some(config), solver_scope, false),
        };
        if !ran_child_phase {
            finalize_noop_construction(solver_scope);
        }
    }

    fn phase_type_name(&self) -> &'static str {
        "Construction"
    }
}

fn finalize_noop_construction<S, D, ProgressCb>(
    solver_scope: &mut SolverScope<'_, S, D, ProgressCb>,
) where
    S: PlanningSolution,
    D: solverforge_scoring::Director<S>,
    ProgressCb: ProgressCallback<S>,
{
    let had_best = solver_scope.best_score().is_some();
    solver_scope.update_best_solution();
    if had_best {
        solver_scope.promote_current_solution_on_score_tie();
    }
}

pub enum RuntimePhase<C, LS> {
    Construction(C),
    LocalSearch(LS),
}

impl<C, LS> Debug for RuntimePhase<C, LS>
where
    C: Debug,
    LS: Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Construction(phase) => write!(f, "RuntimePhase::Construction({phase:?})"),
            Self::LocalSearch(phase) => write!(f, "RuntimePhase::LocalSearch({phase:?})"),
        }
    }
}

impl<S, D, ProgressCb, C, LS> Phase<S, D, ProgressCb> for RuntimePhase<C, LS>
where
    S: PlanningSolution,
    D: solverforge_scoring::Director<S>,
    ProgressCb: ProgressCallback<S>,
    C: Phase<S, D, ProgressCb> + Debug,
    LS: Phase<S, D, ProgressCb> + Debug,
{
    fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
        match self {
            Self::Construction(phase) => phase.solve(solver_scope),
            Self::LocalSearch(phase) => phase.solve(solver_scope),
        }
    }

    fn phase_type_name(&self) -> &'static str {
        "RuntimePhase"
    }
}

pub fn build_phases<S, V, DM, IDM>(
    config: &SolverConfig,
    descriptor: &SolutionDescriptor,
    model: &RuntimeModel<S, V, DM, IDM>,
) -> PhaseSequence<RuntimePhase<Construction<S, V, DM, IDM>, LocalSearchStrategy<S, V, DM, IDM>>>
where
    S: PlanningSolution + 'static,
    S::Score: Score + ParseableScore,
    V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
    DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
    IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
{
    let mut phases = Vec::new();

    if config.phases.is_empty() {
        phases.push(RuntimePhase::Construction(Construction::new(
            None,
            descriptor.clone(),
            model.clone(),
        )));
        for phase in
            crate::builder::search::defaults::default_local_search_phases(model, config.random_seed)
        {
            phases.push(RuntimePhase::LocalSearch(phase));
        }
        return PhaseSequence::new(phases);
    }

    for phase in &config.phases {
        match phase {
            PhaseConfig::ConstructionHeuristic(ch) => {
                phases.push(RuntimePhase::Construction(Construction::new(
                    Some(ch.clone()),
                    descriptor.clone(),
                    model.clone(),
                )));
            }
            PhaseConfig::LocalSearch(ls) => {
                phases.push(RuntimePhase::LocalSearch(build_local_search(
                    Some(ls),
                    model,
                    config.random_seed,
                )));
            }
            PhaseConfig::Custom(custom) => {
                panic!(
                    "custom phase `{}` requires a typed solution search function",
                    custom.name
                );
            }
            PhaseConfig::PartitionedSearch(partitioned) => {
                let name = partitioned
                    .partitioner
                    .as_deref()
                    .unwrap_or("<missing partitioner>");
                panic!(
                    "partitioned_search partitioner `{name}` requires typed partitioner registration"
                );
            }
        }
    }

    PhaseSequence::new(phases)
}

#[cfg(test)]
mod construction_routing_tests {
    use solverforge_config::ConstructionHeuristicType;

    fn should_use_descriptor_path(
        heuristic: ConstructionHeuristicType,
        has_scalar_variables: bool,
        has_list_variables: bool,
    ) -> bool {
        if !has_scalar_variables {
            return false;
        }

        match heuristic {
            ConstructionHeuristicType::ListRoundRobin
            | ConstructionHeuristicType::ListCheapestInsertion
            | ConstructionHeuristicType::ListRegretInsertion
            | ConstructionHeuristicType::ListClarkeWright
            | ConstructionHeuristicType::ListKOpt => false,
            ConstructionHeuristicType::FirstFit | ConstructionHeuristicType::CheapestInsertion => {
                !has_list_variables
            }
            ConstructionHeuristicType::FirstFitDecreasing
            | ConstructionHeuristicType::WeakestFit
            | ConstructionHeuristicType::WeakestFitDecreasing
            | ConstructionHeuristicType::StrongestFit
            | ConstructionHeuristicType::StrongestFitDecreasing
            | ConstructionHeuristicType::AllocateEntityFromQueue
            | ConstructionHeuristicType::AllocateToValueFromQueue => true,
        }
    }

    #[test]
    fn pure_scalar_first_fit_uses_descriptor_path() {
        assert!(should_use_descriptor_path(
            ConstructionHeuristicType::FirstFit,
            true,
            false,
        ));
    }

    #[test]
    fn pure_scalar_cheapest_insertion_uses_descriptor_path() {
        assert!(should_use_descriptor_path(
            ConstructionHeuristicType::CheapestInsertion,
            true,
            false,
        ));
    }

    #[test]
    fn mixed_first_fit_keeps_generic_construction_path() {
        assert!(!should_use_descriptor_path(
            ConstructionHeuristicType::FirstFit,
            true,
            true,
        ));
    }

    #[test]
    fn mixed_cheapest_insertion_keeps_generic_construction_path() {
        assert!(!should_use_descriptor_path(
            ConstructionHeuristicType::CheapestInsertion,
            true,
            true,
        ));
    }

    #[test]
    fn scalar_only_heuristics_still_route_to_descriptor_path() {
        assert!(should_use_descriptor_path(
            ConstructionHeuristicType::StrongestFit,
            true,
            true,
        ));
    }
}