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

[Michael Hennebry]

On Wed, 6 Feb 2013, Martijn van Oosterhout wrote:

> On 5 February 2013 19:29, Michael Hennebry
> <address@hidden> wrote:

> > 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.
>
> That might work. I'm afraid about adding too many constraints but
> perhaps I shouldn't be. Using the cut planes is also an approach to
> investigate.

The mechanism suggested was selected to be easy and to avoid false positives.
It will not find a loop that is not there.
In fact, I might have been too conservative.
If you are looking for loops involving only n edges,
1-1/(n+1) should round to 1.

There is a better heuristic.
Label all your node with slack 0.
Select a pair of nodes, a and b.
Merge them, call the new node f.
slack[f]=slack[a]+slack[b]+1-x[a,b]-x[b,a]
x[f,q]=x[a,q]+x[b,q]  for q a node not a, b, f
x[q,f]=x[q,a]+x[q,b]  for q a node not a, b, f

Any node that gets negative slack corresponds to a cuttable loop.

'Tis customary to start with large values of x[a,b]+x[b,a].

If some loops are allowed,
you might have to take special steps to avoid cutting them.


Also, you don't neeed to avoid false positives,
you just need to avoid passing them to GLPK.

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