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;