solverforge_solver/
basic.rs

1//! Basic variable solver for simple assignment problems.
2//!
3//! This module provides `run_solver` for problems using `#[basic_variable_config]`,
4//! where each entity has a single planning variable that can be assigned from a
5//! fixed value range.
6//!
7//! Logging levels:
8//! - **INFO**: Solver start/end, phase summaries, problem scale
9//! - **DEBUG**: Individual steps with timing and scores
10//! - **TRACE**: Move evaluation details
11
12use std::fmt;
13use std::sync::atomic::AtomicBool;
14use std::time::Duration;
15
16use solverforge_config::SolverConfig;
17use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
18use solverforge_core::score::{ParseableScore, Score};
19use solverforge_scoring::{ConstraintSet, ScoreDirector, TypedScoreDirector};
20use tokio::sync::mpsc;
21use tracing::info;
22
23use crate::heuristic::selector::decorator::UnionMoveSelector;
24use crate::heuristic::selector::{
25    EitherChangeMoveSelector, EitherSwapMoveSelector, FromSolutionEntitySelector,
26    StaticTypedValueSelector,
27};
28use crate::phase::construction::{BestFitForager, ConstructionHeuristicPhase, QueuedEntityPlacer};
29use crate::phase::localsearch::{
30    AcceptedCountForager, LocalSearchPhase, SimulatedAnnealingAcceptor,
31};
32use crate::scope::BestSolutionCallback;
33use crate::scope::SolverScope;
34use crate::solver::Solver;
35use crate::termination::{
36    BestScoreTermination, OrTermination, StepCountTermination, Termination, TimeTermination,
37    UnimprovedStepCountTermination, UnimprovedTimeTermination,
38};
39
40/// Default time limit in seconds.
41const DEFAULT_TIME_LIMIT_SECS: u64 = 30;
42
43/// Monomorphized termination enum for basic solver configurations.
44///
45/// Avoids repeated branching across `solve_with_termination` overloads by
46/// capturing the selected termination variant upfront.
47pub(crate) enum AnyBasicTermination<S: PlanningSolution, D: ScoreDirector<S>> {
48    Default(OrTermination<(TimeTermination,), S, D>),
49    WithBestScore(OrTermination<(TimeTermination, BestScoreTermination<S::Score>), S, D>),
50    WithStepCount(OrTermination<(TimeTermination, StepCountTermination), S, D>),
51    WithUnimprovedStep(OrTermination<(TimeTermination, UnimprovedStepCountTermination<S>), S, D>),
52    WithUnimprovedTime(OrTermination<(TimeTermination, UnimprovedTimeTermination<S>), S, D>),
53}
54
55impl<S: PlanningSolution, D: ScoreDirector<S>> fmt::Debug for AnyBasicTermination<S, D> {
56    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
57        match self {
58            Self::Default(_) => write!(f, "AnyBasicTermination::Default"),
59            Self::WithBestScore(_) => write!(f, "AnyBasicTermination::WithBestScore"),
60            Self::WithStepCount(_) => write!(f, "AnyBasicTermination::WithStepCount"),
61            Self::WithUnimprovedStep(_) => write!(f, "AnyBasicTermination::WithUnimprovedStep"),
62            Self::WithUnimprovedTime(_) => write!(f, "AnyBasicTermination::WithUnimprovedTime"),
63        }
64    }
65}
66
67impl<S: PlanningSolution, D: ScoreDirector<S>, BestCb: BestSolutionCallback<S>>
68    Termination<S, D, BestCb> for AnyBasicTermination<S, D>
69where
70    S::Score: Score,
71{
72    fn is_terminated(&self, solver_scope: &SolverScope<S, D, BestCb>) -> bool {
73        match self {
74            Self::Default(t) => t.is_terminated(solver_scope),
75            Self::WithBestScore(t) => t.is_terminated(solver_scope),
76            Self::WithStepCount(t) => t.is_terminated(solver_scope),
77            Self::WithUnimprovedStep(t) => t.is_terminated(solver_scope),
78            Self::WithUnimprovedTime(t) => t.is_terminated(solver_scope),
79        }
80    }
81
82    fn install_inphase_limits(&self, solver_scope: &mut SolverScope<S, D, BestCb>) {
83        match self {
84            Self::Default(t) => t.install_inphase_limits(solver_scope),
85            Self::WithBestScore(t) => t.install_inphase_limits(solver_scope),
86            Self::WithStepCount(t) => t.install_inphase_limits(solver_scope),
87            Self::WithUnimprovedStep(t) => t.install_inphase_limits(solver_scope),
88            Self::WithUnimprovedTime(t) => t.install_inphase_limits(solver_scope),
89        }
90    }
91}
92
93/// Solves a basic variable problem using construction heuristic + late acceptance local search.
94///
95/// This function is called by macro-generated `solve()` methods for solutions
96/// using `#[basic_variable_config]`.
97///
98/// # Type Parameters
99///
100/// * `S` - The solution type (must implement `PlanningSolution`)
101/// * `C` - The constraint set type
102///
103/// # Arguments
104///
105/// * `solution` - The initial solution to solve
106/// * `finalize_fn` - Function to prepare derived fields before solving
107/// * `constraints_fn` - Function that creates the constraint set
108/// * `get_variable` - Gets the planning variable value for an entity
109/// * `set_variable` - Sets the planning variable value for an entity
110/// * `value_count` - Returns the number of valid values
111/// * `entity_count_fn` - Returns the number of entities
112/// * `descriptor` - Solution descriptor for solver infrastructure
113/// * `entity_count_by_descriptor` - Returns entity count for a given descriptor index
114/// * `terminate` - Optional external termination flag
115/// * `sender` - Channel for streaming best solutions as they are found
116/// * `_variable_field` - Variable field name (unused, for future extensions)
117/// * `_descriptor_index` - Descriptor index (unused, for future extensions)
118#[allow(clippy::too_many_arguments)]
119pub fn run_solver<S, C>(
120    mut solution: S,
121    finalize_fn: fn(&mut S),
122    constraints_fn: fn() -> C,
123    get_variable: fn(&S, usize) -> Option<usize>,
124    set_variable: fn(&mut S, usize, Option<usize>),
125    value_count: fn(&S) -> usize,
126    entity_count_fn: fn(&S) -> usize,
127    descriptor: fn() -> SolutionDescriptor,
128    entity_count_by_descriptor: fn(&S, usize) -> usize,
129    terminate: Option<&AtomicBool>,
130    sender: mpsc::UnboundedSender<(S, S::Score)>,
131    _variable_field: &'static str,
132    _descriptor_index: usize,
133) -> S
134where
135    S: PlanningSolution,
136    S::Score: Score + ParseableScore,
137    C: ConstraintSet<S, S::Score>,
138{
139    finalize_fn(&mut solution);
140
141    let config = SolverConfig::load("solver.toml").unwrap_or_default();
142    let n_entities = entity_count_fn(&solution);
143    let n_values = value_count(&solution);
144
145    info!(
146        event = "solve_start",
147        entity_count = n_entities,
148        value_count = n_values,
149    );
150
151    // Create score director with real entity counter for selector iteration
152    let constraints = constraints_fn();
153    let director = TypedScoreDirector::with_descriptor(
154        solution,
155        constraints,
156        descriptor(),
157        entity_count_by_descriptor,
158    );
159
160    // Handle empty case - nothing to solve, return immediately
161    if n_entities == 0 || n_values == 0 {
162        let mut solver_scope = SolverScope::new(director);
163        solver_scope.start_solving();
164        let score = solver_scope.calculate_score();
165        info!(event = "solve_end", score = %score);
166        let solution = solver_scope.take_best_or_working_solution();
167        let _ = sender.send((solution.clone(), score));
168        return solution;
169    }
170
171    // Build construction phase with BestFitForager
172    let values: Vec<usize> = (0..n_values).collect();
173    let entity_selector = FromSolutionEntitySelector::new(0);
174    let value_selector = StaticTypedValueSelector::new(values);
175    let placer = QueuedEntityPlacer::new(
176        entity_selector,
177        value_selector,
178        get_variable,
179        set_variable,
180        0,
181        "variable",
182    );
183    let construction = ConstructionHeuristicPhase::new(placer, BestFitForager::new());
184
185    // Build local search phase with Late Acceptance
186    // Unified move selector: ChangeMove + SwapMove via EitherMove
187    let values: Vec<usize> = (0..n_values).collect();
188    let change_selector =
189        EitherChangeMoveSelector::simple(get_variable, set_variable, 0, "variable", values);
190    let swap_selector = EitherSwapMoveSelector::simple(get_variable, set_variable, 0, "variable");
191    let move_selector = UnionMoveSelector::new(change_selector, swap_selector);
192    let acceptor = SimulatedAnnealingAcceptor::default();
193    let forager = AcceptedCountForager::new(1);
194    let local_search = LocalSearchPhase::new(move_selector, acceptor, forager, None);
195
196    // Build termination from config
197    let term_config = config.termination.as_ref();
198    let time_limit = term_config
199        .and_then(|c| c.time_limit())
200        .unwrap_or(Duration::from_secs(DEFAULT_TIME_LIMIT_SECS));
201    let time = TimeTermination::new(time_limit);
202
203    let best_score_target: Option<S::Score> = term_config
204        .and_then(|c| c.best_score_limit.as_ref())
205        .and_then(|s| S::Score::parse(s).ok());
206
207    let termination: AnyBasicTermination<S, TypedScoreDirector<S, C>> =
208        if let Some(target) = best_score_target {
209            AnyBasicTermination::WithBestScore(OrTermination::new((
210                time,
211                BestScoreTermination::new(target),
212            )))
213        } else if let Some(step_limit) = term_config.and_then(|c| c.step_count_limit) {
214            AnyBasicTermination::WithStepCount(OrTermination::new((
215                time,
216                StepCountTermination::new(step_limit),
217            )))
218        } else if let Some(unimproved_step_limit) =
219            term_config.and_then(|c| c.unimproved_step_count_limit)
220        {
221            AnyBasicTermination::WithUnimprovedStep(OrTermination::new((
222                time,
223                UnimprovedStepCountTermination::<S>::new(unimproved_step_limit),
224            )))
225        } else if let Some(unimproved_time) = term_config.and_then(|c| c.unimproved_time_limit()) {
226            AnyBasicTermination::WithUnimprovedTime(OrTermination::new((
227                time,
228                UnimprovedTimeTermination::<S>::new(unimproved_time),
229            )))
230        } else {
231            AnyBasicTermination::Default(OrTermination::new((time,)))
232        };
233
234    let callback_sender = sender.clone();
235    let callback = move |solution: &S| {
236        let score = solution.score().unwrap_or_default();
237        let _ = callback_sender.send((solution.clone(), score));
238    };
239
240    let solver = Solver::new(((), construction, local_search))
241        .with_termination(termination)
242        .with_time_limit(time_limit)
243        .with_best_solution_callback(callback);
244
245    let result = if let Some(flag) = terminate {
246        solver.with_terminate(flag).solve(director)
247    } else {
248        solver.solve(director)
249    };
250
251    // Send the final solution so the receiver always gets the last state
252    let final_score = result.solution.score().unwrap_or_default();
253    let _ = sender.send((result.solution.clone(), final_score));
254
255    info!(
256        event = "solve_end",
257        score = %final_score,
258        steps = result.stats.step_count,
259        moves_evaluated = result.stats.moves_evaluated,
260    );
261    result.solution
262}
solverforge_solver/basic.rs

solverforge_solver/
basic.rs
