4 ms·
What algorithm for ILP do you use? I think most (all?) solvers use a variation of branch-and-bound.
by adrianN 10y ago
What algorithm for ILP do you use? I think most (all?) solvers use a variation of branch-and-bound.
- Pamar 10y agoI 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 10y 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 10y 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.