Using integer programming to find a solution without optimizing it
There is at most a pseudo-logarithmic gap between the complexity of optimization and simply finding a feasible solution.
We can turn any optimization problem into a feasibility problem by simply adding the optimality expression to the inequalities with some value $C$, and using binary search to find the optimal $C$.