So, what we know is that there is no hope for a polynomial algorithm for integer linear programming unless of course NP is equal to P. And at the same time there is no hope for a short optimality proof. For example, an optimality proof is provided by duality. In this case we have two sets and two functions. We know that each one is upper bounded by the other one and we know there exist two points, hat x and hat y, such that the inequality turns into an equality. So, the implication is that hat x is a minimum of f(x) and a the same time hat y is a maximum of g(y). If we are able to find things of this sort, then once we have a solution we are able to prove its optimality.