I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't definitely be used in order to get the shortest routes in the end, would such algorithm be valuable and something new? It will definitely reduce many combinations of routes but I don't think 80% would be always even close to enough to turn samples like a million cities into a P problem.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Valuable but not new.
This idea, which also applies more generally to mixed integer linear programming, is called reduced-cost fixing and goes back at least as far as Dantzig, Fulkerson, and Johnson (1954).
See https://or.stackexchange.com/questions/9125/good-references-for-reduced-cost-fixing
For eliminating edges a priori for Euclidean TSPs, see Edge Elimination in TSP Instances, Stefan Hougardy and Rasmus T. Schroeder (2014).
-
$\begingroup$ Can it remove up to 80% of values for any samples though? $\endgroup$ Commented Dec 3, 2022 at 0:26
-
$\begingroup$ It depends on the instance and the quality of the feasible solution. $\endgroup$– RobPrattCommented Dec 3, 2022 at 0:54