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 <[email protected]> http://svana.org/kleptog/ _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
