I am reading this paper, available for free viewing, which contains an example of job shop scheduling, shown below.
The details of the variable definitions, etc., can be found in the paper, but it's a pretty typical job scheduling problem. The paper solves it by decomposing it into an MILP and a Constraint Programming sub-problem. The MILP part is supposed to be "easy to solve" in some sense (i.e. polynomial time).
What I don't understand is: why is the MILP they have identified is any easier to solve than the original problem? Is it because constraints (13) and (16) involve more than one binary variable? To me, constraint (12) seems very difficult to satisfy, but for some reason that is included in the MILP. Faced with a general MILP, how to identify constraints which are more difficult to satisfy?