Skip to content

ILP<i64> rules declare bounds as constraints, so ILP<i64> → ILP<bool> always fails #1176

Description

@isPANN

Summary

Every path of the form X → ILP<i64> → ILP<bool> → … (for example to QUBO or SpinGlass) fails on every instance for 41 of the 44 rules that produce ILP<i64>:

Error: concrete path N failed during reduction: ILP -> ILP: binary encoding requires a finite upper bound for every integer variable

This was 126 of the 128 errors in a sweep of pred path <variant> <target> <example.json> across all variants.

Root cause

  • ILP::new (src/models/algebraic/ilp.rs) gives every i64 variable the default domain [0, +∞).
  • Rules state variable bounds as constraint rows instead of variable domains. For example, minimumfeedbackarcset_ilp.rs adds o_v <= n - 1 as a LinearConstraint.
  • ilp_i64_ilp_bool.rs needs variable.upper_bound() to be finite for its binary encoding, so it rejects the output.

Only 3 of the 44 ReduceTo<ILP<i64>> rules use ILP::with_variables: biconnectivityaugmentation_ilp, ilp_bool_ilp_i64 and openshopscheduling_ilp. biconnectivityaugmentation_ilp still fails, so some of its variables are left unbounded.

Reproduce

pred create MIS --graph 0-1,1-2,2-3,3-0,0-2 -o mis.json
pred path MIS QUBO mis.json   # path 5: … → MinimumFeedbackArcSet → ILP/i64 → ILP/bool → QUBO

Proposed fix

  • For each ReduceTo<ILP<i64>> rule, declare the known variable intervals with ILP::with_variables (and IntegerVariable::new(Some(lo), Some(hi))) instead of, or in addition to, bound rows. Order/position variables, counts and flows almost always have a derivable finite bound.
  • Where a variable is truly unbounded, document it. The ILP<i64> → ILP<bool> edge then correctly rejects those instances.
  • Decide whether redundant bound constraints should be removed once they become variable domains. That affects num_constraints formulas and their tests.
  • Add a test that runs each ILP<i64> rule's canonical example through ILP<i64> → ILP<bool> and checks that the encoding succeeds.
  • Also check for a root-cause option: should ILP<i64> → ILP<bool> derive implied bounds from single-variable constraint rows?

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions