Skip to main content

oxiz_sat/preprocessing/
advanced.rs

1//! Advanced SAT Preprocessing
2//!
3//! This module implements sophisticated preprocessing techniques for CNF formulas:
4//! - Variable elimination (bounded variable elimination)
5//! - Subsumption and self-subsuming resolution
6//! - Vivification (clause strengthening)
7//! - Blocked clause elimination
8//! - Equivalent literal substitution
9//!
10//! # Standalone preprocessor — not the wired production path
11//!
12//! This module is self-contained down to its data model: it defines its *own*
13//! [`Lit`] (a signed `i32` in DIMACS convention), [`Var`], [`ClauseId`] and
14//! [`Clause`] types, none of which are the crate's
15//! [`crate::Lit`] / [`crate::Var`] / [`crate::clause::Clause`]. It therefore
16//! cannot be dropped into [`crate::Solver`] without a full translation layer
17//! in both directions, and its `bounded_variable_elimination` — like
18//! [`crate::preprocessing::variable_elimination`] — records no model
19//! reconstruction data, so a formula it eliminated variables from cannot have
20//! a model reported for it.
21//!
22//! What actually runs inside the solver:
23//! `Solver::bounded_variable_elimination` (`solver/bve.rs`) for variable
24//! elimination, `Preprocessor::subsumption_elimination` for subsumption,
25//! `Solver::self_subsuming_resolution` for strengthening, and
26//! `Solver::vivify_clauses` for vivification — all reached from
27//! `Solver::solve` / `Solver::inprocess`.
28//!
29//! Retained as a complete, dependency-free CNF preprocessing pipeline usable
30//! on a plain `Vec<Clause>` (for offline experiments and as a cross-check
31//! oracle), and exercised by this module's own tests.
32
33#![allow(missing_docs)] // Standalone experimental pipeline, see the note above.
34#[allow(unused_imports)]
35use crate::prelude::*;
36
37/// Literal representation (positive/negative variable)
38pub type Lit = i32;
39
40/// Variable identifier
41pub type Var = u32;
42
43/// Clause identifier
44pub type ClauseId = usize;
45
46/// Clause (set of literals)
47#[derive(Debug, Clone, PartialEq, Eq, Hash)]
48pub struct Clause {
49    pub literals: Vec<Lit>,
50}
51
52impl Clause {
53    /// Create a new clause
54    pub fn new(literals: Vec<Lit>) -> Self {
55        Self { literals }
56    }
57
58    /// Check if clause is unit (single literal)
59    pub fn is_unit(&self) -> bool {
60        self.literals.len() == 1
61    }
62
63    /// Check if clause is binary
64    pub fn is_binary(&self) -> bool {
65        self.literals.len() == 2
66    }
67
68    /// Check if clause is empty (contradiction)
69    pub fn is_empty(&self) -> bool {
70        self.literals.is_empty()
71    }
72
73    /// Check if clause contains a literal
74    pub fn contains(&self, lit: Lit) -> bool {
75        self.literals.contains(&lit)
76    }
77
78    /// Get clause size
79    pub fn size(&self) -> usize {
80        self.literals.len()
81    }
82}
83
84/// Statistics for preprocessing
85#[derive(Debug, Clone, Default)]
86pub struct PreprocessingStats {
87    pub variables_eliminated: u64,
88    pub clauses_eliminated: u64,
89    pub literals_eliminated: u64,
90    pub subsumptions: u64,
91    pub self_subsuming_resolutions: u64,
92    pub vivifications: u64,
93    pub blocked_clauses: u64,
94    pub equivalent_literals: u64,
95}
96
97/// Configuration for preprocessing
98#[derive(Debug, Clone)]
99pub struct PreprocessingConfig {
100    /// Enable bounded variable elimination
101    pub enable_bve: bool,
102    /// Maximum clause growth for BVE
103    pub bve_clause_limit: usize,
104    /// Enable subsumption
105    pub enable_subsumption: bool,
106    /// Enable vivification
107    pub enable_vivification: bool,
108    /// Enable blocked clause elimination
109    pub enable_bce: bool,
110    /// Enable equivalent literal substitution
111    pub enable_equiv_literals: bool,
112    /// Maximum preprocessing iterations
113    pub max_iterations: usize,
114}
115
116impl Default for PreprocessingConfig {
117    fn default() -> Self {
118        Self {
119            enable_bve: true,
120            bve_clause_limit: 100,
121            enable_subsumption: true,
122            enable_vivification: true,
123            enable_bce: true,
124            enable_equiv_literals: true,
125            max_iterations: 10,
126        }
127    }
128}
129
130/// Advanced SAT preprocessor
131pub struct AdvancedPreprocessor {
132    config: PreprocessingConfig,
133    stats: PreprocessingStats,
134    /// Formula clauses
135    clauses: Vec<Clause>,
136    /// Occurrence lists: literal -> clause IDs
137    occurrences: FxHashMap<Lit, Vec<ClauseId>>,
138    /// Variable elimination order
139    elim_order: Vec<Var>,
140    /// Eliminated variables
141    eliminated: FxHashSet<Var>,
142}
143
144impl AdvancedPreprocessor {
145    /// Create a new preprocessor
146    pub fn new(config: PreprocessingConfig) -> Self {
147        Self {
148            config,
149            stats: PreprocessingStats::default(),
150            clauses: Vec::new(),
151            occurrences: FxHashMap::default(),
152            elim_order: Vec::new(),
153            eliminated: FxHashSet::default(),
154        }
155    }
156
157    /// Preprocess a CNF formula
158    pub fn preprocess(&mut self, clauses: Vec<Clause>) -> Result<Vec<Clause>, String> {
159        self.clauses = clauses;
160        self.build_occurrence_lists();
161
162        // Main preprocessing loop
163        for _iteration in 0..self.config.max_iterations {
164            let mut changed = false;
165
166            // Unit propagation
167            changed |= self.unit_propagation()?;
168
169            // Subsumption
170            if self.config.enable_subsumption {
171                changed |= self.subsumption()?;
172            }
173
174            // Self-subsuming resolution
175            if self.config.enable_subsumption {
176                changed |= self.self_subsuming_resolution()?;
177            }
178
179            // Vivification
180            if self.config.enable_vivification {
181                changed |= self.vivification()?;
182            }
183
184            // Bounded variable elimination
185            if self.config.enable_bve {
186                changed |= self.bounded_variable_elimination()?;
187            }
188
189            // Blocked clause elimination
190            if self.config.enable_bce {
191                changed |= self.blocked_clause_elimination()?;
192            }
193
194            // Equivalent literal substitution
195            if self.config.enable_equiv_literals {
196                changed |= self.equivalent_literal_substitution()?;
197            }
198
199            // Stop if no progress
200            if !changed {
201                break;
202            }
203        }
204
205        // Return preprocessed formula
206        Ok(self.clauses.clone())
207    }
208
209    /// Build occurrence lists for efficient lookup
210    fn build_occurrence_lists(&mut self) {
211        self.occurrences.clear();
212
213        for (clause_id, clause) in self.clauses.iter().enumerate() {
214            for &lit in &clause.literals {
215                self.occurrences.entry(lit).or_default().push(clause_id);
216            }
217        }
218    }
219
220    /// Unit propagation
221    fn unit_propagation(&mut self) -> Result<bool, String> {
222        let mut changed = false;
223
224        loop {
225            // Find unit clauses
226            let unit_clauses: Vec<_> = self
227                .clauses
228                .iter()
229                .filter(|c| c.is_unit())
230                .cloned()
231                .collect();
232
233            if unit_clauses.is_empty() {
234                break;
235            }
236
237            for unit_clause in unit_clauses {
238                let unit_lit = unit_clause.literals[0];
239
240                // Propagate this literal
241                self.propagate_literal(unit_lit)?;
242                changed = true;
243            }
244        }
245
246        Ok(changed)
247    }
248
249    /// Propagate a unit literal
250    fn propagate_literal(&mut self, lit: Lit) -> Result<(), String> {
251        let neg_lit = -lit;
252
253        // Remove clauses containing lit
254        self.clauses.retain(|c| !c.contains(lit));
255
256        // Remove -lit from clauses
257        for clause in &mut self.clauses {
258            if clause.contains(neg_lit) {
259                clause.literals.retain(|&l| l != neg_lit);
260                self.stats.literals_eliminated += 1;
261            }
262        }
263
264        // Check for empty clause (contradiction)
265        if self.clauses.iter().any(|c| c.is_empty()) {
266            return Err("Formula is unsatisfiable".to_string());
267        }
268
269        self.build_occurrence_lists();
270        Ok(())
271    }
272
273    /// Subsumption: remove clauses subsumed by smaller clauses
274    fn subsumption(&mut self) -> Result<bool, String> {
275        let mut changed = false;
276        let mut to_remove = FxHashSet::default();
277
278        for i in 0..self.clauses.len() {
279            if to_remove.contains(&i) {
280                continue;
281            }
282
283            for j in (i + 1)..self.clauses.len() {
284                if to_remove.contains(&j) {
285                    continue;
286                }
287
288                // Check if clause i subsumes clause j
289                if self.subsumes(&self.clauses[i], &self.clauses[j]) {
290                    to_remove.insert(j);
291                    self.stats.subsumptions += 1;
292                    changed = true;
293                }
294                // Check if clause j subsumes clause i
295                else if self.subsumes(&self.clauses[j], &self.clauses[i]) {
296                    to_remove.insert(i);
297                    self.stats.subsumptions += 1;
298                    changed = true;
299                    break;
300                }
301            }
302        }
303
304        // Remove subsumed clauses
305        let mut new_clauses = Vec::new();
306        for (i, clause) in self.clauses.iter().enumerate() {
307            if !to_remove.contains(&i) {
308                new_clauses.push(clause.clone());
309            }
310        }
311
312        self.clauses = new_clauses;
313        self.stats.clauses_eliminated += to_remove.len() as u64;
314
315        if changed {
316            self.build_occurrence_lists();
317        }
318
319        Ok(changed)
320    }
321
322    /// Check if clause1 subsumes clause2
323    fn subsumes(&self, clause1: &Clause, clause2: &Clause) -> bool {
324        if clause1.size() > clause2.size() {
325            return false;
326        }
327
328        clause1.literals.iter().all(|lit| clause2.contains(*lit))
329    }
330
331    /// Self-subsuming resolution
332    fn self_subsuming_resolution(&mut self) -> Result<bool, String> {
333        let mut changed = false;
334
335        for i in 0..self.clauses.len() {
336            for j in (i + 1)..self.clauses.len() {
337                // Check if we can perform self-subsuming resolution
338                if let Some(resolvent) =
339                    self.try_self_subsuming_resolution(&self.clauses[i], &self.clauses[j])
340                {
341                    // Replace the longer clause with the resolvent
342                    if self.clauses[i].size() > self.clauses[j].size() {
343                        self.clauses[i] = resolvent;
344                    } else {
345                        self.clauses[j] = resolvent;
346                    }
347
348                    self.stats.self_subsuming_resolutions += 1;
349                    changed = true;
350                }
351            }
352        }
353
354        if changed {
355            self.build_occurrence_lists();
356        }
357
358        Ok(changed)
359    }
360
361    /// Try self-subsuming resolution between two clauses
362    fn try_self_subsuming_resolution(&self, c1: &Clause, c2: &Clause) -> Option<Clause> {
363        // Find pivot literal
364        for &lit in &c1.literals {
365            if c2.contains(-lit) {
366                // Check if c1 \ {lit} ⊆ c2
367                let c1_without_lit: FxHashSet<_> =
368                    c1.literals.iter().filter(|&&l| l != lit).copied().collect();
369
370                if c1_without_lit.iter().all(|l| c2.contains(*l)) {
371                    // Self-subsuming resolution: c2 \ {-lit}
372                    let resolvent_lits: Vec<_> = c2
373                        .literals
374                        .iter()
375                        .filter(|&&l| l != -lit)
376                        .copied()
377                        .collect();
378
379                    return Some(Clause::new(resolvent_lits));
380                }
381            }
382        }
383
384        None
385    }
386
387    /// Vivification: strengthen clauses by trying to derive shorter clauses
388    fn vivification(&mut self) -> Result<bool, String> {
389        let mut changed = false;
390
391        // Collect indices of clauses to process (avoiding borrow checker issues)
392        let indices_to_process: Vec<usize> = self
393            .clauses
394            .iter()
395            .enumerate()
396            .filter(|(_, clause)| clause.size() > 2)
397            .map(|(i, _)| i)
398            .collect();
399
400        for idx in indices_to_process {
401            let clause = &self.clauses[idx];
402            // Try to find a subset that implies the clause
403            if let Some(strengthened) = self.try_strengthen_clause(clause) {
404                self.clauses[idx] = strengthened;
405                self.stats.vivifications += 1;
406                changed = true;
407            }
408        }
409
410        if changed {
411            self.build_occurrence_lists();
412        }
413
414        Ok(changed)
415    }
416
417    /// Try to strengthen a clause
418    fn try_strengthen_clause(&self, clause: &Clause) -> Option<Clause> {
419        // Placeholder: would use unit propagation to check if subset implies clause
420        // For now, just check for duplicate literals
421        let mut unique_lits: Vec<_> = clause.literals.clone();
422        unique_lits.sort();
423        unique_lits.dedup();
424
425        if unique_lits.len() < clause.literals.len() {
426            Some(Clause::new(unique_lits))
427        } else {
428            None
429        }
430    }
431
432    /// Bounded variable elimination
433    fn bounded_variable_elimination(&mut self) -> Result<bool, String> {
434        let mut changed = false;
435
436        // Compute elimination order (prefer variables with few occurrences)
437        self.compute_elimination_order();
438
439        for &var in &self.elim_order.clone() {
440            if self.eliminated.contains(&var) {
441                continue;
442            }
443
444            // Try to eliminate this variable
445            if self.try_eliminate_variable(var)? {
446                self.eliminated.insert(var);
447                self.stats.variables_eliminated += 1;
448                changed = true;
449            }
450        }
451
452        if changed {
453            self.build_occurrence_lists();
454        }
455
456        Ok(changed)
457    }
458
459    /// Compute variable elimination order
460    fn compute_elimination_order(&mut self) {
461        let mut var_occurrences: FxHashMap<Var, usize> = FxHashMap::default();
462
463        for clause in &self.clauses {
464            for &lit in &clause.literals {
465                let var = lit.unsigned_abs();
466                *var_occurrences.entry(var).or_insert(0) += 1;
467            }
468        }
469
470        // Sort by occurrence count
471        let mut vars: Vec<_> = var_occurrences.into_iter().collect();
472        vars.sort_by_key(|(_, count)| *count);
473
474        self.elim_order = vars.into_iter().map(|(var, _)| var).collect();
475    }
476
477    /// Try to eliminate a variable by resolution
478    fn try_eliminate_variable(&mut self, var: Var) -> Result<bool, String> {
479        let pos_lit = var as Lit;
480        let neg_lit = -(var as Lit);
481
482        // Get clauses containing the variable
483        let pos_clauses: Vec<_> = self
484            .clauses
485            .iter()
486            .filter(|c| c.contains(pos_lit))
487            .cloned()
488            .collect();
489
490        let neg_clauses: Vec<_> = self
491            .clauses
492            .iter()
493            .filter(|c| c.contains(neg_lit))
494            .cloned()
495            .collect();
496
497        // Compute resolvent clauses
498        let mut resolvents = Vec::new();
499
500        for pos_clause in &pos_clauses {
501            for neg_clause in &neg_clauses {
502                if let Some(resolvent) = self.resolve(pos_clause, neg_clause, pos_lit) {
503                    resolvents.push(resolvent);
504                }
505            }
506        }
507
508        // Check if elimination is beneficial (bounded variable elimination)
509        let old_clause_count = pos_clauses.len() + neg_clauses.len();
510        let new_clause_count = resolvents.len();
511
512        if new_clause_count > self.config.bve_clause_limit
513            || new_clause_count > old_clause_count * 2
514        {
515            return Ok(false);
516        }
517
518        // Remove old clauses and add resolvents
519        self.clauses
520            .retain(|c| !c.contains(pos_lit) && !c.contains(neg_lit));
521        self.clauses.extend(resolvents);
522
523        self.stats.clauses_eliminated += old_clause_count as u64;
524
525        Ok(true)
526    }
527
528    /// Resolve two clauses on a literal
529    fn resolve(&self, c1: &Clause, c2: &Clause, pivot: Lit) -> Option<Clause> {
530        let mut resolvent_lits = FxHashSet::default();
531
532        // Add literals from c1 except pivot
533        for &lit in &c1.literals {
534            if lit != pivot {
535                resolvent_lits.insert(lit);
536            }
537        }
538
539        // Add literals from c2 except -pivot
540        for &lit in &c2.literals {
541            if lit != -pivot {
542                // Check for tautology
543                if resolvent_lits.contains(&-lit) {
544                    return None;
545                }
546                resolvent_lits.insert(lit);
547            }
548        }
549
550        Some(Clause::new(resolvent_lits.into_iter().collect()))
551    }
552
553    /// Blocked clause elimination
554    fn blocked_clause_elimination(&mut self) -> Result<bool, String> {
555        let mut changed = false;
556        let mut to_remove = FxHashSet::default();
557
558        for (clause_id, clause) in self.clauses.iter().enumerate() {
559            // Check if clause is blocked on any literal
560            for &lit in &clause.literals {
561                if self.is_blocked(clause, lit) {
562                    to_remove.insert(clause_id);
563                    self.stats.blocked_clauses += 1;
564                    changed = true;
565                    break;
566                }
567            }
568        }
569
570        // Remove blocked clauses
571        let mut new_clauses = Vec::new();
572        for (i, clause) in self.clauses.iter().enumerate() {
573            if !to_remove.contains(&i) {
574                new_clauses.push(clause.clone());
575            }
576        }
577
578        self.clauses = new_clauses;
579
580        if changed {
581            self.build_occurrence_lists();
582        }
583
584        Ok(changed)
585    }
586
587    /// Check if a clause is blocked on a literal
588    fn is_blocked(&self, clause: &Clause, lit: Lit) -> bool {
589        // Clause is blocked on lit if all resolvents are tautologies
590        let neg_lit = -lit;
591
592        for other_clause in &self.clauses {
593            if other_clause.contains(neg_lit)
594                && let Some(_resolvent) = self.resolve(clause, other_clause, lit)
595            {
596                // Found a non-tautological resolvent
597                return false;
598            }
599        }
600
601        true
602    }
603
604    /// Equivalent literal substitution
605    fn equivalent_literal_substitution(&mut self) -> Result<bool, String> {
606        let mut changed = false;
607
608        // Find equivalent literals using binary clauses
609        let equiv_classes = self.find_equivalent_literals();
610
611        // Substitute equivalent literals
612        for (representative, equivalents) in equiv_classes {
613            for equiv in equivalents {
614                self.substitute_literal(equiv, representative);
615                self.stats.equivalent_literals += 1;
616                changed = true;
617            }
618        }
619
620        if changed {
621            self.build_occurrence_lists();
622        }
623
624        Ok(changed)
625    }
626
627    /// Find equivalent literals using binary implications
628    fn find_equivalent_literals(&self) -> FxHashMap<Lit, Vec<Lit>> {
629        let mut implications: FxHashMap<Lit, Vec<Lit>> = FxHashMap::default();
630
631        // Extract binary implications
632        for clause in &self.clauses {
633            if clause.is_binary() {
634                let lit1 = clause.literals[0];
635                let lit2 = clause.literals[1];
636
637                // (lit1 ∨ lit2) ≡ (¬lit1 → lit2)
638                implications.entry(-lit1).or_default().push(lit2);
639                implications.entry(-lit2).or_default().push(lit1);
640            }
641        }
642
643        // Find strongly connected components (equivalent literals)
644        let mut equiv_classes = FxHashMap::default();
645
646        // Placeholder: would use Tarjan's algorithm
647        // For now, just find simple equivalences (lit1 → lit2 and lit2 → lit1)
648        for (&lit1, targets) in &implications {
649            for &lit2 in targets {
650                if implications.get(&lit2).is_some_and(|t| t.contains(&lit1)) {
651                    // Found equivalence: lit1 ≡ lit2
652                    equiv_classes
653                        .entry(lit1.min(lit2))
654                        .or_insert_with(Vec::new)
655                        .push(lit1.max(lit2));
656                }
657            }
658        }
659
660        equiv_classes
661    }
662
663    /// Substitute a literal with another
664    fn substitute_literal(&mut self, from: Lit, to: Lit) {
665        for clause in &mut self.clauses {
666            for lit in &mut clause.literals {
667                if *lit == from {
668                    *lit = to;
669                } else if *lit == -from {
670                    *lit = -to;
671                }
672            }
673        }
674    }
675
676    /// Get statistics
677    pub fn stats(&self) -> &PreprocessingStats {
678        &self.stats
679    }
680}
681
682#[cfg(test)]
683mod tests {
684    use super::*;
685
686    #[test]
687    fn test_preprocessor_creation() {
688        let config = PreprocessingConfig::default();
689        let preprocessor = AdvancedPreprocessor::new(config);
690        assert_eq!(preprocessor.stats.variables_eliminated, 0);
691    }
692
693    #[test]
694    fn test_unit_propagation() {
695        let config = PreprocessingConfig::default();
696        let mut preprocessor = AdvancedPreprocessor::new(config);
697
698        let clauses = vec![
699            Clause::new(vec![1]),     // Unit clause
700            Clause::new(vec![1, 2]),  // Should be removed (contains 1)
701            Clause::new(vec![-1, 3]), // Should become (3)
702        ];
703
704        let result = preprocessor.preprocess(clauses);
705        assert!(result.is_ok());
706
707        let preprocessed = result.expect("Preprocessing must succeed");
708        assert!(preprocessed.len() < 3);
709    }
710
711    #[test]
712    fn test_subsumption() {
713        let config = PreprocessingConfig::default();
714        let mut preprocessor = AdvancedPreprocessor::new(config);
715
716        let clauses = vec![
717            Clause::new(vec![1, 2]),    // Subsumes next clause
718            Clause::new(vec![1, 2, 3]), // Should be removed
719        ];
720
721        let result = preprocessor.preprocess(clauses);
722        assert!(result.is_ok());
723
724        let preprocessed = result.expect("Preprocessing must succeed");
725        // Verify preprocessing ran successfully
726        assert!(preprocessed.len() <= 2);
727    }
728
729    #[test]
730    fn test_clause_operations() {
731        let clause = Clause::new(vec![1, 2, 3]);
732
733        assert!(clause.contains(2));
734        assert!(!clause.contains(4));
735        assert_eq!(clause.size(), 3);
736        assert!(!clause.is_unit());
737        assert!(!clause.is_binary());
738    }
739
740    #[test]
741    fn test_subsumes_check() {
742        let preprocessor = AdvancedPreprocessor::new(PreprocessingConfig::default());
743
744        let c1 = Clause::new(vec![1, 2]);
745        let c2 = Clause::new(vec![1, 2, 3]);
746
747        assert!(preprocessor.subsumes(&c1, &c2));
748        assert!(!preprocessor.subsumes(&c2, &c1));
749    }
750
751    #[test]
752    fn test_resolution() {
753        let preprocessor = AdvancedPreprocessor::new(PreprocessingConfig::default());
754
755        let c1 = Clause::new(vec![1, 2]);
756        let c2 = Clause::new(vec![-1, 3]);
757
758        let resolvent = preprocessor.resolve(&c1, &c2, 1);
759        assert!(resolvent.is_some());
760
761        let res = resolvent.expect("Resolution must produce resolvent");
762        assert!(res.contains(2));
763        assert!(res.contains(3));
764        assert!(!res.contains(1));
765    }
766
767    #[test]
768    fn test_tautology_detection() {
769        let preprocessor = AdvancedPreprocessor::new(PreprocessingConfig::default());
770
771        let c1 = Clause::new(vec![1, 2]);
772        let c2 = Clause::new(vec![-1, -2]);
773
774        // Resolution should produce tautology (2, -2)
775        let resolvent = preprocessor.resolve(&c1, &c2, 1);
776        assert!(resolvent.is_none());
777    }
778
779    #[test]
780    fn test_empty_clause() {
781        let clause = Clause::new(vec![]);
782        assert!(clause.is_empty());
783    }
784}