[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: Andrew Makhorin
Subject: Re: [Help-glpk] Help with callbacks for branch/cut optimisation
Date: Wed, 06 Feb 2013 23:41:45 +0400

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

It is possible. Moreover, it is much better to add subtour elimination
constraints as early as possible, because this may significantly reduce
the size of the search tree. To generate such constraints for
*fractional* solutions to lp relaxation you may use a standard technique
based on finding a min cut in a capacitated network. If you are
interested, I could provide a detailed example (from glpk 4.9).

See also glpk/examples/cplex/README.

reply via email to

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