/tsp_bb_lp

Solving the Salesman Problem through Branch and Bound and Linear Programming

Primary LanguageC

tsp_bb_lp

Solving the Salesman Problem through Branch and Bound and Linear Programming

Problem description

The salesman problem (TSP) is a classic NP-hard problem in computer science. It is widely accepted (although not proved) that TSP cannot be solved in polynomial time by deterministic systems.

Theoretical approach

This projects aims to solve TSP by combining combinatorial optimization (Branch and Bound) with operations research (Linear Programming)

Dependencies

The LP solving is done through the GLPK library

This project was developed as a undergrad thesis at the Federal University of Parana for the Computer Sciences course.