0
$\begingroup$

I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.

I ask this because I made a program which uses a linear programming algorithm and it solves them, but the execution time does not vary specifically from the input size, so I can't define its asymptotic behavior $O(n)$ yet.

For example, for the TSP with an input size $n=20$, depending on the cases and tested on an ordinary computer, it takes between $30$ seconds and $3$ minutes to solve the problem.

Greetings.

Improve this question
$\endgroup$
2
  • 10
    $\begingroup$ I am not exactly sure what you’re asking, but there is provably no polynomial size linear program such that any projection of the feasible region yields the TSP polytope (i.e. the convex hull of the indicator vectors of Hamiltonian cycles). This is a famous result of Fiorini, Massar, Pokutta, Tiwary and de Wolf (arxiv.org/abs/1111.0837). $\endgroup$
    – Jason Gaitonde
    Commented Dec 24, 2023 at 3:00
  • $\begingroup$ If you have a convex polytope whose vertices are integral, then you can solve integer programs via linear programming. But these are extremely special instances $\endgroup$
    – Rodrigo de Azevedo
    Commented Dec 25, 2023 at 14:06

0

Reset to default

You must log in to answer this question.