hercules 0.5.0

A Heuristics toolbox for QUBO in Rust
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

use crate::branch_node::QuboBBNode;
use crate::branchbound::BBSolver;
use crate::{local_search_utils, utils};
use ndarray::Array1;

pub enum HeuristicSelection {
    SimpleRounding,
    LocalSearch,
}

impl HeuristicSelection {
    pub fn make_heuristic(&self, solver: &BBSolver, node: &QuboBBNode) -> (Array1<usize>, f64) {
        match self {
            Self::SimpleRounding => Self::simple_rounding(solver, node),
            Self::LocalSearch => Self::local_search(solver, node),
        }
    }

    pub fn simple_rounding(solver: &BBSolver, node: &QuboBBNode) -> (Array1<usize>, f64) {
        // round the solution to the nearest integer
        let rounded_solution = utils::rounded_vector(&node.solution);
        let objective = solver.qubo.eval_usize(&rounded_solution);

        (rounded_solution, objective)
    }

    pub fn local_search(solver: &BBSolver, node: &QuboBBNode) -> (Array1<usize>, f64) {
        // round the solution to the nearest integer
        let rounded_solution = utils::rounded_vector(&node.solution);

        let mut x = rounded_solution;

        let mut x_1 = local_search_utils::two_step_local_search_improved(&solver.qubo, &x);

        let mut steps = 0;

        while x_1 != x && steps < 100 {
            x.clone_from(&x_1);
            x_1 = local_search_utils::two_step_local_search_improved(&solver.qubo, &x);
            steps += 1;
        }

        let objective = solver.qubo.eval_usize(&x_1);

        (x_1, objective)
    }
}

#[cfg(test)]
mod tests {
    use crate::branch_node::QuboBBNode;
    use crate::branchbound::BBSolver;
    use crate::heuristic_stratagy::HeuristicSelection;
    use crate::qubo::Qubo;
    use crate::solver_options::SolverOptions;
    use crate::utils;
    use ndarray::Array1;
    use smolprng::{JsfLarge, PRNG};

    #[test]
    fn test_local_search() {
        // generate a random QUBO
        let mut prng = PRNG {
            generator: JsfLarge::default(),
        };

        let p = Qubo::make_random_qubo(50, &mut prng, 0.2);
        let mut solver = BBSolver::new(p.clone(), SolverOptions::new());

        solver.options.heuristic = HeuristicSelection::LocalSearch;

        for _ in 0..100 {
            // generate a random point inside with x in [0, 1]^10 with
            let mut x_0 = Array1::zeros(p.num_x());
            (0..p.num_x()).for_each(|i| x_0[i] = prng.gen_f64());

            let obj_0 = solver.qubo.eval(&x_0);

            // make a dummy node
            let node = QuboBBNode {
                lower_bound: f64::NEG_INFINITY,
                solution: x_0.clone(),
                fixed_variables: std::collections::HashMap::new(),
            };

            // compute the next step
            let (_, obj_1) = solver.options.heuristic.make_heuristic(&solver, &node);

            // ensure that the objective has not increased
            assert!(obj_1 <= obj_0);
        }
    }

    #[test]
    fn test_random_search() {
        // generate a random QUBO
        let mut prng = PRNG {
            generator: JsfLarge::default(),
        };

        let p = Qubo::make_random_qubo(50, &mut prng, 0.2);
        let mut solver = BBSolver::new(p.clone(), SolverOptions::new());

        solver.options.heuristic = HeuristicSelection::SimpleRounding;

        for _ in 0..100 {
            // generate a random point inside with x in [0, 1]^10 with
            let mut x_0 = Array1::zeros(p.num_x());
            (0..p.num_x()).for_each(|i| x_0[i] = prng.gen_f64());

            // make a dummy node
            let node = QuboBBNode {
                lower_bound: f64::NEG_INFINITY,
                solution: x_0.clone(),
                fixed_variables: std::collections::HashMap::new(),
            };

            let rounded_sol = utils::rounded_vector(&x_0);

            let obj_0 = solver.qubo.eval_usize(&rounded_sol);

            // compute the next step
            let (_, obj_1) = solver.options.heuristic.make_heuristic(&solver, &node);

            println!("Obj 0: {}, Obj 1: {}", obj_0, obj_1);

            // ensure that the objective has not increased
            assert!(obj_1 <= obj_0);
        }
    }
}