rustsat_tools/encodings/
knapsack.rs

1//! # Shared Knapsack Encoding Tooling
2//!
3//! - Data types
4//! - Input parser
5//! - Random generator
6
7use std::{io, ops::Range};
8
9use rand::{Rng, SeedableRng};
10use rand_chacha::ChaCha8Rng;
11
12/// An instance of the (multi-criteria 0-1) knapsack problem
13#[derive(Clone, PartialEq, Eq)]
14pub struct Knapsack {
15    pub(crate) items: Vec<ItemData>,
16    pub(crate) capacity: usize,
17}
18
19/// Data associated with one knapsack item
20#[derive(Clone, PartialEq, Eq)]
21pub(crate) struct ItemData {
22    pub weight: usize,
23    pub values: Vec<usize>,
24}
25
26pub enum Capacity {
27    /// A fixed knapsack capacity
28    Fixed(usize),
29    /// Calculate the capacity as the total weight divided by the given value
30    FractionTotalWeight(usize),
31}
32
33impl Knapsack {
34    pub fn random(
35        n_items: usize,
36        n_objectives: usize,
37        value_range: Range<usize>,
38        weight_range: Range<usize>,
39        capacity: Capacity,
40        seed: u64,
41    ) -> Self {
42        let mut rng = ChaCha8Rng::seed_from_u64(seed);
43        let items: Vec<_> = (0..n_items)
44            .map(|_| {
45                let weight = rng.random_range(weight_range.clone());
46                let values = (0..n_objectives)
47                    .map(|_| rng.random_range(value_range.clone()))
48                    .collect();
49                ItemData { weight, values }
50            })
51            .collect();
52        let capacity = match capacity {
53            Capacity::Fixed(cap) => cap,
54            Capacity::FractionTotalWeight(div) => {
55                items.iter().fold(0, |sum, item| sum + item.weight) / div
56            }
57        };
58        Self { items, capacity }
59    }
60
61    pub fn from_file(reader: impl io::BufRead, format: FileFormat) -> anyhow::Result<Self> {
62        match format {
63            FileFormat::MooLibrary => parsing::parse_moolib(reader),
64            FileFormat::VOptLib => parsing::parse_voptlib(reader),
65        }
66    }
67}
68
69/// Possible Knapsack input file formats
70#[derive(Clone, Copy, PartialEq, Eq)]
71pub enum FileFormat {
72    /// Input files as provided by [MOO-Library](http://home.ku.edu.tr/~moolibrary/)
73    MooLibrary,
74    /// Input files as provided by [vOptLib](https://github.com/vOptSolver/vOptLib/tree/master/UKP)
75    VOptLib,
76}
77
78mod parsing {
79    use std::io;
80
81    use anyhow::Context;
82    use nom::{
83        bytes::complete::tag,
84        character::complete::{space0, u32},
85        error::Error as NomErr,
86        sequence::tuple,
87    };
88
89    use crate::parsing::{callback_list, single_value};
90
91    macro_rules! next_non_comment_line {
92        ($reader:expr) => {
93            'block: {
94                let mut buf = String::new();
95                while $reader.read_line(&mut buf)? > 0 {
96                    if !buf.trim_start().starts_with('#') && !buf.trim().is_empty() {
97                        break 'block Some(buf);
98                    }
99                    buf.clear();
100                }
101                None
102            }
103        };
104    }
105
106    pub fn parse_moolib(mut reader: impl io::BufRead) -> anyhow::Result<super::Knapsack> {
107        let line = next_non_comment_line!(reader)
108            .context("file ended before number of objectives line")?;
109        let (_, n_obj) = single_value(u32, "#")(&line)
110            .map_err(|e| e.to_owned())
111            .with_context(|| format!("failed to parse number of objectives line '{line}'"))?;
112        let line =
113            next_non_comment_line!(reader).context("file ended before number of items line")?;
114        let (_, n_items) = single_value(u32, "#")(&line)
115            .map_err(|e| e.to_owned())
116            .with_context(|| format!("failed to parse number of items line '{line}'"))?;
117        let line = next_non_comment_line!(reader).context("file ended before capacity line")?;
118        let (_, capacity) = single_value(u32, "#")(&line)
119            .map_err(|e| e.to_owned())
120            .with_context(|| format!("failed to parse capacity line '{line}'"))?;
121        let mut inst = super::Knapsack {
122            items: vec![
123                super::ItemData {
124                    weight: 0,
125                    values: vec![]
126                };
127                n_items as usize
128            ],
129            capacity: capacity as usize,
130        };
131        let mut buf = String::new();
132        let mut started = false;
133        let mut ended = false;
134        while reader.read_line(&mut buf)? > 0 {
135            let remain = buf.trim_start();
136            if remain.starts_with('#') || buf.trim().is_empty() {
137                buf.clear();
138                continue;
139            }
140            let remain = if started {
141                remain
142            } else {
143                anyhow::ensure!(remain.starts_with('['), "expected list to start");
144                started = true;
145                &remain[1..]
146            };
147            let mut item_idx = 0;
148            let remain = callback_list(remain, u32, |value| {
149                anyhow::ensure!(item_idx < inst.items.len(), "too many values in value list");
150                inst.items[item_idx].values.push(value as usize);
151                item_idx += 1;
152                Ok(())
153            })?;
154            match tuple::<_, _, NomErr<_>, _>((space0, tag(","), space0))(remain) {
155                Ok(_) => (),
156                Err(_) => {
157                    tuple::<_, _, NomErr<_>, _>((space0, tag("]")))(remain)
158                        .map_err(|e| e.to_owned())
159                        .context("failed to find closing delimiter for value list")?;
160                    ended = true;
161                    break;
162                }
163            }
164            buf.clear();
165        }
166        anyhow::ensure!(ended, "file ended before value list ended");
167        let line = next_non_comment_line!(reader).context("file ended before weight line")?;
168        let mut item_idx = 0;
169        callback_list(line.trim_start(), u32, |weight| {
170            anyhow::ensure!(
171                item_idx < inst.items.len(),
172                "too many values in weight list"
173            );
174            inst.items[item_idx].weight = weight as usize;
175            item_idx += 1;
176            Ok(())
177        })?;
178        for item in &inst.items {
179            anyhow::ensure!(
180                item.values.len() == n_obj as usize,
181                "number of values for item does not match number of objectives"
182            );
183        }
184        Ok(inst)
185    }
186
187    pub fn parse_voptlib(mut reader: impl io::BufRead) -> anyhow::Result<super::Knapsack> {
188        let line =
189            next_non_comment_line!(reader).context("file ended before number of items line")?;
190        let (_, n_items) = single_value(u32, "#")(&line)
191            .map_err(|e| e.to_owned())
192            .with_context(|| format!("failed to parse number of items line '{line}'"))?;
193        let line = next_non_comment_line!(reader)
194            .context("file ended before number of objectives line")?;
195        let (_, n_obj) = single_value(u32, "#")(&line)
196            .map_err(|e| e.to_owned())
197            .with_context(|| format!("failed to parse number of objectives line '{line}'"))?;
198        let _ = single_value(u32, "#")(&line)
199            .map_err(|e| e.to_owned())
200            .with_context(|| format!("failed to parse number of constraints line '{line}'"))?;
201        let mut inst = super::Knapsack {
202            items: vec![
203                super::ItemData {
204                    weight: 0,
205                    values: vec![]
206                };
207                n_items as usize
208            ],
209            capacity: 0,
210        };
211        for obj_idx in 0..n_obj {
212            for item_idx in 0..n_items {
213                let line = next_non_comment_line!(reader).with_context(|| {
214                    format!("file ended before {item_idx} value of objective {obj_idx}")
215                })?;
216                let (_, value) = single_value(u32, "#")(&line)
217                    .map_err(|e| e.to_owned())
218                    .with_context(|| {
219                        format!("failed to parse {item_idx} value of objective {obj_idx} '{line}'")
220                    })?;
221                inst.items[item_idx as usize].values.push(value as usize);
222            }
223        }
224        for item_idx in 0..n_items {
225            let line = next_non_comment_line!(reader)
226                .with_context(|| format!("file ended before weight of item {item_idx}"))?;
227            let (_, weight) = single_value(u32, "#")(&line)
228                .map_err(|e| e.to_owned())
229                .with_context(|| format!("failed to parse weight of item {item_idx} '{line}'"))?;
230            inst.items[item_idx as usize].weight = weight as usize;
231        }
232        Ok(inst)
233    }
234
235    #[cfg(test)]
236    mod tests {
237        use std::{fs::File, io::BufReader};
238
239        #[test]
240        fn moolib() {
241            let reader = BufReader::new(File::open("./data/KP_p-3_n-10_ins-1.dat").unwrap());
242            super::parse_moolib(reader).unwrap();
243        }
244
245        #[test]
246        fn voptlib() {
247            let reader = BufReader::new(File::open("./data/F5050W01.dat").unwrap());
248            super::parse_voptlib(reader).unwrap();
249        }
250    }
251}
rustsat_tools/encodings/knapsack.rs

rustsat_tools/encodings/
knapsack.rs
