Skip to main content

logicaffeine_proof/
linarith_solve.rs

1//! The decision core for linear integer arithmetic: Fourier-Motzkin elimination
2//! that tracks the non-negative combination it eliminates with, so an
3//! unsatisfiable system yields its **Farkas certificate** — the multipliers `λᵢ ≥ 0`
4//! on the original constraints such that `Σ λᵢ·constraintᵢ` is a positive constant
5//! `≤ 0` (a contradiction). The proof engine reconstructs a kernel proof from those
6//! multipliers via `le_mul_nonneg`/`le_add_mono` + the Bool no-confusion
7//! discriminator. Pure and self-contained — no kernel, no certificates here.
8
9use std::collections::BTreeMap;
10
11use crate::ProofTerm;
12
13/// A linear expression `Σ cⱼ·xⱼ + constant` over the integers (zero coefficients
14/// pruned, so equality is canonical).
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct LinExpr {
17    pub coeffs: BTreeMap<String, i64>,
18    pub constant: i64,
19}
20
21impl LinExpr {
22    fn constant(c: i64) -> Self {
23        LinExpr {
24            coeffs: BTreeMap::new(),
25            constant: c,
26        }
27    }
28    fn var(name: &str) -> Self {
29        let mut coeffs = BTreeMap::new();
30        coeffs.insert(name.to_string(), 1);
31        LinExpr {
32            coeffs,
33            constant: 0,
34        }
35    }
36    fn prune(mut self) -> Self {
37        self.coeffs.retain(|_, c| *c != 0);
38        self
39    }
40    fn add(&self, o: &Self) -> Self {
41        let mut coeffs = self.coeffs.clone();
42        for (k, v) in &o.coeffs {
43            *coeffs.entry(k.clone()).or_insert(0) += v;
44        }
45        LinExpr {
46            coeffs,
47            constant: self.constant + o.constant,
48        }
49        .prune()
50    }
51    fn neg(&self) -> Self {
52        LinExpr {
53            coeffs: self.coeffs.iter().map(|(k, v)| (k.clone(), -v)).collect(),
54            constant: -self.constant,
55        }
56    }
57    pub fn sub(&self, o: &Self) -> Self {
58        self.add(&o.neg())
59    }
60    /// True when this is a bare integer constant (no variables remain).
61    pub fn is_const(&self) -> bool {
62        self.coeffs.is_empty()
63    }
64    fn scale(&self, k: i64) -> Self {
65        LinExpr {
66            coeffs: self
67                .coeffs
68                .iter()
69                .map(|(x, v)| (x.clone(), v * k))
70                .collect(),
71            constant: self.constant * k,
72        }
73        .prune()
74    }
75    fn is_constant(&self) -> bool {
76        self.coeffs.is_empty()
77    }
78    fn coeff(&self, v: &str) -> i64 {
79        self.coeffs.get(v).copied().unwrap_or(0)
80    }
81}
82
83/// Parse a [`ProofTerm`] into a linear expression, or `None` if it is non-linear
84/// (e.g. `mul` of two non-constants). Numeric constants are literals; other names
85/// are variables; `add`/`sub`/`mul` build the form.
86pub fn parse_lin(t: &ProofTerm) -> Option<LinExpr> {
87    match t {
88        ProofTerm::Constant(s) => Some(match s.parse::<i64>() {
89            Ok(n) => LinExpr::constant(n),
90            Err(_) => LinExpr::var(s),
91        }),
92        ProofTerm::Variable(s) | ProofTerm::BoundVarRef(s) => Some(LinExpr::var(s)),
93        ProofTerm::Function(name, args) => match (name.as_str(), args.as_slice()) {
94            ("add", [a, b]) => Some(parse_lin(a)?.add(&parse_lin(b)?)),
95            ("sub", [a, b]) => Some(parse_lin(a)?.sub(&parse_lin(b)?)),
96            ("mul", [a, b]) => {
97                let (la, lb) = (parse_lin(a)?, parse_lin(b)?);
98                if la.is_constant() {
99                    Some(lb.scale(la.constant))
100                } else if lb.is_constant() {
101                    Some(la.scale(lb.constant))
102                } else {
103                    None
104                }
105            }
106            _ => None,
107        },
108        ProofTerm::Group(_) => None,
109    }
110}
111
112/// A row of the elimination: the constraint `e ≤ 0`, tagged with the non-negative
113/// combination `prov` (original-constraint index → multiplier) that produced it.
114#[derive(Clone, Debug)]
115struct Row {
116    e: LinExpr,
117    prov: BTreeMap<usize, i64>,
118}
119
120fn combine_prov(
121    a: &BTreeMap<usize, i64>,
122    ka: i64,
123    b: &BTreeMap<usize, i64>,
124    kb: i64,
125) -> BTreeMap<usize, i64> {
126    let mut out = BTreeMap::new();
127    for (i, v) in a {
128        *out.entry(*i).or_insert(0) += v * ka;
129    }
130    for (i, v) in b {
131        *out.entry(*i).or_insert(0) += v * kb;
132    }
133    out.retain(|_, v| *v != 0);
134    out
135}
136
137/// Given constraints `cᵢ ≤ 0`, find a non-negative integer combination
138/// `Σ λᵢ·cᵢ = (positive constant) ≤ 0` — a Farkas refutation. Returns the
139/// multipliers `λᵢ`, or `None` if the system is satisfiable over ℚ (so no rational
140/// Farkas certificate exists).
141pub fn find_farkas(constraints: &[LinExpr]) -> Option<BTreeMap<usize, i64>> {
142    let mut rows: Vec<Row> = constraints
143        .iter()
144        .enumerate()
145        .map(|(i, e)| Row {
146            e: e.clone(),
147            prov: BTreeMap::from([(i, 1)]),
148        })
149        .collect();
150
151    let contradiction = |rows: &[Row]| -> Option<BTreeMap<usize, i64>> {
152        rows.iter()
153            .find(|r| r.e.is_constant() && r.e.constant > 0)
154            .map(|r| r.prov.clone())
155    };
156    if let Some(p) = contradiction(&rows) {
157        return Some(p);
158    }
159
160    // Eliminate variables one at a time (Fourier-Motzkin).
161    let mut vars: Vec<String> = rows
162        .iter()
163        .flat_map(|r| r.e.coeffs.keys().cloned())
164        .collect();
165    vars.sort();
166    vars.dedup();
167
168    for v in vars {
169        let (mut pos, mut neg, mut zero) = (Vec::new(), Vec::new(), Vec::new());
170        for r in rows {
171            match r.e.coeff(&v) {
172                c if c > 0 => pos.push(r),
173                c if c < 0 => neg.push(r),
174                _ => zero.push(r),
175            }
176        }
177        let mut next = zero;
178        for p in &pos {
179            for n in &neg {
180                let (pc, nc) = (p.e.coeff(&v), -n.e.coeff(&v)); // both > 0
181                                                                // nc·p + pc·n  cancels v (coeff: nc·pc + pc·(-nc) = 0).
182                next.push(Row {
183                    e: p.e.scale(nc).add(&n.e.scale(pc)),
184                    prov: combine_prov(&p.prov, nc, &n.prov, pc),
185                });
186            }
187        }
188        rows = next;
189        if let Some(p) = contradiction(&rows) {
190            return Some(p);
191        }
192    }
193    contradiction(&rows)
194}
195
196/// `Σ multipliers[i]·constraints[i]`. For a valid Farkas certificate this is a
197/// bare positive constant (the variables cancel) — that constant is the `d` in the
198/// reconstructed contradiction `0 ≤ -d`.
199pub fn combine(constraints: &[LinExpr], multipliers: &BTreeMap<usize, i64>) -> LinExpr {
200    let mut acc = LinExpr::constant(0);
201    for (&i, &m) in multipliers {
202        acc = acc.add(&constraints[i].scale(m));
203    }
204    acc
205}
206
207#[cfg(test)]
208#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/linarith_solve/tests.rs"]
209mod tests;