# Relaxation and complexity of two formulations

I have two different MILP formulations for the same scheduling problem with the same complexity but with different running times. Why it is recommended to compare the relaxed versions of each formulation to deduce the running time (and more precisely about the B&B tree size)?

What is the advantage of considering the relaxed models instead of the original models?

Also I have other questions:

• Are all the scheduling problems NP-hard? Otherwise how to determine if a problem is NP-hard or not?

• A formulation with integer and binary variables is called integer program or mixed integer linear program?

• Too many questions in one post! For the third question see here. For the last question, note that binary variables are a subset of integer variables. Commented Oct 22, 2020 at 10:48

Why it is recommended to compare the relaxed versions of each formulation to deduce the running time (and more precisely about the B&B tree size)?

Generally, better (= tighter) is the relaxation of an integer optimization model, better should work a brand-and-bound tree solution approach to this model. Nevertheless, there exist some NP-hard problems for which the cost of the linear relaxation is equal to the cost of an optimal integer solution. Indeed, despite having a cost equal to the optimum integer solution, the relaxed solution may be highly fractional, then bringing no insightful information for the search of an integer one. In conclusion, just looking at the value of the linear relaxation will not inform you so much about the running time of the resolution of the original integer model (by B&B or any other approaches).

Are all the scheduling problems NP-hard? Otherwise how to determine if a problem is NP-hard or not?

Some scheduling problems are easy to solve, by polynomial-time (or even linear-time) combinatorial algorithms. But these problems are generally very basic, not realistic OR problems as you can find in the industry. For example, here is a paper on such an easy problem. To learn about NP-hardness, have a look at the Wikipedia page on the topic; this is a good starting point. You will also find a lot of resources on the web.

The initial gap can be an indicator but not a very good one. I have seen many problems start with a tight bound and then never improve, and I have also seen many problems start with a horrendous gap that improves very quickly.

Honestly, there is no way to know in advance, we just have to try solving all formulations we can come up with, until we find one that works.