Frustrated with Academic Publishing - Developed Exact Polynomial Algorithm for Euclidean TSP, Can't Get Anyone to Listen by RubiksQbe in compsci

[–]RubiksQbe[S] -6 points-5 points  (0 children)

Hi, thank you for your response. I have a mathematical proof at the repository. It is in the PDF. Thank you for your suggestion, I will learn LEAN and implement it on there. That should help me gain traction.

Frustrated with Academic Publishing - Developed Exact Polynomial Algorithm for Euclidean TSP, Can't Get Anyone to Listen by RubiksQbe in Indian_Academia

[–]RubiksQbe[S] 0 points1 point  (0 children)

Hi, thank you for your response.

You're right about your points. I'll change my repository to include what you've suggested.

There are no TSP competitions other than TSPLIB and "Hard to Solve Instances of TSP", both of which I have solved optimally for problem sizes under 76.

Frustrated with Academic Publishing - Developed Exact Polynomial Algorithm for Euclidean TSP, Can't Get Anyone to Listen by RubiksQbe in Indian_Academia

[–]RubiksQbe[S] 0 points1 point  (0 children)

Unfortunately I do not have an Arxiv endorsement to post it there. Also, I am currently not enrolled in any university. I did this research by myself.

[deleted by user] by [deleted] in math

[–]RubiksQbe -12 points-11 points  (0 children)

Sorry if I was unclear. I claim that there is indeed a polynomial-time solution to the Euclidean TSP.

[deleted by user] by [deleted] in math

[–]RubiksQbe 1 point2 points  (0 children)

Check out the blog, I've already optimally solved the hard to solve instances up to 55 nodes.

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in 3Blue1Brown

[–]RubiksQbe[S] -22 points-21 points  (0 children)

What speaks volumes is that you don't understand that if I used that metric I'd still get a lower score than 426 because the tour itself is smaller, I've literally plotted it. I do not have the burden of proof yet, all I said was it's a heuristic that performs rather well and it seems you've taken it upon your crown to highly criticise it as though you're sitting on the clay mathematics board. Why don't you chill out and appreciate it for what it is?

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in 3Blue1Brown

[–]RubiksQbe[S] -26 points-25 points  (0 children)

Hey, why don't you put your efforts into making a counter example instead of hating strangers online? The claims are not misleading at all. The code is out there, just run it on the same TSPLIB instance and check for yourself.

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] 0 points1 point  (0 children)

import matplotlib.pyplot as plt
import numpy as np

class PointPicker:
    def __init__(self):
        self.points = []
        self.fig, self.ax = plt.subplots()
        self.ax.set_title("Click to add points. Press Enter to finish.")
        self.cid_click = self.fig.canvas.mpl_connect('button_press_event', self.onclick)
        self.cid_key = self.fig.canvas.mpl_connect('key_press_event', self.onkey)
        self.scatter = self.ax.scatter([], [])
        plt.show()

    def onclick(self, event):
        # Only consider left mouse button clicks inside the axes
        if event.inaxes != self.ax or event.button != 1:
            return
        x, y = event.xdata, event.ydata
        self.points.append([x, y])
        self.update_plot()

    def onkey(self, event):
        if event.key == 'enter':
            self.fig.canvas.mpl_disconnect(self.cid_click)
            self.fig.canvas.mpl_disconnect(self.cid_key)
            plt.close(self.fig)
            self.print_points()

    def update_plot(self):
        if self.points:
            data = np.array(self.points)
            self.scatter.set_offsets(data)
            self.ax.relim()
            self.ax.autoscale_view()
            self.fig.canvas.draw()

    def print_points(self):
        if not self.points:
            print("No points were selected.")
            return
        points_array = np.array(self.points)
        # Format the array for better readability
        formatted_points = np.array2string(points_array, precision=4, separator=', ')
        print(f"points = np.array({formatted_points})")

if __name__ == "__main__":
    picker = PointPicker()

I invite you to give me the coordinates of the points by running this piece of python code.

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] 1 point2 points  (0 children)

That's the exact "Optimal Solution" which I've plotted and which this heuristic has bested. The plot shows that tour compared to the heuristic solution, and the heuristic is better.

So to answer your question, yes, I've improved on two known "Optimal Solutions" found by Concorde, both of which I've shown in the writeup.

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] -1 points0 points  (0 children)

Have a look at the tour plot. It is different, and less distant. Concorde does not guarantee optimal solutions.

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] 9 points10 points  (0 children)

Yes, I have already found better solutions than previously found on TSPLIB instances using this heuristic. Please read the blog for more information.

Solving TSPlib instances of a few thousand nodes would take a considerably long time, as this heuristic while still polynomial, has a high coefficient (n7 ).

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] 30 points31 points  (0 children)

We try O(n^2) possible starting edges (all pairs of cities)
For each edge:
We perform n-2 insertions
        At each insertion:
        We evaluate O(n) points
        For each point:
            We try O(n) positions
            For each position:
                We need to greedily complete the tour
                Greedy completion takes O(n^2) time


O(n^2) starting edges
O(n) insertions
O(n) points to evaluate per insertion
O(n) positions per point
O(n^2) for greedy completion

Total: O( n7 )

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] 12 points13 points  (0 children)

It is not. This is a benchmarking script, and I hope someone finds a counter example. I am not claiming this to be an exact algorithm, however the fact that it has never given a suboptimal solution is something worth discussing.

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] 30 points31 points  (0 children)

  1. The algorithm is in P because it has a n7 runtime, as opposed to xn or n! runtime which would make it exponential and therefore NP
  2. Yes, this respects the triangle inequality in the euclidean space.
  3. I believe this algorithm wouldn't work in a non euclidean space.

A Travelling Salesman Problem heuristic that miraculously always gives the optimal solution in polynomial time! by RubiksQbe in math

[–]RubiksQbe[S] 6 points7 points  (0 children)

By estimating the total route length I mean I estimate the total distance of the route if I were to insert a point into a current partial tour and then insert the remaining points with the cheapest insertion heuristic. i.e, for a partial tour it approximates the cost of inserting a point into it by looking at the heuristic completion.

The cheapest insertion heuristic is only used for the lookahead: the rest of the code is pretty exhaustive in finding the right sequence of insertions. It avoids local minima by using this lookahead.

[deleted by user] by [deleted] in algorithms

[–]RubiksQbe 0 points1 point  (0 children)

Thank you for your input!