rustsat_tools/encodings/pb/
facilitylocation.rs

1//! # PB (Multi-Criteria) Uncapacitated Facility Location Problem Encoding
2
3use rustsat::{
4    encodings::atomics,
5    instances::fio::opb,
6    lit,
7    types::{constraints::CardConstraint, Lit},
8};
9
10use crate::encodings::facilitylocation::FacilityLocation;
11
12#[derive(Default)]
13enum Line {
14    /// Hint line
15    #[default]
16    Hint,
17    /// Description
18    Description,
19    /// An objective with given index
20    Objective(usize),
21    /// Constraints stating that exactly one facility is selected per customer
22    OneFacility(usize),
23    /// Constraints stating that if a facility (first argument) is selected by a customer (second
24    /// argument), it must be opened
25    MustOpen(usize, usize),
26}
27
28pub struct Encoding {
29    data: FacilityLocation,
30    next_line: Option<Line>,
31}
32
33impl Encoding {
34    pub fn new(data: FacilityLocation) -> Self {
35        Self {
36            data,
37            next_line: Some(Line::default()),
38        }
39    }
40}
41
42impl Iterator for Encoding {
43    type Item = opb::FileLine<<Vec<(Lit, usize)> as IntoIterator>::IntoIter>;
44
45    fn next(&mut self) -> Option<Self::Item> {
46        let selected = |customer: usize, facility: usize| {
47            lit![(customer * self.data.n_facilities() + facility) as u32]
48        };
49        let opening = |facility: usize| {
50            lit![(self.data.n_facilities() * self.data.n_customers() + facility) as u32]
51        };
52        match self.next_line.take() {
53            Some(line) => Some(match line {
54                Line::Hint => {
55                    self.next_line = Some(Line::Description);
56                    opb::FileLine::Comment(format!(
57                        "#variable= {} #constraint= {}",
58                        (self.data.n_customers() + 1) * self.data.n_facilities(),
59                        self.data.n_customers() * (self.data.n_facilities() + 1)
60                    ))
61                }
62                Line::Description => {
63                    self.next_line = Some(Line::Objective(0));
64                    opb::FileLine::Comment(
65                        "MO uncapacitated facility location instance generated by RustSAT"
66                            .to_string(),
67                    )
68                }
69                Line::Objective(objidx) => {
70                    let data = &self.data;
71                    let opening_cost = (0..self.data.n_facilities())
72                        .map(|fac| (opening(fac), data.opening_cost(objidx, fac)));
73                    let obj: Vec<_> = (0..self.data.n_customers())
74                        .flat_map(|customer| {
75                            (0..self.data.n_facilities()).map(move |fac| {
76                                (
77                                    selected(customer, fac),
78                                    data.supply_cost(objidx, customer, fac),
79                                )
80                            })
81                        })
82                        .chain(opening_cost)
83                        .collect();
84                    self.next_line = Some(if objidx + 1 < self.data.n_objs() {
85                        Line::Objective(objidx + 1)
86                    } else {
87                        Line::OneFacility(0)
88                    });
89                    opb::FileLine::Objective(obj.into_iter())
90                }
91                Line::OneFacility(customer) => {
92                    let constr = CardConstraint::new_eq(
93                        (0..self.data.n_facilities()).map(|fac| selected(customer, fac)),
94                        1,
95                    );
96                    self.next_line = Some(if customer + 1 < self.data.n_customers() {
97                        Line::OneFacility(customer + 1)
98                    } else {
99                        Line::MustOpen(0, 0)
100                    });
101                    opb::FileLine::Card(constr)
102                }
103                Line::MustOpen(fac, customer) => {
104                    let constr = atomics::lit_impl_lit(selected(customer, fac), opening(fac));
105                    self.next_line = if customer + 1 < self.data.n_customers() {
106                        Some(Line::MustOpen(fac, customer + 1))
107                    } else if fac + 1 < self.data.n_facilities() {
108                        Some(Line::MustOpen(fac + 1, 0))
109                    } else {
110                        None
111                    };
112                    opb::FileLine::Clause(constr)
113                }
114            }),
115            None => None,
116        }
117    }
118}
rustsat_tools/encodings/pb/facilitylocation.rs

rustsat_tools/encodings/pb/
facilitylocation.rs
