[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Help with callbacks for branch/cut optimisation
From: |
Heinrich Schuchardt |
Subject: |
Re: [Help-glpk] Help with callbacks for branch/cut optimisation |
Date: |
Mon, 04 Feb 2013 19:16:12 +0100 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:10.0.11) Gecko/20121122 Icedove/10.0.11 |
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,