Struct MinimumWeightSolutionToLinearEquations 

pub struct MinimumWeightSolutionToLinearEquations { /* private fields */ }

Minimum Weight Solution to Linear Equations.

Given an n×m integer matrix A and an integer vector b, find a rational vector y with Ay = b that minimizes ||y||_0 (the number of non-zero entries, i.e., the Hamming weight of y).

Representation

Each of the m columns is a binary variable: x_j = 1 means column j is selected (i.e., y_j may be non-zero). The evaluator checks whether the restricted system (using only selected columns) is consistent over the rationals, and returns the count of selected columns if so.

Example

use problemreductions::models::algebraic::MinimumWeightSolutionToLinearEquations;
use problemreductions::{Problem, Solver, BruteForce};

let matrix = vec![
    vec![1, 2, 3, 1],
    vec![2, 1, 1, 3],
];
let rhs = vec![5, 4];
let problem = MinimumWeightSolutionToLinearEquations::new(matrix, rhs);
let solver = BruteForce::new();
let witness = solver.find_witness(&problem);
assert!(witness.is_some());

Implementations

impl MinimumWeightSolutionToLinearEquations

pub fn new(matrix: Vec<Vec<i64>>, rhs: Vec<i64>) -> Self

Create a new MinimumWeightSolutionToLinearEquations instance.

Panics

Panics if the matrix is empty, rows have inconsistent lengths, rhs length does not match the number of rows, or there are no columns.

pub fn matrix(&self) -> &[Vec<i64>]

Returns a reference to the matrix A.

pub fn rhs(&self) -> &[i64]

Returns a reference to the right-hand side vector b.

pub fn num_equations(&self) -> usize

Returns the number of equations (rows of A).

pub fn num_variables(&self) -> usize

Returns the number of variables (columns of A).

Trait Implementations

impl Clone for MinimumWeightSolutionToLinearEquations

fn clone(&self) -> MinimumWeightSolutionToLinearEquations

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MinimumWeightSolutionToLinearEquations

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MinimumWeightSolutionToLinearEquations

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumWeightSolutionToLinearEquations

const NAME: &'static str = "MinimumWeightSolutionToLinearEquations"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Min<usize>

The evaluation value type.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Min<usize>

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl Serialize for MinimumWeightSolutionToLinearEquations

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for MinimumWeightSolutionToLinearEquations