problemreductions/models/algebraic/
mod.rs

1//! Algebraic problems.
2//!
3//! Problems whose input is a matrix, linear system, or lattice:
4//! - [`AlgebraicEquationsOverGF2`]: Multilinear polynomial equations over GF(2)
5//! - [`QUBO`]: Quadratic Unconstrained Binary Optimization
6//! - [`ILP`]: Integer Linear Programming
7//! - [`ClosestVectorProblem`]: Closest Vector Problem (minimize lattice distance)
8//! - [`BMF`]: Boolean Matrix Factorization
9//! - [`ConsecutiveBlockMinimization`]: Consecutive Block Minimization
10//! - [`ConsecutiveOnesSubmatrix`]: Consecutive Ones Submatrix (column selection with C1P)
11//! - [`EquilibriumPoint`]: Pure-strategy Nash Equilibrium existence
12//! - [`QuadraticAssignment`]: Quadratic Assignment Problem
13//! - [`QuadraticCongruences`]: Decide x² ≡ a (mod b) for x in {1, ..., c-1}
14//! - [`QuadraticDiophantineEquations`]: Decide ax² + by = c in positive integers
15//! - [`SimultaneousIncongruences`]: Decide whether x ≢ aᵢ (mod bᵢ) for all i simultaneously
16//! - [`MinimumMatrixDomination`]: Minimum Matrix Domination (minimum dominating set of 1-entries)
17//! - [`MinimumWeightDecoding`]: Minimum Weight Decoding (minimize Hamming weight of Hx≡s mod 2)
18//! - [`MinimumWeightSolutionToLinearEquations`]: Minimum Weight Solution to Linear Equations (minimize Hamming weight of Ay=b solution)
19//! - [`SparseMatrixCompression`]: Sparse Matrix Compression by row overlay
20
21pub(crate) mod algebraic_equations_over_gf2;
22pub(crate) mod bmf;
23pub(crate) mod closest_vector_problem;
24pub(crate) mod consecutive_block_minimization;
25pub(crate) mod consecutive_ones_matrix_augmentation;
26pub(crate) mod consecutive_ones_submatrix;
27pub(crate) mod equilibrium_point;
28pub(crate) mod feasible_basis_extension;
29pub(crate) mod ilp;
30pub(crate) mod minimum_matrix_cover;
31pub(crate) mod minimum_matrix_domination;
32pub(crate) mod minimum_weight_decoding;
33pub(crate) mod minimum_weight_solution_to_linear_equations;
34pub(crate) mod quadratic_assignment;
35pub(crate) mod quadratic_congruences;
36pub(crate) mod quadratic_diophantine_equations;
37pub(crate) mod qubo;
38pub(crate) mod simultaneous_incongruences;
39pub(crate) mod sparse_matrix_compression;
40
41pub use algebraic_equations_over_gf2::AlgebraicEquationsOverGF2;
42pub use bmf::BMF;
43pub use closest_vector_problem::{ClosestVectorProblem, VarBounds};
44pub use consecutive_block_minimization::ConsecutiveBlockMinimization;
45pub use consecutive_ones_matrix_augmentation::ConsecutiveOnesMatrixAugmentation;
46pub use consecutive_ones_submatrix::ConsecutiveOnesSubmatrix;
47pub use equilibrium_point::EquilibriumPoint;
48pub use feasible_basis_extension::FeasibleBasisExtension;
49pub use ilp::{Comparison, LinearConstraint, ObjectiveSense, VariableDomain, ILP};
50pub use minimum_matrix_cover::MinimumMatrixCover;
51pub use minimum_matrix_domination::MinimumMatrixDomination;
52pub use minimum_weight_decoding::MinimumWeightDecoding;
53pub use minimum_weight_solution_to_linear_equations::MinimumWeightSolutionToLinearEquations;
54pub use quadratic_assignment::QuadraticAssignment;
55pub use quadratic_congruences::QuadraticCongruences;
56pub use quadratic_diophantine_equations::QuadraticDiophantineEquations;
57pub use qubo::QUBO;
58pub use simultaneous_incongruences::SimultaneousIncongruences;
59pub use sparse_matrix_compression::SparseMatrixCompression;
60
61#[cfg(feature = "example-db")]
62pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
63    let mut specs = Vec::new();
64    specs.extend(algebraic_equations_over_gf2::canonical_model_example_specs());
65    specs.extend(qubo::canonical_model_example_specs());
66    specs.extend(ilp::canonical_model_example_specs());
67    specs.extend(closest_vector_problem::canonical_model_example_specs());
68    specs.extend(bmf::canonical_model_example_specs());
69    specs.extend(consecutive_block_minimization::canonical_model_example_specs());
70    specs.extend(consecutive_ones_matrix_augmentation::canonical_model_example_specs());
71    specs.extend(consecutive_ones_submatrix::canonical_model_example_specs());
72    specs.extend(feasible_basis_extension::canonical_model_example_specs());
73    specs.extend(minimum_matrix_cover::canonical_model_example_specs());
74    specs.extend(minimum_matrix_domination::canonical_model_example_specs());
75    specs.extend(minimum_weight_decoding::canonical_model_example_specs());
76    specs.extend(minimum_weight_solution_to_linear_equations::canonical_model_example_specs());
77    specs.extend(quadratic_assignment::canonical_model_example_specs());
78    specs.extend(quadratic_congruences::canonical_model_example_specs());
79    specs.extend(quadratic_diophantine_equations::canonical_model_example_specs());
80    specs.extend(equilibrium_point::canonical_model_example_specs());
81    specs.extend(simultaneous_incongruences::canonical_model_example_specs());
82    specs.extend(sparse_matrix_compression::canonical_model_example_specs());
83    specs
84}
problemreductions/models/algebraic/mod.rs

problemreductions/models/algebraic/
mod.rs
