Hi Sebastian,
Thank you for your suggestion. I like it a lot. I'm working with
a MIP that has all the variables constrained to being integers >= 0.
Can you suggest a cut that might work for this sort of problem? One
analogous to the one you suggested doesn't seem to work because it can
eliminate valid solutions --> I'm having trouble thinking of a way to
eliminate only the single solution point.
Thanks,
--Jordan
Sebastian Pokutta wrote:
IF you have a 0-1 program you can try to cut off the solution
(point) as follows to check the presence of other solutions with
same cost.
Say the solution is x and let I be the support of x, i.e. x_i = 1
iff i \in I and let J be the zero-support, i.e. x_i = 0 iff i \in J.
Note that I \cup J \subseteq [n] where n is the dimension but
equality does not necessarily hold as we have a mixed-0-1-program.
Now you can add the cut
\sum_{i in I} (1-x_i) + \sum_{i ⁄in J} x_i >= 1/2 to cut-off exactly
that solution. All other valid solutions y will "survive" because
there is at least one coordinate y_i \neq x_i. Hence, if i \in I
then x_i = 1 and so y_i = 0 and the sum above is >= 1/2. Similar
holds if i \in J.
Now you can re-optimize with this cut added and if you obtain a
valid solution with the same solution value then there are more than
one solution. You could (theoretically - it is rather impraticable
though) even enumerate the solution with same cost using this "trick".
For general mixed-integer program the same procedure works as well,
though you have to find a cut that cuts-off your solution which
might be a bit harder in this case.
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk