[Top][All Lists]

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

Re: [Help-glpk] reincarnation of tspsol

From: Andrew Makhorin
Subject: Re: [Help-glpk] reincarnation of tspsol
Date: Mon, 19 Oct 2015 11:16:47 +0300

Thank you for your comments and providing the patch.

> I think there is an issue with the way tspsol works: The rounding
> heuristic of glp_intopt runs after row generation (when no row was
> added) and may give an integer solution with subtours. The heuristic
> only checks that the solution satisfies the original problem, so no
> subtour elimination constraints are checked. Moreover, an appropriate
> constraint may not have been added yet. 

You are perfectly correct.

> To avoid this, the rounding heuristic should be disabled.
> Unfortunately, there is no control parameter for this in glp_iocp, so
> I'm attaching an awful hack to disable it from the tspsol callback.
> This is only in case anyone gets an "Assertion failed: kk <= n" error
> and wants to check if this is the reason, I would advise against using
> it for any other reason.

Probably the fact of specifying the callback routine can be used as a
flag to disable primal heuristics, because the callback routine itself
is able to apply heuristics performing necessary feasibility checks.

Andrew Makhorin

reply via email to

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