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`, ...).
120    pub fn with_names<S: Into<String>>(mut self, names: impl IntoIterator<Item = S>) -> Self {
121        self.var_names = names.into_iter().map(Into::into).collect();
122        self
123    }
124
125    pub fn num_vars(&self) -> usize {
126        self.objective.len()
127    }
128
129    /// Name of variable `j` (0-based): the given name, or `x{j+1}` by default.
130    pub fn var_name(&self, j: usize) -> String {
131        self.var_names
132            .get(j)
133            .cloned()
134            .unwrap_or_else(|| format!("x{}", j + 1))
135    }
136
137    pub(crate) fn validate(&self) -> Result<(), Error> {
138        let n = self.num_vars();
139        if n == 0 {
140            return Err(Error::InvalidProblem(
141                "the objective has no variables".into(),
142            ));
143        }
144        if !self.var_names.is_empty() && self.var_names.len() != n {
145            return Err(Error::InvalidProblem(format!(
146                "{} variable names for {n} variables",
147                self.var_names.len()
148            )));
149        }
150        for (i, c) in self.constraints.iter().enumerate() {
151            if c.coeffs.len() != n {
152                return Err(Error::InvalidProblem(format!(
153                    "constraint {} has {} coefficients, expected {n}",
154                    i + 1,
155                    c.coeffs.len()
156                )));
157            }
158        }
159        Ok(())
160    }
161}
simplex_trace/problem.rs

simplex_trace/
problem.rs
