Skip to main content

logicaffeine_proof/
optimize.rs

1//! Certified SAT-based optimization. We have no native MaxSAT/ILP solver, so we minimise an
2//! integer cost the honest way: binary-search the smallest feasible cost bound, where each query
3//! is a certified decision (`prove_unsat` → `Sat` witness or RUP-`Refuted`). The result is a
4//! **certified optimum** — a witness at the optimum and a refutation at optimum−1 — not merely a
5//! value we happened to find.
6//!
7//! `feasible_at(bound)` must be MONOTONE: feasible at `b` ⇒ feasible at `b+1` (e.g. "cost ≤ b" via
8//! [`crate::cardinality::at_most`]).
9
10use crate::sat::{prove_unsat, UnsatOutcome};
11use crate::ProofExpr;
12
13/// The outcome of a certified minimization.
14#[derive(Clone, Debug, PartialEq)]
15pub struct MinResult {
16    /// The smallest feasible cost bound.
17    pub optimum: i64,
18    /// A satisfying assignment at the optimum (atom → value).
19    pub witness: Vec<(String, bool)>,
20    /// `true` when `optimum-1` was RUP-`Refuted` (so the optimum is provably minimal), or when the
21    /// optimum equals the search floor.
22    pub minimal_certified: bool,
23}
24
25/// Binary-search `[lo, hi]` for the least `bound` with `feasible_at(bound)` satisfiable.
26/// Returns `None` if even `hi` is infeasible or a query leaves the supported fragment.
27pub fn minimize_certified(
28    feasible_at: impl Fn(i64) -> ProofExpr,
29    lo: i64,
30    hi: i64,
31) -> Option<MinResult> {
32    if lo > hi {
33        return None;
34    }
35    // The top of the range must be feasible, else there is no solution at all.
36    if !matches!(prove_unsat(&feasible_at(hi)), UnsatOutcome::Sat(_)) {
37        return None;
38    }
39    let mut l = lo;
40    let mut h = hi;
41    while l < h {
42        let mid = l + (h - l) / 2;
43        match prove_unsat(&feasible_at(mid)) {
44            UnsatOutcome::Sat(_) => h = mid,
45            UnsatOutcome::Refuted => l = mid + 1,
46            UnsatOutcome::Unsupported => return None,
47        }
48    }
49    let optimum = l;
50    let witness = match prove_unsat(&feasible_at(optimum)) {
51        UnsatOutcome::Sat(m) => m,
52        _ => return None,
53    };
54    let minimal_certified = optimum <= lo
55        || matches!(
56            prove_unsat(&feasible_at(optimum - 1)),
57            UnsatOutcome::Refuted
58        );
59    Some(MinResult {
60        optimum,
61        witness,
62        minimal_certified,
63    })
64}
65
66#[cfg(test)]
67#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/optimize/tests.rs"]
68mod tests;