What is a "hard problem" in the context of Mixed-integer programming?

Question

As a practical (real-world problems) point of view, it's important we could solve optimization problems as quickly as possible (for instance, to release a daily schedule).

Maybe a problem with many variables Or constraints is solved in a few time but, another takes a long time to solve. My questions are:

• What does "hard problem" mean?

• Is there any way to figure out such problems?

• How can we solve these problems without using some advanced algorithms? (In an optimal sense)

Answer 1

I'm going to stay away from asymptotic stuff and stick with problems whose dimensions seem manageable with current software. (Any problem is hard to solve if large enough. I once worked with some folks who proposed a spatial model so granular that the constraint matrix would not fit in memory.)

• Slow improvement in the best node bound makes it hard to solve a MIP, at least if "solve" means "to proven optimality". It's not uncommon to run a model with multiple sets of input parameters and have some instances solve quickly and others exhibit slow bound improvement. @nikaza mentioned "big M" models with large values of $M$. They tend to have weak relaxations, but it also happens with other types of models.
• Bad numerics can make your life miserable. By this I mean situations where rounding error results in incorrect solutions, slow progress or the solver just surrendering. Again, "big M" is sometimes the culprit, but it can happen for other reasons, including poorly scaled variables and constraints.
• Dealing with multiple objectives can be hard, in part because there may be no definitive "correct" way to balance them. I think the difficulty here is usually not that the model is hard to solve (although that can happen, due to numerics, if you optimize a weighted combination of objectives and use really big or really small weights for some). The difficulty tends to be needing to solve the model repeatedly with different trade-offs to find a solution that makes everyone happy.
• Symmetry can slow progress of the solver, largely because equivalent solutions can exist in different parts of the search tree. There are ways to exploit symmetry in some cases (if you know enough about the symmetry in the model at the outset, and possibly if you are coding your own solver) and ways to mitigate it (either by modeling or, with some solvers, by asking the solver to try to mitigate it), but I've dealt with instances where my best efforts were not enough to get the solution time down to something I was happy with.

Answer 2

MILP problems are hard in general, in the sense that there is no algorithm that solves any given MILP in polynomial time (unless P=NP).

With respect to when it's hard in practice, unfortunately, the answer is that, in general, we can't know until we try to solve them.

We do know some things that usually make the problems harder to solve but even then it's a rule of thumb:

1. Degeneracy/multiple global optima
2. Using full integers instead of binaries
3. Having too many integer variables
4. Using large M in big M notations
5. Having very large variable ranges
6. Overestimating feasible regions
7. Having dense problems, i.e., not sparse

Because these problems are generally quite hard we need advanced algorithms/solvers to solve anything meaningfully big in practice.

Answer 3

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.