Skip to content

Add bf_vs_ilp tests for all ILP reduction rules #773

@isPANN

Description

@isPANN

Problem

Not all ILP reduction rules have a bf_vs_ilp test that verifies the ILP solver produces an optimal solution by comparing against BruteForce on the same instance. This means an ILP formulation bug (e.g., missing constraint causing a suboptimal objective) could go undetected.

Context

The canonical_rule_example_specs tests (rule_specs_solution_pairs_are_consistent) verify that source.evaluate(source_config) and target.evaluate(target_config) are consistent, but do not compare the objective value against the BruteForce ground truth. The bf_vs_ilp unit test pattern is the only thing that catches optimality bugs on small instances.

After #772, all ILP canonical examples now use ILPSolver::new().solve() dynamically — making bf_vs_ilp coverage even more important as a second line of defense.

Expected fix

For every *_ilp.rs rule that lacks a test_*_bf_vs_ilp function, add one following the existing pattern:

#[test]
fn test_<source>_to_ilp_bf_vs_ilp() {
    let problem = /* small instance */;
    let reduction = ReduceTo::<ILP<V>>::reduce_to(&problem);

    let bf_value = BruteForce::new().solve(&problem);
    let ilp_solution = ILPSolver::new()
        .solve(reduction.target_problem())
        .expect("ILP should be solvable");
    let extracted = reduction.extract_solution(&ilp_solution);
    assert_eq!(problem.evaluate(&extracted), bf_value);
}

Scope

Audit all src/unit_tests/rules/*_ilp.rs files and add missing bf_vs_ilp tests.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    Status
    Done

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions