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
    No fields configured for issues without a type.

    Projects

    Status
    No status

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions