# How to identify constraints that make problem not solvable in polynomial time?

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?

• I can't find any mention of "polynomial" in the paper Sep 27 at 7:42
• Look at the Jain and Grossman reference. It's mentioned there. Sep 27 at 16:07

• Yes, you could still use CP to solve the resulting subproblem that involves all machines, but the resulting feasibility cuts would be weaker. Also note that $x$ appears in the objective, so the subproblem would no longer be one of just determining feasibility. The decomposition here is variable-based (Benders), not constraint-based (Dantzig-Wolfe). Sep 27 at 12:47
• I understand in principle what you're saying - "...cuts could be weaker". However, if I got an infeasible solution, e.g. $x_{11} =1, x_{12}=1$ which clearly violates constraint (12), then the cut proposed in the paper $\sum_{i \in S'} x_{im} \le |S'| -1$ where $S'= \{ i | x_{im} =1 \forall i \forall m \}$would still eliminate this infeasible solution. Sorry for dragging this out but could you please tell me what you mean by the "cuts would be weaker"? Sep 27 at 16:32