Linear Relaxation for Traveling Salesman Problem (TSP)

Navigating the World of Optimization: A Dive into Linear Relaxation

Fresh from completing a MOOC on Discrete Optimization offered by Coursera, I find myself equipped with a solid foundation in understanding concepts and techniques for solving optimization problems.

One intriguing technique is Linear Programming (LP). So, in the following blog post, I’ll discuss my insights into leveraging LP for achieving linear relaxation in the context of TSP.

The TSP Conundrum

The Traveling Salesman Problem (TSP), a classic optimization challenge, tasks us with finding the shortest path that visits each node exactly once. This problem is no walk in the park… :D …it’s NP-complete, meaning there’s no guaranteed speedy algorithm to find an optimal solution as the problem size grows.

Linear Relaxation to the Rescue

To tackle the complexity of TSP, one approach is to leverage Linear Programming. LP allows us to relax binary constraints on decision variables, allowing real-valued solutions. Though these solutions might not be integers, they serve as an efficient upper bound for the optimization problem.

Insights from the Implementation

In a recent exploration, I delved into implementing an LP-based solution using Google OR-Tools. During the course at coursera I did implement my own LP using the simplex method. But it was more for learning purposes than for actuall usage. The notebook I created walks through the intricacies, from generating a graph to visualizing the obtained solutions. I found this approach not only insightful but also a stepping stone for further refinements.

If you’re curious about the implementation details, branching strategies, and the visualization of the solutions, I invite you to check out the notebook. You can find it here.

Conclusion

Linear relaxation emerges as a powerful tool in the arsenal of solving combinatorial optimization problems. It not only provides a pragmatic upper bound but also lays the groundwork for iterative improvements. Tackling TSP with LP has been an enlightening journey, and I’m excited to see where this exploration leads next.

Happy optimizing!