[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Michael Hennebry
Subject: Re: [Help-glpk] Help with callbacks for branch/cut optimisation
Date: Tue, 5 Feb 2013 12:29:02 -0600 (CST)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Sun, 3 Feb 2013, Martijn van Oosterhout wrote:

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

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.

If you really need integers to do your constraint generation,
add the test to your GLP_IROWGEN routine.
If you do not have integers, do not add any cuts.

You probably do not need integers.
Loop constraints, i.e. cycle-breaking constraints,
can be generated for fractional solutions.
x12 + x23 + x31 <= 2 is a valid cycle-breaking constraint
and will cut off x12=x23=x31=0.7 .

Doing so can speed things up.

For the purposes of generating cycle-breaking constraints,
you can probably "round" solution to integer:
Anything >= 1-n**-2 rounds to one, everything else to 0.
n is the size of the largest loop with which you might be concerned.
Any loops found will cut off the current solution.
There are better ways.

Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily

reply via email to

[Prev in Thread] Current Thread [Next in Thread]