3 ms·
I am answering here (hoping that it will be read by others too). First of all: thanks everyone for forcing me to go back and re-visit some stuff about LP/IP -
by Pamar 9y ago
I am answering here (hoping that it will be read by others too).
First of all: thanks everyone for forcing me to go back and re-visit some stuff about LP/IP - I think I was wrong - some sort of search tree/branch and bound is not just a speedup trick - it looks like it is the only way to actually get a correct solution for IP problems.
So let me amend my two previous statements:
Linear Programming does not require any search tree or backtracking is CORRECT.
Linear Programming can solve Sudoku is *WRONG* - for Sudoku you need Integer Programming, and that requires an approach that involves search trees/backtracking.
Sorry for the confusion, and thanks again for making me recheck my assumptions.
- zodiac 9y agoI'm pretty sure cutting-plane methods for IP don't strictly require "tree search" (of course, they still require super-polynomial time to solve IP problems) https://en.wikipedia.org/wiki/Cutting-plane_method https://en.wikipedia.org/wiki/Cutting-plane_method
- taeric 9y agoTo your original point, they do not consider these "backtracking" in the standard sense. So, I'd actually agree to your original point and that I was wrong. I should also have stressed harder that I agreed with your definition of brute force. I was just offering an explanation for where I think the post went awry.