rustsat_tools/encodings/pb/
assignment.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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//! # PB (Multi-Criteria) Assignment Problem Encoding

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

use crate::encodings::assignment::Assignment;

#[derive(Default)]
enum Line {
    /// Hint line
    #[default]
    Hint,
    /// Description
    Description,
    /// An objective with given index
    Objective(usize),
    /// Constraints stating that exactly one task per agent needs to be selected
    OneTask(usize),
    /// Constraints stating that exactly one agent per task needs to be selected
    OneAgent(usize),
}

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

impl Encoding {
    pub fn new(data: Assignment) -> 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> {
        let selector = |task: usize, agent: usize| lit![(self.data.n_tasks * task + agent) as u32];
        match self.next_line.take() {
            Some(line) => Some(match line {
                Line::Hint => {
                    self.next_line = Some(Line::Description);
                    opb::FileLine::Comment(format!(
                        "#variable= {} #constraint= {}",
                        self.data.n_tasks * self.data.n_tasks,
                        2 * self.data.n_tasks
                    ))
                }
                Line::Description => {
                    self.next_line = Some(Line::Objective(0));
                    opb::FileLine::Comment(
                        "MO Assignment instance generated by RustSAT".to_string(),
                    )
                }
                Line::Objective(objidx) => {
                    let data = &self.data;
                    let obj: Vec<_> = (0..self.data.n_tasks)
                        .flat_map(|task| {
                            (0..self.data.n_tasks).map(move |agent| {
                                (selector(task, agent), data.cost(task, agent, objidx))
                            })
                        })
                        .collect();
                    self.next_line = Some(if objidx + 1 < self.data.n_objs {
                        Line::Objective(objidx + 1)
                    } else {
                        Line::OneTask(0)
                    });
                    opb::FileLine::Objective(obj.into_iter())
                }
                Line::OneTask(agent) => {
                    let constr = CardConstraint::new_eq(
                        (0..self.data.n_tasks).map(|task| selector(task, agent)),
                        1,
                    );
                    self.next_line = Some(if agent + 1 < self.data.n_tasks {
                        Line::OneTask(agent + 1)
                    } else {
                        Line::OneAgent(0)
                    });
                    opb::FileLine::Card(constr)
                }
                Line::OneAgent(task) => {
                    let constr = CardConstraint::new_eq(
                        (0..self.data.n_tasks).map(|agent| selector(task, agent)),
                        1,
                    );
                    self.next_line = if task + 1 < self.data.n_tasks {
                        Some(Line::OneAgent(task + 1))
                    } else {
                        None
                    };
                    opb::FileLine::Card(constr)
                }
            }),
            None => None,
        }
    }
}