solverforge-solver 0.20.4

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

use solverforge_core::domain::PlanningSolution;
use solverforge_core::fast_hash::FastSet;

use super::assignment_candidate::{
    order_candidates, AssignmentMoveIntent, ScalarAssignmentMoveOptions,
};
use super::assignment_entity::{
    required_entities_by_scarcity, required_value_degrees, sort_values_by_required_scarcity,
};
use super::assignment_path::{
    move_from_edits, AssignmentPathWork, AssignmentRequest, AugmentingPathSearch,
};
use super::assignment_state::ScalarAssignmentState;
use crate::builder::ScalarAssignmentBinding;
use crate::heuristic::r#move::CompoundScalarMove;

pub(super) fn required_batch_move<S, ShouldStop>(
    group: &ScalarAssignmentBinding<S>,
    solution: &S,
    state: &mut ScalarAssignmentState,
    options: ScalarAssignmentMoveOptions,
    should_stop: &mut ShouldStop,
) -> Option<CompoundScalarMove<S>>
where
    S: PlanningSolution,
    ShouldStop: FnMut() -> bool,
{
    let mut entities = required_entities_by_scarcity(
        group,
        solution,
        state,
        options.value_candidate_limit,
        should_stop,
    )?;
    order_candidates(&mut entities, options);
    if should_stop() {
        return None;
    }
    let value_degrees = required_value_degrees(
        group,
        solution,
        &entities,
        options.value_candidate_limit,
        should_stop,
    )?;
    let mut scalar_edits = Vec::new();
    let mut edited_entities = FastSet::default();
    let mut visiting = FastSet::default();
    let mut blockers = Vec::new();
    let mut overlay = state.take_path_overlay();
    overlay.clear();
    let search =
        AugmentingPathSearch::new(group, solution, options, AssignmentMoveIntent::required());
    for entity_index in entities {
        if should_stop() {
            overlay.clear();
            state.restore_path_overlay(overlay);
            return None;
        }
        if overlay.current_value(state, entity_index).is_some() {
            continue;
        }
        let mut values =
            group.candidate_values(solution, entity_index, options.value_candidate_limit);
        sort_values_by_required_scarcity(
            group,
            solution,
            entity_index,
            &value_degrees,
            &mut values,
        );
        for value in values {
            if should_stop() {
                overlay.clear();
                state.restore_path_overlay(overlay);
                return None;
            }
            let overlay_checkpoint = overlay.checkpoint();
            let edit_checkpoint = scalar_edits.len();
            visiting.clear();
            let mut work = AssignmentPathWork::new(
                &mut overlay,
                &mut visiting,
                &mut scalar_edits,
                &mut blockers,
            );
            if !search.discover(
                state,
                // The batch below can retain only independent single-entity edits.
                // Defer augmenting rematches to the following required cursor,
                // where their multi-entity edits can actually be applied.
                AssignmentRequest::root(entity_index, value, 0),
                &mut work,
                should_stop,
            ) {
                overlay.rollback(overlay_checkpoint);
                scalar_edits.truncate(edit_checkpoint);
                if should_stop() {
                    overlay.clear();
                    state.restore_path_overlay(overlay);
                    return None;
                }
                continue;
            }
            let candidate_edits = &scalar_edits[edit_checkpoint..];
            if candidate_edits
                .iter()
                .any(|edit| edited_entities.contains(&edit.entity_index()))
            {
                overlay.rollback(overlay_checkpoint);
                scalar_edits.truncate(edit_checkpoint);
                continue;
            }
            if candidate_edits.len() != 1 {
                overlay.rollback(overlay_checkpoint);
                scalar_edits.truncate(edit_checkpoint);
                continue;
            }
            let candidate = &candidate_edits[0];
            if !group.value_is_legal(solution, candidate.entity_index(), candidate.to_value()) {
                overlay.rollback(overlay_checkpoint);
                scalar_edits.truncate(edit_checkpoint);
                continue;
            }
            for edit in candidate_edits {
                edited_entities.insert(edit.entity_index());
            }
            break;
        }
    }
    if should_stop() {
        overlay.clear();
        state.restore_path_overlay(overlay);
        return None;
    }
    overlay.clear();
    state.restore_path_overlay(overlay);
    if scalar_edits.is_empty() {
        return None;
    }
    if !state.scalar_edits_feasible(group, solution, &scalar_edits) {
        return None;
    }
    move_from_edits(group, solution, &scalar_edits, "scalar_assignment_required")
}