rustsat_tools/encodings/pb/
knapsack.rs

1//! # PB (Multi-Criteria) Knapsack Encoding
2
3use rustsat::{
4    instances::fio::opb,
5    lit,
6    types::{constraints::PbConstraint, Lit},
7};
8
9use crate::encodings::knapsack::Knapsack;
10
11#[derive(Default)]
12enum Line {
13    /// Hint line
14    #[default]
15    Hint,
16    /// Description
17    Description,
18    /// An objective with given index
19    Objective(usize),
20    /// The capacity constraint
21    Capacity,
22}
23
24pub struct Encoding {
25    data: Knapsack,
26    next_line: Option<Line>,
27}
28
29impl Encoding {
30    pub fn new(data: Knapsack) -> Self {
31        Self {
32            data,
33            next_line: Some(Line::default()),
34        }
35    }
36}
37
38impl Iterator for Encoding {
39    type Item = opb::FileLine<<Vec<(Lit, usize)> as IntoIterator>::IntoIter>;
40
41    fn next(&mut self) -> Option<Self::Item> {
42        match self.next_line.take() {
43            Some(line) => Some(match line {
44                Line::Hint => {
45                    self.next_line = Some(Line::Description);
46                    opb::FileLine::Comment(format!(
47                        "#variable= {} #constraint= 1",
48                        self.data.items.len()
49                    ))
50                }
51                Line::Description => {
52                    self.next_line = Some(Line::Objective(0));
53                    opb::FileLine::Comment("MO Knapsack instance generated by RustSAT".to_string())
54                }
55                Line::Objective(oidx) => {
56                    let obj: Vec<_> = self
57                        .data
58                        .items
59                        .iter()
60                        .enumerate()
61                        .map(|(iidx, item)| (!lit![iidx as u32], item.values[oidx]))
62                        .collect();
63                    self.next_line = Some(if oidx + 1 < self.data.items[0].values.len() {
64                        Line::Objective(oidx + 1)
65                    } else {
66                        Line::Capacity
67                    });
68                    opb::FileLine::Objective(obj.into_iter())
69                }
70                Line::Capacity => {
71                    self.next_line = None;
72                    let cap_constr = PbConstraint::new_ub(
73                        self.data
74                            .items
75                            .iter()
76                            .enumerate()
77                            .map(|(idx, item)| (lit![idx as u32], item.weight as isize)),
78                        self.data.capacity as isize,
79                    );
80                    opb::FileLine::Pb(cap_constr)
81                }
82            }),
83            None => None,
84        }
85    }
86}
rustsat_tools/encodings/pb/knapsack.rs

rustsat_tools/encodings/pb/
knapsack.rs
