In recent years algebraic geometry, number theory, and commutative algebra have shown their potential to solve challenging problems in discrete optimization. This talk hopes to show algebraic tools can be used to prove strong computational complexity results in optimization problems with non-linear or multi-objective objective functions and linear constraints. This is talk is partly based on joint work with M. Koeppe and R. Hemmecke.