Skip to main content
MathOverflow

Return to Question

edited tags
Link
RobPratt
RobPratt
  • 5.4k
  • 1
  • 15
  • 25
Minor grammar improvements and Math Jaxing
Source Link
Daniele Tampieri
Daniele Tampieri
  • 6.4k
  • 7
  • 30
  • 45

Solve NP-hard type problems with linear programming ​

I would like to know if there is any way to solve thean 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 makemade a program usingwhich 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 O(n)its asymptotic behavior $O(n)$ yet.

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

Greetings.

Solve NP-hard type problems with linear programming ​

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

I ask because I make a program using linear programming and it solves them, but the execution time does not vary specifically from the input size, so I can't define 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 them.

Greetings.

Solve NP-hard type problems with linear programming

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.

Source Link
Juan Carlos
Juan Carlos
  • 1

Solve NP-hard type problems with linear programming ​

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

I ask because I make a program using linear programming and it solves them, but the execution time does not vary specifically from the input size, so I can't define 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 them.

Greetings.