simplex_trace/
num.rs

1use std::cmp::Ordering;
2use std::fmt;
3use std::ops::Neg;
4
5use num_bigint::BigInt;
6use num_rational::BigRational;
7use num_traits::{Signed, Zero};
8
9/// Arbitrary-precision exact rational number used for every value in the crate.
10pub type Rational = BigRational;
11
12/// Conversion into a [`Rational`], so the builder API accepts plain integers and fractions.
13pub trait IntoRational {
14    fn into_rational(self) -> Rational;
15}
16
17impl IntoRational for Rational {
18    fn into_rational(self) -> Rational {
19        self
20    }
21}
22
23impl IntoRational for i32 {
24    fn into_rational(self) -> Rational {
25        Rational::from_integer(BigInt::from(self))
26    }
27}
28
29impl IntoRational for i64 {
30    fn into_rational(self) -> Rational {
31        Rational::from_integer(BigInt::from(self))
32    }
33}
34
35/// `(numerator, denominator)`. Panics if the denominator is zero.
36impl IntoRational for (i64, i64) {
37    fn into_rational(self) -> Rational {
38        ratio(self.0, self.1)
39    }
40}
41
42/// Builds the fraction `n / d`. Panics if `d == 0`.
43pub fn ratio(n: i64, d: i64) -> Rational {
44    Rational::new(BigInt::from(n), BigInt::from(d))
45}
46
47/// A number of the form `m·M + c`, where `M` is the symbolic "big M" penalty.
48///
49/// Ordering is lexicographic (`M` dominates), which is exactly what the Big-M method needs
50/// without picking a numeric value for `M`. With `m == 0` it is an ordinary rational.
51///
52/// With the `serde` feature it is `{"m": "7", "c": "-4"}` for `7M - 4`.
53#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
54#[derive(Clone, Debug, PartialEq, Eq)]
55pub struct Coef {
56    /// Coefficient of `M`.
57    #[cfg_attr(feature = "serde", serde(with = "crate::serde_rational::one"))]
58    pub m: Rational,
59    /// Constant part.
60    #[cfg_attr(feature = "serde", serde(with = "crate::serde_rational::one"))]
61    pub c: Rational,
62}
63
64impl Coef {
65    pub fn zero() -> Self {
66        Coef::constant(Rational::zero())
67    }
68
69    pub fn constant(c: Rational) -> Self {
70        Coef {
71            m: Rational::zero(),
72            c,
73        }
74    }
75
76    pub fn big_m(m: Rational) -> Self {
77        Coef {
78            m,
79            c: Rational::zero(),
80        }
81    }
82
83    pub fn is_zero(&self) -> bool {
84        self.m.is_zero() && self.c.is_zero()
85    }
86
87    pub fn is_negative(&self) -> bool {
88        match self.m.cmp(&Rational::zero()) {
89            Ordering::Less => true,
90            Ordering::Greater => false,
91            Ordering::Equal => self.c.is_negative(),
92        }
93    }
94
95    pub fn is_positive(&self) -> bool {
96        match self.m.cmp(&Rational::zero()) {
97            Ordering::Greater => true,
98            Ordering::Less => false,
99            Ordering::Equal => self.c.is_positive(),
100        }
101    }
102
103    /// `self -= f * r`
104    pub(crate) fn sub_mul(&mut self, f: &Coef, r: &Rational) {
105        self.m -= &f.m * r;
106        self.c -= &f.c * r;
107    }
108}
109
110impl PartialOrd for Coef {
111    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
112        Some(self.cmp(other))
113    }
114}
115
116impl Ord for Coef {
117    fn cmp(&self, other: &Self) -> Ordering {
118        self.m.cmp(&other.m).then_with(|| self.c.cmp(&other.c))
119    }
120}
121
122impl Neg for Coef {
123    type Output = Coef;
124
125    fn neg(self) -> Coef {
126        Coef {
127            m: -self.m,
128            c: -self.c,
129        }
130    }
131}
132
133impl fmt::Display for Coef {
134    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
135        if self.m.is_zero() {
136            return write!(f, "{}", self.c);
137        }
138        let one = Rational::from_integer(BigInt::from(1));
139        let m = if self.m == one {
140            "M".to_string()
141        } else if self.m == -one {
142            "-M".to_string()
143        } else {
144            format!("{}M", self.m)
145        };
146        if self.c.is_zero() {
147            write!(f, "{m}")
148        } else if self.c.is_negative() {
149            write!(f, "{m} - {}", -self.c.clone())
150        } else {
151            write!(f, "{m} + {}", self.c)
152        }
153    }
154}
simplex_trace/num.rs

simplex_trace/
num.rs
