Add ILP reduction paths for CircuitSAT, MaxCut, QUBO, SpinGlass

[GiggleLiu]

Problem

The CLI pred solve command defaults to the ILP solver and auto-reduces problems to ILP. However, 4 problem types currently have no reduction path to ILP:

Problem	Status
CircuitSAT	No path to ILP
MaxCut	No path to ILP
QUBO	No path to ILP
SpinGlass	No path to ILP

Running pred solve on these problems produces: Error: No reduction path from <Problem> to ILP

The user must currently use --solver brute-force as a workaround.

Expected Behavior

All problem types should be solvable via pred solve with the default ILP solver.

Possible Reductions

• QUBO → ILP: QUBO can be reformulated as a binary quadratic program, which can be linearized into ILP
• SpinGlass → ILP: Similar to QUBO (SpinGlass is equivalent to QUBO on a graph)
• MaxCut → ILP: Standard ILP formulation exists with edge indicator variables
• CircuitSAT → ILP: Via CircuitSAT → Satisfiability → ILP (SAT → ILP path already exists), or direct circuit-to-ILP encoding

Workaround

pred solve problem.json --solver brute-force

[GiggleLiu]

As SpinGlass and MaxCut can be reduced to QUBO with a trivial reduction, so just implementing QUBO to ILP is enough.

For CircuitSAT, can directly reduction from CircuitSAT ILP be more efficient? Survey needed.