Module algebraic

Expand description

Algebraic problems.

Problems whose input is a matrix, linear system, or lattice:

AlgebraicEquationsOverGF2: Multilinear polynomial equations over GF(2)
QUBO: Quadratic Unconstrained Binary Optimization
ILP: Integer Linear Programming
ClosestVectorProblem: Closest Vector Problem (minimize lattice distance)
BMF: Boolean Matrix Factorization
ConsecutiveBlockMinimization: Consecutive Block Minimization
ConsecutiveOnesSubmatrix: Consecutive Ones Submatrix (column selection with C1P)
EquilibriumPoint: Pure-strategy Nash Equilibrium existence
QuadraticAssignment: Quadratic Assignment Problem
QuadraticCongruences: Decide x² ≡ a (mod b) for x in {1, …, c-1}
QuadraticDiophantineEquations: Decide ax² + by = c in positive integers
SimultaneousIncongruences: Decide whether x ≢ aᵢ (mod bᵢ) for all i simultaneously
MinimumMatrixDomination: Minimum Matrix Domination (minimum dominating set of 1-entries)
MinimumWeightDecoding: Minimum Weight Decoding (minimize Hamming weight of Hx≡s mod 2)
MinimumWeightSolutionToLinearEquations: Minimum Weight Solution to Linear Equations (minimize Hamming weight of Ay=b solution)
SparseMatrixCompression: Sparse Matrix Compression by row overlay

Structs§

AlgebraicEquationsOverGF2: Algebraic Equations over GF(2).
BMF: The Boolean Matrix Factorization problem.
Bounded: Every variable has explicit finite lower and upper bounds.
ClosestVectorProblem: Euclidean Closest Vector Problem over an integer lattice basis.
ConsecutiveBlockMinimization: Consecutive Block Minimization (CBM) problem.
ConsecutiveOnesMatrixAugmentation
ConsecutiveOnesSubmatrix: The Consecutive Ones Submatrix problem.
EquilibriumPoint: Equilibrium Point problem.
FeasibleBasisExtension: The Feasible Basis Extension problem.
General: Variable intervals may have infinite endpoints.
ILP: Integer Linear Programming model.
IntegerVariable: Bounds of one mathematical integer variable.
LinearConstraint: One sparse linear constraint.
MinimumMatrixCover: Minimum Matrix Cover.
MinimumMatrixDomination: Minimum Matrix Domination.
MinimumWeightDecoding: Minimum Weight Decoding.
MinimumWeightSolutionToLinearEquations: Minimum Weight Solution to Linear Equations.
QUBO: The QUBO (Quadratic Unconstrained Binary Optimization) problem.
QuadraticAssignment: The Quadratic Assignment Problem (QAP).
QuadraticCongruences: Quadratic Congruences problem.
QuadraticDiophantineEquations: Quadratic Diophantine Equations problem.
SimultaneousIncongruences: Simultaneous Incongruences problem.
SparseMatrixCompression: Sparse Matrix Compression.

BoundsPolicy: Type-level requirement on the explicitly stored variable intervals.
ILPCoefficient: Numeric domain shared by an ILP’s constraints, right-hand sides, and objective.
VariableDomain: Static certificate for a homogeneous ILP variable domain.