You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The current Problem trait hardcodes discrete configuration spaces:
pubtraitProblem:Clone{typeValue:Clone;fndims(&self) -> Vec<usize>;// cardinality per variablefnevaluate(&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):
pubtraitProblem:Clone{constNAME:&'staticstr;typeValue:Clone;typeConfig;// Vec<usize> for discrete, Vec<f64> for continuousfnevaluate(&self,config:&Self::Config) -> Self::Value;fnvariant() -> Vec<(&'staticstr,&'staticstr)>;}
The current dims() method would move to a sub-trait or extension trait for enumerable (discrete) problems:
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 logic — reduce_to() doesn't use dims()/evaluate()
Alternatives Considered
Default implementations (dims() returns vec![]) — backward compatible but not type-safe; discrete/continuous distinction is runtime-only
Dummy dims for continuous problems — zero framework change, but semantically wrong
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
Motivation
The current
Problemtrait hardcodes discrete configuration spaces: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 trivialevaluate(), which is semantically dishonest.Proposed Change
Introduce an associated type
Configon theProblemtrait, following the pattern used by Rust'sargmincrate (CostFunction::Param):The current
dims()method would move to a sub-trait or extension trait for enumerable (discrete) problems:BruteForcewould be bounded byEnumerableinstead ofProblem.Impact
type Config = Vec<usize>;added (mechanical, can be scripted)ProblemtoEnumerableReduceTo,ReductionResult) — need to become generic overConfigor use type erasure;extract_solutioncurrently returnsVec<usize>Configassociated typereduce_to()doesn't usedims()/evaluate()Alternatives Considered
dims()returnsvec![]) — backward compatible but not type-safe; discrete/continuous distinction is runtime-onlyContinuousProblemtrait — duplicates infrastructure, splits the ecosystemPriority
Low — currently only QuadraticProgramming (#528) needs this. Should be done when more continuous problems accumulate or when a larger trait refactor is planned.
References
argmincrate'sCostFunctiontrait: associated typeParamfor configuration space