Out of curiosity, how does one prove near optimality in problems like this?
E.g., do you assume that the optimal value is the one produced by the non-integer LP?
E.g., do you assume that the optimal value is the one produced by the non-integer LP?
Great thing is that you can find the dual really easily and each feasible solution of the primal problem can be used to get a feasible solution of the dual.
The math behind that is really neat.
For several problems you can prove lower and/or upper bounds for the optimal results. For example you can prove that a route between two points may not be shorter than their distance.
If you use LP in production you often don't care about optimality and can work with suboptimal results very well. Worst case you stop after a timeout and just pick the best result.
Edit: I forgot to mention that during solving of a LP you usually get dynamically computed bounds. The branch and bounds algorithm works by computing bounds on relaxed problems that give upper bounds for the original problem.