problemreductions/models/algebraic/
minimum_weight_solution_to_linear_equations.rs

1//! Minimum Weight Solution to Linear Equations problem implementation.
2//!
3//! Given an n×m integer matrix A and integer vector b, find a rational vector y
4//! with Ay = b that minimizes the number of non-zero entries (Hamming weight).
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "MinimumWeightSolutionToLinearEquations",
14        display_name: "Minimum Weight Solution to Linear Equations",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Find a rational solution to Ay=b minimizing the number of non-zero entries",
20        fields: MinimumWeightSolutionCreateSpec::FIELDS,
21    }
22}
23
24/// Minimum Weight Solution to Linear Equations.
25///
26/// Given an n×m integer matrix A and an integer vector b, find a rational
27/// vector y with Ay = b that minimizes ||y||_0 (the number of non-zero
28/// entries, i.e., the Hamming weight of y).
29///
30/// # Representation
31///
32/// Each of the m columns is a binary variable: `x_j = 1` means column j is
33/// selected (i.e., y_j may be non-zero). The evaluator checks whether the
34/// restricted system (using only selected columns) is consistent over the
35/// rationals, and returns the count of selected columns if so.
36///
37/// # Example
38///
39/// ```
40/// use problemreductions::models::algebraic::MinimumWeightSolutionToLinearEquations;
41/// use problemreductions::{Problem, BruteForce};
42///
43/// let matrix = vec![
44///     vec![1, 2, 3, 1],
45///     vec![2, 1, 1, 3],
46/// ];
47/// let rhs = vec![5, 4];
48/// let problem = MinimumWeightSolutionToLinearEquations::new(matrix, rhs);
49/// let solver = BruteForce::new();
50/// let witness = solver.solve(&problem).unwrap();
51/// assert!(witness.is_some());
52/// ```
53#[derive(Debug, Clone, Serialize, Deserialize)]
54#[serde(try_from = "MinimumWeightSolutionCreateSpec")]
55pub struct MinimumWeightSolutionToLinearEquations {
56    /// The n×m integer matrix A.
57    matrix: Vec<Vec<i64>>,
58    /// The right-hand side vector b of length n.
59    rhs: Vec<i64>,
60}
61
62#[derive(Debug, Deserialize, crate::CreateSpec)]
63struct MinimumWeightSolutionCreateSpec {
64    /// Integer matrix as JSON.
65    #[create(codec = "json")]
66    matrix: Vec<Vec<i64>>,
67    /// Right-hand side vector.
68    #[create(codec = "comma-separated")]
69    rhs: Vec<i64>,
70}
71
72impl TryFrom<MinimumWeightSolutionCreateSpec> for MinimumWeightSolutionToLinearEquations {
73    type Error = crate::registry::ConstructionError;
74
75    fn try_from(spec: MinimumWeightSolutionCreateSpec) -> Result<Self, Self::Error> {
76        Self::try_new(spec.matrix, spec.rhs)
77    }
78}
79
80impl MinimumWeightSolutionToLinearEquations {
81    /// Create a new MinimumWeightSolutionToLinearEquations instance.
82    ///
83    /// # Panics
84    ///
85    /// Panics if the matrix is empty, rows have inconsistent lengths,
86    /// rhs length does not match the number of rows, or there are no columns.
87    pub fn new(matrix: Vec<Vec<i64>>, rhs: Vec<i64>) -> Self {
88        Self::try_new(matrix, rhs).unwrap_or_else(|error| panic!("{error}"))
89    }
90
91    fn try_new(
92        matrix: Vec<Vec<i64>>,
93        rhs: Vec<i64>,
94    ) -> Result<Self, crate::registry::ConstructionError> {
95        let first = matrix.first().ok_or("matrix must have at least one row")?;
96        if first.is_empty() {
97            return Err("matrix must have at least one column".into());
98        }
99        if matrix.iter().any(|row| row.len() != first.len()) {
100            return Err("all matrix rows must have the same length".into());
101        }
102        if rhs.len() != matrix.len() {
103            return Err("RHS length must equal number of rows".into());
104        }
105        Ok(Self { matrix, rhs })
106    }
107
108    /// Returns a reference to the matrix A.
109    pub fn matrix(&self) -> &[Vec<i64>] {
110        &self.matrix
111    }
112
113    /// Returns a reference to the right-hand side vector b.
114    pub fn rhs(&self) -> &[i64] {
115        &self.rhs
116    }
117
118    /// Returns the number of equations (rows of A).
119    pub fn num_equations(&self) -> usize {
120        self.matrix.len()
121    }
122
123    /// Returns the number of variables (columns of A).
124    pub fn num_variables(&self) -> usize {
125        self.matrix[0].len()
126    }
127
128    /// Check whether the system restricted to the given column indices is
129    /// consistent over the rationals. Uses integer Gaussian elimination on
130    /// the augmented matrix [A'|b] with checked integer arithmetic.
131    fn is_consistent(&self, columns: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
132        let n = self.num_equations();
133        let k = columns.len();
134
135        // Build augmented matrix [A'|b].
136        // Each row has k coefficient columns + 1 rhs column.
137        let mut aug: Vec<Vec<i64>> = (0..n)
138            .map(|i| {
139                let mut row = Vec::with_capacity(k + 1);
140                for &j in columns {
141                    row.push(self.matrix[i][j]);
142                }
143                row.push(self.rhs[i]);
144                row
145            })
146            .collect();
147
148        let mut pivot_row = 0;
149        for col in 0..k {
150            // Find a non-zero entry in column `col` at or below `pivot_row`.
151            let Some(swap_row) = (pivot_row..n).find(|&r| aug[r][col] != 0) else {
152                continue;
153            };
154            aug.swap(pivot_row, swap_row);
155
156            let pivot_val = aug[pivot_row][col];
157            let pivot_row_snapshot = aug[pivot_row].clone();
158            // Eliminate all other rows.
159            for (r, row) in aug.iter_mut().enumerate() {
160                if r == pivot_row {
161                    continue;
162                }
163                let factor = row[col];
164                if factor == 0 {
165                    continue;
166                }
167                // row[r] = pivot_val * row[r] - factor * row[pivot_row]
168                for (cell, &pv) in row.iter_mut().zip(pivot_row_snapshot.iter()) {
169                    let left = pivot_val.checked_mul(*cell).ok_or_else(|| {
170                        crate::traits::EvaluationError::IntegerOverflow(
171                            "multiplying a consistency-elimination row".into(),
172                        )
173                    })?;
174                    let right = factor.checked_mul(pv).ok_or_else(|| {
175                        crate::traits::EvaluationError::IntegerOverflow(
176                            "multiplying a consistency-elimination pivot row".into(),
177                        )
178                    })?;
179                    *cell = left.checked_sub(right).ok_or_else(|| {
180                        crate::traits::EvaluationError::IntegerOverflow(
181                            "subtracting consistency-elimination rows".into(),
182                        )
183                    })?;
184                }
185            }
186            pivot_row += 1;
187        }
188
189        // Check for inconsistency: any row with all-zero coefficients but
190        // non-zero rhs means the system is inconsistent.
191        for row in &aug[pivot_row..n] {
192            if row[k] != 0 {
193                return Ok(false);
194            }
195        }
196        Ok(true)
197    }
198}
199
200impl Problem for MinimumWeightSolutionToLinearEquations {
201    const NAME: &'static str = "MinimumWeightSolutionToLinearEquations";
202    type Solution = Vec<bool>;
203    type Value = Min<i64>;
204
205    crate::problem_parameters![
206        ("num_equations", num_equations),
207        ("num_variables", num_variables),
208    ];
209
210    fn variant() -> Vec<(&'static str, &'static str)> {
211        crate::variant_params![]
212    }
213
214    fn evaluate(
215        &self,
216        config: &Self::Solution,
217    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
218        Ok({
219            if config.len() != self.num_variables() {
220                return Err(crate::traits::EvaluationError::InvalidConfiguration(
221                    "assignment length does not match the equation variables".into(),
222                ));
223            }
224            let columns: Vec<usize> = config
225                .iter()
226                .enumerate()
227                .filter(|(_, &v)| v)
228                .map(|(j, _)| j)
229                .collect();
230
231            if columns.is_empty() {
232                // No columns selected — consistent iff b = 0.
233                if self.rhs.iter().all(|&v| v == 0) {
234                    return Ok(Min(Some(0)));
235                } else {
236                    return Ok(Min(None));
237                }
238            }
239
240            if self.is_consistent(&columns)? {
241                Min(Some(i64::try_from(columns.len()).map_err(|_| {
242                    crate::traits::EvaluationError::IntegerOverflow(
243                        "converting solution weight to i64".into(),
244                    )
245                })?))
246            } else {
247                Min(None)
248            }
249        })
250    }
251}
252
253impl crate::solvers::BruteForceProblem for MinimumWeightSolutionToLinearEquations {
254    fn dimensions(&self) -> Vec<usize> {
255        vec![2; self.num_variables()]
256    }
257}
258
259crate::declare_variants! {
260    default MinimumWeightSolutionToLinearEquations => "2^num_variables" create MinimumWeightSolutionCreateSpec,
261}
262
263crate::register_brute_force! {
264    MinimumWeightSolutionToLinearEquations decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
265}
266
267#[cfg(feature = "example-db")]
268pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
269    // A = [[1,2,3,1],[2,1,1,3]], b = [5,4], m=4, n=2
270    // Config [1,1,0,0]: select columns 0,1. Submatrix [[1,2],[2,1]].
271    // Solve [1,2;2,1]y=[5,4] → y=(1,2). Consistent. Min(2).
272    let matrix = vec![vec![1, 2, 3, 1], vec![2, 1, 1, 3]];
273    let rhs = vec![5, 4];
274    vec![crate::example_db::specs::ModelExampleSpec {
275        id: "minimum_weight_solution_to_linear_equations",
276        instance: Box::new(MinimumWeightSolutionToLinearEquations::new(matrix, rhs)),
277        optimal_config: serde_json::json!(vec![true, true, false, false]),
278        optimal_value: serde_json::json!(2),
279    }]
280}
281
282#[cfg(test)]
283#[path = "../../unit_tests/models/algebraic/minimum_weight_solution_to_linear_equations.rs"]
284mod tests;
problemreductions/models/algebraic/minimum_weight_solution_to_linear_equations.rs

problemreductions/models/algebraic/
minimum_weight_solution_to_linear_equations.rs
