rustsat_tools/encodings/pb/
knapsack.rs

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
//! # PB (Multi-Criteria) Knapsack Encoding

use rustsat::{
    instances::fio::opb,
    lit,
    types::{constraints::PBConstraint, Lit},
};

use crate::encodings::knapsack::Knapsack;

#[derive(Default)]
enum Line {
    /// Hint line
    #[default]
    Hint,
    /// Description
    Description,
    /// An objective with given index
    Objective(usize),
    /// The capacity constraint
    Capacity,
}

pub struct Encoding {
    data: Knapsack,
    next_line: Option<Line>,
}

impl Encoding {
    pub fn new(data: Knapsack) -> Self {
        Self {
            data,
            next_line: Some(Line::default()),
        }
    }
}

impl Iterator for Encoding {
    type Item = opb::FileLine<<Vec<(Lit, usize)> as IntoIterator>::IntoIter>;

    fn next(&mut self) -> Option<Self::Item> {
        match self.next_line.take() {
            Some(line) => Some(match line {
                Line::Hint => {
                    self.next_line = Some(Line::Description);
                    opb::FileLine::Comment(format!(
                        "#variable= {} #constraint= 1",
                        self.data.items.len()
                    ))
                }
                Line::Description => {
                    self.next_line = Some(Line::Objective(0));
                    opb::FileLine::Comment("MO Knapsack instance generated by RustSAT".to_string())
                }
                Line::Objective(oidx) => {
                    let obj: Vec<_> = self
                        .data
                        .items
                        .iter()
                        .enumerate()
                        .map(|(iidx, item)| (!lit![iidx as u32], item.values[oidx]))
                        .collect();
                    self.next_line = Some(if oidx + 1 < self.data.items[0].values.len() {
                        Line::Objective(oidx + 1)
                    } else {
                        Line::Capacity
                    });
                    opb::FileLine::Objective(obj.into_iter())
                }
                Line::Capacity => {
                    self.next_line = None;
                    let cap_constr = PBConstraint::new_ub(
                        self.data
                            .items
                            .iter()
                            .enumerate()
                            .map(|(idx, item)| (lit![idx as u32], item.weight as isize)),
                        self.data.capacity as isize,
                    );
                    opb::FileLine::Pb(cap_constr)
                }
            }),
            None => None,
        }
    }
}