[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
Re: [Help-glpk] reincarnation of tspsol, Heinrich Schuchardt, 2015/10/20