solverforge-solver 0.23.0

Solver engine for SolverForge
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use super::support::{forkable_director, run, selector, starting_solution};
use crate::phase::localsearch::{
    solve_local_search_with_resources, AcceptedCountForager, BestScoreForager, HillClimbingAcceptor,
};
use crate::scope::SolverScope;
use crate::test_utils::{create_nqueens_descriptor, NQueensSolution};

#[test]
fn sequential_and_parallel_reach_identical_trajectories() {
    let sequential = run(1, AcceptedCountForager::new(4, false), 25, None);
    for evaluator_count in [2, 4] {
        let parallel = run(
            evaluator_count,
            AcceptedCountForager::new(4, false),
            25,
            None,
        );
        assert_eq!(parallel.rows, sequential.rows);
        assert_eq!(parallel.score, sequential.score);
        assert_eq!(parallel.moves_evaluated, sequential.moves_evaluated);
        assert_eq!(parallel.moves_applied, sequential.moves_applied);
        assert_eq!(parallel.steps, sequential.steps);
    }
    assert!(sequential.moves_applied > 0);
}

#[test]
fn speculative_evaluations_are_reported_and_not_counted() {
    let sequential = run(1, AcceptedCountForager::new(1, false), 10, None);
    let parallel = run(2, AcceptedCountForager::new(1, false), 10, None);

    assert_eq!(parallel.rows, sequential.rows);
    assert_eq!(parallel.moves_evaluated, sequential.moves_evaluated);
    assert_eq!(sequential.moves_speculative, 0);
    assert!(parallel.moves_speculative > 0);
}

#[test]
fn in_phase_move_limit_reserves_the_window() {
    let parallel = run(2, BestScoreForager::new(false), 10, Some(5));

    assert_eq!(parallel.moves_evaluated, 5);
    assert_eq!(parallel.moves_speculative, 0);
}

#[test]
fn replicas_follow_solution_replacement() {
    let descriptor = create_nqueens_descriptor();
    let run_with_replacement = |evaluator_count: usize| {
        let mut solver_scope =
            SolverScope::new(forkable_director!(starting_solution(), &descriptor)).with_seed(11);
        solver_scope.start_solving();
        let mut source = selector();
        let mut acceptor = HillClimbingAcceptor::new();
        let mut forager = AcceptedCountForager::new(3, false);
        solve_local_search_with_resources(
            &mut source,
            &mut (),
            &mut acceptor,
            &mut forager,
            Some(5),
            evaluator_count,
            &mut solver_scope,
        );
        solver_scope.replace_working_solution_and_reinitialize(NQueensSolution::with_rows(&[
            9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
        ]));
        solve_local_search_with_resources(
            &mut source,
            &mut (),
            &mut acceptor,
            &mut forager,
            Some(5),
            evaluator_count,
            &mut solver_scope,
        );
        solver_scope
            .working_solution()
            .queens
            .iter()
            .map(|queen| queen.row)
            .collect::<Vec<_>>()
    };

    assert_eq!(run_with_replacement(2), run_with_replacement(1));
}

#[test]
fn evaluator_counts_above_the_ceiling_keep_the_sequential_trajectory() {
    let sequential = run(1, AcceptedCountForager::new(4, false), 25, None);
    let parallel = run(64, AcceptedCountForager::new(4, false), 25, None);

    assert_eq!(parallel.rows, sequential.rows);
    assert_eq!(parallel.score, sequential.score);
    assert_eq!(parallel.moves_evaluated, sequential.moves_evaluated);
    assert_eq!(parallel.moves_applied, sequential.moves_applied);
}

#[test]
fn exhausted_move_budget_pulls_like_the_sequential_loop() {
    // A full-scan forager never discards speculative work, so generation
    // counts compare exactly, including the pull that meets the spent budget.
    let sequential = run(1, BestScoreForager::new(false), 10, Some(5));
    let parallel = run(2, BestScoreForager::new(false), 10, Some(5));

    assert_eq!(parallel.moves_evaluated, sequential.moves_evaluated);
    assert_eq!(parallel.moves_generated, sequential.moves_generated);
    assert_eq!(parallel.moves_speculative, 0);
}