[Pamar]

As I mentioned elsewhere, it has been ages since I took an actual formal exam on Linear Programming (and Integer Programming) - since then I always used dedicated sw to solve LP (there is for example a nice, self-contained LP solver in Numerical Recipes in C) and so I always focused more on how to describe the problems in terms of linear constraints.

"In my mind" it works like this: https://www.quora.com/What-is-the-difference-between-integer...

Having said this, while NP is guaranteed to terminate the actual computation time may take ages. Integer Programming may very well leverage the fact that the solution is restricted to integer values and apply different, faster algorithm to exploit this property - including search trees. But in the most general sense you do not need a search tree or backtracking for Linear Programming.