I forgot about an IP formulation technique that can work here to avoid the big-M constraints. The idea is to have a boolean variable for each of the cross product {possible sums} x {subsets of size 2 or 3}. You have to cap the possible sums at some maximum value, but that's okay since we're looking for small examples. An example such variable would be e_{83, {x_2, x_4}}.
You'd have constraints like this to enforce that every sum only gets used once:
e_{83, {x_1, x_2}} + e_{83, {x_1, x_3}} + ... + e_{83, {x_6, x_7, x_8}} <= 1
Constraints like this set the sum of each subset:
x_2 + x_4 = 1 * e_{1, {x_2, x_4}} + 2 * e_{2, {x_2, x_4}} + ... + 300 * e_{300, {x_2, x_4}}
Constraints like this ensure that each subset has exactly one sum:
e_{1, {x_2, x_4}} + e_{2, {x_2, x_4}} + ... + e_{300, {x_2, x_4}} = 1
The number of variables is quite large, but I think it should be easier for an IP solver than a big-M formulation because the LP relaxation is nicer. I don't have access to an IP solver license currently so I can't really test this out. As far as I know, free IP solvers are not very good, so trying it out there would not be very representative.
Author
Topic: How do I even start to solve this math problem? (Read 11362 times)