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

[Michael Hennebry]

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