It is unclear whether you are asking about integer programs or linear, so I'll address both. Integer programming is very hard, and is an active area of researc

It is unclear whether you are asking about integer programs or linear, so I'll address both. Integer programming is very hard, and is an active area of research. The space of problems that arise in practice typically have sparsity, special structure, and other features that allow for shortcuts to be employed so that brute force isn't needed. Interior point solvers are guaranteed to find a global solution, and it can be proved that they will do so efficiently [1]. Practical implementations leverage decades of experience to improve upon the theoretical guarantees. [1] https://en.wikipedia.org/wiki/Convex_optimization https://en.wikipedia.org/wiki/Convex_optimization