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

use crate::constraint::{Constraint, ConstraintType};
use crate::preprocess::preprocess_qubo;
use crate::qubo::Qubo;
use std::collections::HashMap;

/// Find Equations and inequalities that can be used to strengthen the QUBO by probing using the presolver
/// This is a probing method that tries to fix each variable to 0 and 1 and see what other variables can be fixed as a result
fn find_constraints(
    qubo: &Qubo,
    fixed_vars: &HashMap<usize, usize>,
    in_standard_form: bool,
) -> (Vec<Constraint>, HashMap<usize, usize>) {

    let mut constraints = Vec::new();
    let mut new_fixed_vars = HashMap::new();
    let n = qubo.num_x();

    for i in 0..n {
        if fixed_vars.contains_key(&i) {
            continue;
        }

        let mut fixed_vars_0 = fixed_vars.clone();
        let mut fixed_vars_1 = fixed_vars.clone();

        fixed_vars_0.insert(i, 0);
        fixed_vars_1.insert(i, 1);

        let fixed_vars_0 = preprocess_qubo(qubo, &fixed_vars_0, in_standard_form);
        let fixed_vars_1 = preprocess_qubo(qubo, &fixed_vars_1, in_standard_form);

        for j in 0..n {
            if i == j || fixed_vars.contains_key(&j) {
                continue;
            }

            // see if we have any equations
            if fixed_vars_0.contains_key(&j) && fixed_vars_1.contains_key(&j) {
                if fixed_vars_1[&j] == 1 && fixed_vars_0[&j] == 0 {
                    constraints.push(Constraint::new(i, j, ConstraintType::Equal));
                } else if fixed_vars_0[&j] == 1 && fixed_vars_1[&j] == 0 {
                    constraints.push(Constraint::new(i, j, ConstraintType::ExactlyOne));
                } else if fixed_vars_0[&j] == 0  && fixed_vars_1[&j] == 0 {
                    new_fixed_vars.insert(j, 0);
                } else { new_fixed_vars.insert(j, 1); }
            // see if we have any inequalities
            }else{
                if fixed_vars_0.contains_key(&j) {
                    if fixed_vars_0[&j] == 1 {
                        constraints.push(Constraint::new(i, j, ConstraintType::AtLeastOne));
                    } else if fixed_vars_0[&j] == 0 {
                        constraints.push(Constraint::new(i, j, ConstraintType::LessThan));
                    }
                }
                else if fixed_vars_1.contains_key(&j) {
                    if fixed_vars_1[&j] == 1 {
                        constraints.push(Constraint::new(i, j, ConstraintType::GreaterThan));
                    } else if fixed_vars_1[&j] == 0 {
                        constraints.push(Constraint::new(i, j, ConstraintType::NoMoreThanOne));
                    }
                }
            }
        }
    }

    (constraints, new_fixed_vars)
}