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/// A linear constraint `coeffs · x  (relation)  rhs`.
26#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
27#[derive(Clone, Debug, PartialEq, Eq)]
28#[non_exhaustive]
29pub struct Constraint {
30    #[cfg_attr(feature = "serde", serde(with = "crate::serde_rational::vec"))]
31    pub coeffs: Vec<Rational>,
32    pub relation: Relation,
33    #[cfg_attr(feature = "serde", serde(with = "crate::serde_rational::one"))]
34    pub rhs: Rational,
35}
36
37/// A linear program with non-negative variables.
38///
39/// ```
40/// use simplex_trace::{Problem, Relation};
41///
42/// // max 3x1 + 5x2  s.t.  x1 <= 4,  2x2 <= 12,  3x1 + 2x2 <= 18
43/// let problem = Problem::maximize([3, 5])
44///     .subject_to([1, 0], Relation::Le, 4)
45///     .subject_to([0, 2], Relation::Le, 12)
46///     .subject_to([3, 2], Relation::Le, 18);
47/// assert_eq!(problem.num_vars(), 2);
48/// ```
49///
50/// With the `serde` feature, numbers are exact strings (`"3"`, `"-1/2"`), never JSON
51/// floats, and `var_names` may be omitted:
52///
53/// ```json
54/// {
55///   "sense": "maximize",
56///   "objective": ["3", "5"],
57///   "constraints": [
58///     { "coeffs": ["1", "0"], "relation": "<=", "rhs": "4" },
59///     { "coeffs": ["3", "2"], "relation": "<=", "rhs": "18" }
60///   ]
61/// }
62/// ```
63#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
64#[derive(Clone, Debug, PartialEq, Eq)]
65#[non_exhaustive]
66pub struct Problem {
67    pub sense: Sense,
68    #[cfg_attr(feature = "serde", serde(with = "crate::serde_rational::vec"))]
69    pub objective: Vec<Rational>,
70    pub constraints: Vec<Constraint>,
71    /// Names of the variables. Empty means the defaults `x1`, `x2`, ...
72    #[cfg_attr(
73        feature = "serde",
74        serde(default, skip_serializing_if = "Vec::is_empty")
75    )]
76    pub var_names: Vec<String>,
77}
78
79impl Problem {
80    pub fn maximize<T: IntoRational>(objective: impl IntoIterator<Item = T>) -> Self {
81        Self::new(Sense::Maximize, objective)
82    }
83
84    pub fn minimize<T: IntoRational>(objective: impl IntoIterator<Item = T>) -> Self {
85        Self::new(Sense::Minimize, objective)
86    }
87
88    fn new<T: IntoRational>(sense: Sense, objective: impl IntoIterator<Item = T>) -> Self {
89        let objective: Vec<Rational> = objective
90            .into_iter()
91            .map(IntoRational::into_rational)
92            .collect();
93        Problem {
94            sense,
95            objective,
96            constraints: Vec::new(),
97            var_names: Vec::new(),
98        }
99    }
100
101    /// Adds a constraint. Length mismatches are reported by [`solve`](crate::solve).
102    pub fn subject_to<T: IntoRational>(
103        mut self,
104        coeffs: impl IntoIterator<Item = T>,
105        relation: Relation,
106        rhs: impl IntoRational,
107    ) -> Self {
108        self.constraints.push(Constraint {
109            coeffs: coeffs
110                .into_iter()
111                .map(IntoRational::into_rational)
112                .collect(),
113            relation,
114            rhs: rhs.into_rational(),
115        });
116        self
117    }
118
119    /// Overrides the default variable names (`x1`, `x2`, ...). Names must be unique and may
120    /// not look like a slack or artificial column (`s1`, `a2`, ...); [`solve`](crate::solve)
121    /// rejects such problems.
122    pub fn with_names<S: Into<String>>(mut self, names: impl IntoIterator<Item = S>) -> Self {
123        self.var_names = names.into_iter().map(Into::into).collect();
124        self
125    }
126
127    pub fn num_vars(&self) -> usize {
128        self.objective.len()
129    }
130
131    /// Name of variable `j` (0-based): the given name, or `x{j+1}` by default.
132    pub fn var_name(&self, j: usize) -> String {
133        self.var_names
134            .get(j)
135            .cloned()
136            .unwrap_or_else(|| format!("x{}", j + 1))
137    }
138
139    pub(crate) fn validate(&self) -> Result<(), Error> {
140        let n = self.num_vars();
141        if n == 0 {
142            return Err(Error::InvalidProblem(
143                "the objective has no variables".into(),
144            ));
145        }
146        if !self.var_names.is_empty() && self.var_names.len() != n {
147            return Err(Error::InvalidProblem(format!(
148                "{} variable names for {n} variables",
149                self.var_names.len()
150            )));
151        }
152        for (j, name) in self.var_names.iter().enumerate() {
153            if name.is_empty() {
154                return Err(Error::InvalidProblem(format!(
155                    "variable {} has an empty name",
156                    j + 1
157                )));
158            }
159            if self.var_names[..j].contains(name) {
160                return Err(Error::InvalidProblem(format!(
161                    "duplicate variable name {name:?}"
162                )));
163            }
164            // `s1`, `a2`, ... are the slack/surplus and artificial columns of the tableau.
165            let mut chars = name.chars();
166            let reserved = matches!(chars.next(), Some('s' | 'a'))
167                && chars.clone().next().is_some()
168                && chars.all(|c| c.is_ascii_digit());
169            if reserved {
170                return Err(Error::InvalidProblem(format!(
171                    "variable name {name:?} is reserved for slack and artificial columns"
172                )));
173            }
174        }
175        for (i, c) in self.constraints.iter().enumerate() {
176            if c.coeffs.len() != n {
177                return Err(Error::InvalidProblem(format!(
178                    "constraint {} has {} coefficients, expected {n}",
179                    i + 1,
180                    c.coeffs.len()
181                )));
182            }
183        }
184        Ok(())
185    }
186}
simplex_trace/problem.rs

simplex_trace/
problem.rs
