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

[Heinrich Schuchardt]

Hello Martijn,

> 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.

For the TSP you first solve the LP. If the solution contains loops or 
non-integer variables you add additional constraints and solve the LP 
again. Essentially the MILP solver using branch and bound does the same. 
At each branching point it adds a constraint and solves the LP again.

> 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.

See the book indicated below for different constraints to add when you 
see a non-integer solution.

Literature:
The Traveling Salesman Problem: A Computational Study
Princeton Series in Applied Mathematics
David L. Applegate, Robert E. Bixby, Vasek Chvátal and William J. Cook
ISBN-10: 0691129932

You may also be interested in:

Limit Crossing
Sharlee Climer
ISBN 978-3-639-05796-6

Best regards

Heinrich Schuchardt


On 03.02.2013 17:29, Martijn van Oosterhout wrote:
> 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,