0
$\begingroup$

I am reading this paper, available for free viewing, which contains an example of job shop scheduling, shown below.

part_1 part_2

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I can't find any mention of "polynomial" in the paper $\endgroup$
    – fontanf
    Sep 27 at 7:42
  • $\begingroup$ Look at the Jain and Grossman reference. It's mentioned there. $\endgroup$
    – somewhere
    Sep 27 at 16:07

2 Answers 2

Reset to default
3
$\begingroup$

The motivation is the same as in the Jain and Grossmann reference [59]. After assigning jobs to machines, the problem decomposes into a separate feasibility subproblem for each machine. Jain and Grossmann solve these subproblems by using the CUMULATIVE constraint from CP. The paper you linked instead uses QC for the subproblems.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Right, yeah I get that. But why not include constraint (12) in the CP? It's a difficult constraint to satisfy so it might as well be part of the constraint programming. If we include constraint (12) in the CP, decomposing it like this would still satisfy the requirements to apply techniques in Jain and Grossman. $\endgroup$
    – somewhere
    Sep 27 at 3:36
  • $\begingroup$ Constraint (12) involves a sum across machines, so including it in the subproblem would destroy the separability by machine and hence prohibit solving the machines independently. $\endgroup$
    – RobPratt
    Sep 27 at 3:51
  • $\begingroup$ I agree that would stop us from solving the for machines' feasibility independently. However, it wouldn't stop us from using the CUMULATIVE constraint for checking feasibility of all machines at once, right? $\endgroup$
    – somewhere
    Sep 27 at 5:37
  • $\begingroup$ 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). $\endgroup$
    – RobPratt
    Sep 27 at 12:47
  • $\begingroup$ 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"? $\endgroup$
    – somewhere
    Sep 27 at 16:32
3
$\begingroup$

You can also see that the second part, constraints 13 to 16, contains more variables (IxI), more constraints (IxIxMxM) and a big M formulation (which is not good for MIP resolution). The first part (constraints 10 to 12) is more tractable and seems to be close to a bin-packing problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Then is there any reason we can't make it even more tractable by moving some of the constraints from the MILP to the CP? e.g. constraint (12). $\endgroup$
    – somewhere
    Sep 27 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.