simplex_trace/
problem.rs

1use crate::error::Error;
2use crate::num::{IntoRational, Rational};
3
4/// Whether the objective is maximized or minimized.
5#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
6#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8pub enum Sense {
9    Maximize,
10    Minimize,
11}
12
13/// Relation of a constraint: `<=`, `>=` or `=` (also their JSON form with `serde`).
14#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
15#[derive(Clone, Copy, Debug, PartialEq, Eq)]
16pub enum Relation {
17    #[cfg_attr(feature = "serde", serde(rename = "<="))]
18    Le,
19    #[cfg_attr(feature = "serde", serde(rename = ">="))]
20    Ge,
21    #[cfg_attr(feature = "serde", serde(rename = "="))]
22    Eq,
23}
24
25/// The sign restriction of a variable.
26///
27/// The tableau only has non-negative columns, so the other signs are substituted, as in
28/// Taha: a free variable becomes `x = x+ - x-` (two columns, named `x1+` and `x1-`) and a
29/// non-positive one `x = -x-` (one column, `x1-`). Values and sensitivity are reported for the
30/// original variable. With the `serde` feature: `"non_negative"`, `"free"`, `"non_positive"`.
31#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
32#[cfg_attr(feature = "serde", serde(rename_all = "snake_case"))]
33#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
34#[non_exhaustive]
35pub enum Sign {
36    /// `x >= 0`, the default.
37    #[default]
38    NonNegative,
39    /// No sign restriction.
40    Free,
41    /// `x <= 0`.
42    NonPositive,
43}
44
45/// A linear constraint `coeffs · x  (relation)  rhs`.
46#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
47#[derive(Clone, Debug, PartialEq, Eq)]
48#[non_exhaustive]
49pub struct Constraint {
50    pub coeffs: Vec<Rational>,
51    pub relation: Relation,
52    pub rhs: Rational,
53}
54
55/// A linear program. Variables are non-negative unless declared [`free`](Problem::free) or
56/// [`non_positive`](Problem::non_positive).
57///
58/// ```
59/// use simplex_trace::{Problem, Relation};
60///
61/// // max 3x1 + 5x2  s.t.  x1 <= 4,  2x2 <= 12,  3x1 + 2x2 <= 18
62/// let problem = Problem::maximize([3, 5])
63///     .subject_to([1, 0], Relation::Le, 4)
64///     .subject_to([0, 2], Relation::Le, 12)
65///     .subject_to([3, 2], Relation::Le, 18);
66/// assert_eq!(problem.num_vars(), 2);
67/// ```
68///
69/// With the `serde` feature, numbers are exact strings (`"3"`, `"-1/2"`), never JSON
70/// floats, and `var_names` and `signs` may be omitted:
71///
72/// ```json
73/// {
74///   "sense": "maximize",
75///   "objective": ["3", "5"],
76///   "constraints": [
77///     { "coeffs": ["1", "0"], "relation": "<=", "rhs": "4" },
78///     { "coeffs": ["3", "2"], "relation": "<=", "rhs": "18" }
79///   ]
80/// }
81/// ```
82#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
83#[derive(Clone, Debug, PartialEq, Eq)]
84#[non_exhaustive]
85pub struct Problem {
86    pub sense: Sense,
87    pub objective: Vec<Rational>,
88    pub constraints: Vec<Constraint>,
89    /// Names of the variables. Empty means the defaults `x1`, `x2`, ...
90    #[cfg_attr(
91        feature = "serde",
92        serde(default, skip_serializing_if = "Vec::is_empty")
93    )]
94    pub var_names: Vec<String>,
95    /// Sign restriction of each variable. Empty means every variable is non-negative.
96    #[cfg_attr(
97        feature = "serde",
98        serde(default, skip_serializing_if = "Vec::is_empty")
99    )]
100    pub signs: Vec<Sign>,
101}
102
103/// A problem rewritten with non-negative variables only, as the tableau needs it, and how to
104/// map its columns back: `parts[j]` lists the columns of original variable `j`, each with
105/// `true` if it enters negated (`x = x+ - x-`, `x = -x-`).
106pub(crate) struct Expansion {
107    pub problem: Problem,
108    pub parts: Vec<Vec<(usize, bool)>>,
109}
110
111impl Expansion {
112    /// The values of the original variables from the values of the columns.
113    pub fn combine(&self, columns: &[Rational]) -> Vec<Rational> {
114        self.parts
115            .iter()
116            .map(|cols| {
117                cols.iter()
118                    .map(|&(col, negated)| {
119                        if negated {
120                            -&columns[col]
121                        } else {
122                            columns[col].clone()
123                        }
124                    })
125                    .sum()
126            })
127            .collect()
128    }
129}
130
131impl Problem {
132    pub fn maximize<T: IntoRational>(objective: impl IntoIterator<Item = T>) -> Self {
133        Self::new(Sense::Maximize, objective)
134    }
135
136    pub fn minimize<T: IntoRational>(objective: impl IntoIterator<Item = T>) -> Self {
137        Self::new(Sense::Minimize, objective)
138    }
139
140    fn new<T: IntoRational>(sense: Sense, objective: impl IntoIterator<Item = T>) -> Self {
141        let objective: Vec<Rational> = objective
142            .into_iter()
143            .map(IntoRational::into_rational)
144            .collect();
145        Problem {
146            sense,
147            objective,
148            constraints: Vec::new(),
149            var_names: Vec::new(),
150            signs: Vec::new(),
151        }
152    }
153
154    /// Declares variable `j` (0-based) free: it may take any sign.
155    pub fn free(self, j: usize) -> Self {
156        self.with_sign(j, Sign::Free)
157    }
158
159    /// Declares variable `j` (0-based) non-positive: `x_j <= 0`.
160    pub fn non_positive(self, j: usize) -> Self {
161        self.with_sign(j, Sign::NonPositive)
162    }
163
164    /// Sets the sign restriction of variable `j` (0-based). An index out of range is reported
165    /// by [`solve`](crate::solve).
166    pub fn with_sign(mut self, j: usize, sign: Sign) -> Self {
167        let len = self.signs.len().max(self.num_vars()).max(j + 1);
168        self.signs.resize(len, Sign::NonNegative);
169        self.signs[j] = sign;
170        self
171    }
172
173    /// Sign restriction of variable `j` (0-based).
174    pub fn sign(&self, j: usize) -> Sign {
175        self.signs.get(j).copied().unwrap_or_default()
176    }
177
178    /// The same problem with non-negative variables only (see [`Sign`]). Assumes `validate`.
179    pub(crate) fn expand(&self) -> Expansion {
180        let n = self.num_vars();
181        let mut parts = Vec::with_capacity(n);
182        let mut names = Vec::with_capacity(n);
183        // For each column: the original variable and whether it enters negated.
184        let mut columns: Vec<(usize, bool)> = Vec::with_capacity(n);
185        for j in 0..n {
186            let name = self.var_name(j);
187            let mut add = |suffix: &str, negated: bool, parts: &mut Vec<(usize, bool)>| {
188                parts.push((columns.len(), negated));
189                columns.push((j, negated));
190                names.push(format!("{name}{suffix}"));
191            };
192            let mut own = Vec::new();
193            match self.sign(j) {
194                Sign::NonNegative => add("", false, &mut own),
195                Sign::Free => {
196                    add("+", false, &mut own);
197                    add("-", true, &mut own);
198                }
199                Sign::NonPositive => add("-", true, &mut own),
200            }
201            parts.push(own);
202        }
203        let expand_row = |row: &[Rational]| -> Vec<Rational> {
204            columns
205                .iter()
206                .map(|&(j, negated)| if negated { -&row[j] } else { row[j].clone() })
207                .collect()
208        };
209        let problem = Problem {
210            sense: self.sense,
211            objective: expand_row(&self.objective),
212            constraints: self
213                .constraints
214                .iter()
215                .map(|c| Constraint {
216                    coeffs: expand_row(&c.coeffs),
217                    relation: c.relation,
218                    rhs: c.rhs.clone(),
219                })
220                .collect(),
221            var_names: names,
222            signs: Vec::new(),
223        };
224        Expansion { problem, parts }
225    }
226
227    /// Adds a constraint. Length mismatches are reported by [`solve`](crate::solve).
228    pub fn subject_to<T: IntoRational>(
229        mut self,
230        coeffs: impl IntoIterator<Item = T>,
231        relation: Relation,
232        rhs: impl IntoRational,
233    ) -> Self {
234        self.constraints.push(Constraint {
235            coeffs: coeffs
236                .into_iter()
237                .map(IntoRational::into_rational)
238                .collect(),
239            relation,
240            rhs: rhs.into_rational(),
241        });
242        self
243    }
244
245    /// Overrides the default variable names (`x1`, `x2`, ...). Names must be unique, may not
246    /// look like a slack or artificial column (`s1`, `a2`, ...) and may not end in `+` or `-`
247    /// (the columns of free and non-positive variables); [`solve`](crate::solve) rejects such
248    /// problems.
249    pub fn with_names<S: Into<String>>(mut self, names: impl IntoIterator<Item = S>) -> Self {
250        self.var_names = names.into_iter().map(Into::into).collect();
251        self
252    }
253
254    pub fn num_vars(&self) -> usize {
255        self.objective.len()
256    }
257
258    /// Name of variable `j` (0-based): the given name, or `x{j+1}` by default.
259    pub fn var_name(&self, j: usize) -> String {
260        self.var_names
261            .get(j)
262            .cloned()
263            .unwrap_or_else(|| format!("x{}", j + 1))
264    }
265
266    pub(crate) fn validate(&self) -> Result<(), Error> {
267        let n = self.num_vars();
268        if n == 0 {
269            return Err(Error::InvalidProblem(
270                "the objective has no variables".into(),
271            ));
272        }
273        if !self.var_names.is_empty() && self.var_names.len() != n {
274            return Err(Error::InvalidProblem(format!(
275                "{} variable names for {n} variables",
276                self.var_names.len()
277            )));
278        }
279        if !self.signs.is_empty() && self.signs.len() != n {
280            return Err(Error::InvalidProblem(format!(
281                "{} sign restrictions for {n} variables",
282                self.signs.len()
283            )));
284        }
285        for (j, name) in self.var_names.iter().enumerate() {
286            if name.ends_with(['+', '-']) {
287                return Err(Error::InvalidProblem(format!(
288                    "variable name {name:?} may not end in '+' or '-' (reserved for the columns of free and non-positive variables)"
289                )));
290            }
291            if name.is_empty() {
292                return Err(Error::InvalidProblem(format!(
293                    "variable {} has an empty name",
294                    j + 1
295                )));
296            }
297            if self.var_names[..j].contains(name) {
298                return Err(Error::InvalidProblem(format!(
299                    "duplicate variable name {name:?}"
300                )));
301            }
302            // `s1`, `a2`, ... are the slack/surplus and artificial columns of the tableau.
303            let mut chars = name.chars();
304            let reserved = matches!(chars.next(), Some('s' | 'a'))
305                && chars.clone().next().is_some()
306                && chars.all(|c| c.is_ascii_digit());
307            if reserved {
308                return Err(Error::InvalidProblem(format!(
309                    "variable name {name:?} is reserved for slack and artificial columns"
310                )));
311            }
312        }
313        for (i, c) in self.constraints.iter().enumerate() {
314            if c.coeffs.len() != n {
315                return Err(Error::InvalidProblem(format!(
316                    "constraint {} has {} coefficients, expected {n}",
317                    i + 1,
318                    c.coeffs.len()
319                )));
320            }
321        }
322        Ok(())
323    }
324}
simplex_trace/problem.rs

simplex_trace/
problem.rs
