Skip to content

[Refactor] Generalize Problem trait with associated type Config for continuous-variable problems #958

@isPANN

Description

@isPANN

Motivation

The current Problem trait hardcodes discrete configuration spaces:

pub trait Problem: Clone {
    type Value: Clone;
    fn dims(&self) -> Vec<usize>;          // cardinality per variable
    fn evaluate(&self, config: &[usize]) -> Self::Value;  // discrete index
}

This assumes all variables have finite discrete domains. However, some NP-complete problems have continuous (rational/real) variables — notably Quadratic Programming (#528), where Vavasis (1990) proved NP membership despite the continuous domain (the witness bit-length is polynomially bounded).

Currently there is no clean way to implement such problems. The workaround is to return dummy dims() values and a trivial evaluate(), which is semantically dishonest.

Proposed Change

Introduce an associated type Config on the Problem trait, following the pattern used by Rust's argmin crate (CostFunction::Param):

pub trait Problem: Clone {
    const NAME: &'static str;
    type Value: Clone;
    type Config;  // Vec<usize> for discrete, Vec<f64> for continuous
    fn evaluate(&self, config: &Self::Config) -> Self::Value;
    fn variant() -> Vec<(&'static str, &'static str)>;
}

The current dims() method would move to a sub-trait or extension trait for enumerable (discrete) problems:

pub trait Enumerable: Problem<Config = Vec<usize>> {
    fn dims(&self) -> Vec<usize>;
}

BruteForce would be bounded by Enumerable instead of Problem.

Impact

  • 200+ model files need type Config = Vec<usize>; added (mechanical, can be scripted)
  • BruteForce solver changes bound from Problem to Enumerable
  • Reduction traits (ReduceTo, ReductionResult) — need to become generic over Config or use type erasure; extract_solution currently returns Vec<usize>
  • Registry/DynProblem — moderate changes for type-erased dispatch
  • declare_variants! macro — needs to emit the Config associated type
  • No impact on reduction logicreduce_to() doesn't use dims()/evaluate()

Alternatives Considered

  1. Default implementations (dims() returns vec![]) — backward compatible but not type-safe; discrete/continuous distinction is runtime-only
  2. Dummy dims for continuous problems — zero framework change, but semantically wrong
  3. Parallel ContinuousProblem trait — duplicates infrastructure, splits the ecosystem

Priority

Low — currently only QuadraticProgramming (#528) needs this. Should be done when more continuous problems accumulate or when a larger trait refactor is planned.

References

  • argmin crate's CostFunction trait: associated type Param for configuration space
  • Vavasis (1990): QP ∈ NP despite continuous variables (polynomial bit-length witnesses)
  • [Model] QuadraticProgramming #528: QuadraticProgramming model blocked on this design question

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    Status

    No status

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions