Timeline for Can an optimization algorithm be "universal"?
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 11, 2021 at 16:48 | comment | added | D.W.♦ | @Peregring-lk, No. All NP-complete problems are reducible to integer linear programming, but that's not a very useful statement, as the same is true if you replace ILP with any other NP-complete problem. The simplex algorithm is not a state-of-the-art method for ILP. None of this changes my statements in my answer. | |
| Jan 11, 2021 at 13:18 | comment | added | ABu | Isn't all NP-hard problems reducible to non-linear programming? I know that a lot of NP-hard problems are reducible to integer linear programming; I remember even reading that the simplex algorithm (which I know, it's for LP, not ILP), was called NP-mighty or something like that, meaning that any NP-complete problem instance belongs to the lineal programming problem, and it's solvable using the simplex algorithm; I don't know at which extent a similar affirmation can be stated about NP-hard problems though. | |
| Sep 2, 2019 at 16:26 | history | answered | D.W.♦ | CC BY-SA 4.0 |