[Help-glpk] Help with callbacks for branch/cut optimisation

[Martijn van Oosterhout]

Hoi,

I'm using glpk to solve a MILP problem which resembles the Travelling
Salesman Problem. That is, you can easily formulate an ILP problem
with all the basic constraints but the solution might have loops.
Adding all the necessary constraints to exclude loops would take far
too long, so what you do is solve the basic problem and if the found
solution isn't actually feasible, add a constraint excluding that
solution and try again. (I say 'resembles' because the TSP has a
special structure with permits other ways to avoid loops, these other
ways don't work here).

I thought that by using the callbacks in the branch/cut algorithm I
could add the necessary constraints during the optimisation rather
than running the whole solver multiple times. The documentation talks
about cut pools which look like they might be useful.

Except when I tried it didn't work, because the reason GLP_IROWGEN is
called with the solution to the LP relaxation, at which point you have
non-integer variables and determining problematic loops isn't
possible. By the time reason GLP_IBINGO is called it's too late to
prevent the integer solution being returned, because you can't add
constraints at that point.

I feel I'm missing something obvious. A thought that crossed my mind
is that all integer feasible solutions are found by solving an relaxed
LP problem. So it would be sufficient to, in the GLP_IROWGEN, check
for integrality and if so add my constraints. However, it doesn't
explicitly say this in the documentation and it's not immediately
clear to me that it will always work.

Can anybody clarify this for me?

Thanks in advance,
-- 
Martijn van Oosterhout <address@hidden> http://svana.org/kleptog/