In the context of computational complexity theory, a hard problem typically refers to an infinite set of problem instances for which it is widely believed that the worst-case amount of work needed to solve the problem grows super-polynomially when the size of the problem instance grows. Here "amount of work" is typically measured in elementary operations (e.g. CPU instructions, that typically take a fixed amount of time), and the "size of the problem" instance is typically measured as the amount of symbols need to express the problem data (e.g. number of bits). Mixed Integer Programming is such a hard problem. However, the theory only tells us that for any instance size, some instances that are difficult to solve must exist. There may be plenty of instances for that same size that are easy to solve and the theory doesn't say anything about a fixed specific instance as the amount of work required to solve a fixed single instance is fixed as well.
The above mentioned hardness is often proven using a reduction proof: you show that if you can solve a new problem class in a certain (e.g. polynomial) amount of work, you can solve another problem that is known to be hard in roughly the same amount of work. Such hardness proof are thus relative: they just argue that problem A is at least as hard as problem B.
In come cases, it is also possible to prove that a subclass of problem instances is significantly easier to solve. For mixed integer programming, these are for example instances where:
- The constraint matrix is totally unimodular (the LP-relaxation will give you an integer solution)
- You have total dual-integrality (the LP-relaxation will give you an integer solution)
- The number of variables is bounded by a constant. (I don't recall the exact reference on how to do this, but I remember that it involves using the LLL-algorithm)
- The number of constraints is bounded by a constant, and the size of numbers in the instance are also bounded by a constant. This result is due to Papadimitriou.
If we are talking about a single problem instance without any additional information, the best you can do is try to solve it. If it turns out that the LP-relaxation is integer feasible, you stumbled upon an easy MIP instance.
In general, solving a MIP to optimality requires two things: (1) a solution and (2) a proof that the solution is optimal. While finding a feasible solution is already a hard problem according to computational complexity theory, in practice the main difficulty is often finding the proof of optimality. If the LP-relaxation of the MIP turns out to be integer, this proof is relatively easy: it is the same as the proof that the LP is optimal (which you can check using duality theorems). If the LP-relaxation is not integer, the only way we know involves some form of enumeration. In fact, all branch-and-bound approaches are just a clever way to enumerate all possible integer solutions, cutting away only the part of the solution space for which it is known that the optimal solution can not lie there.