Problem with big-M in CPLEX OPL

I have a model for the no-wait flow shop scheduling problem, that utilizes the linear ordering variables, and there is a constraint with big-M. When I implement the model in CPLEX OPL, the model assigns zero to all linear ordering variables. I guess the problem is with the big-M constraint, but I don't know how to fix it.

Here is my implementation of the two main constraints in CPLEX OPL. The variable X[i][j] takes 1 if job j is processed after job i in the sequence. The variable C[i][k] shows the completion time of job i on machine k.

In the second constraint (c2) I put 10000 as the big-M (the same value I use in other solvers). The answer turns out to be infeasible due to constraint 1 (c1), since the solver puts all X variables equal to zero (hence violating c1 since 0 = 1).

int NumofJobs = 2;
int NumofMachines = 3;

range n = 1..NumofJobs;
range m = 1..NumofMachines;
dvar boolean X[n][n];
dvar int+ C[n][m];

minimize (sum (i in n) (C[i][NumofMachines]));

subject to {

forall (i in n)
forall (j in n: j > i)
c1: X[i][j] + X[j][i] == 1;

forall (i in n)
forall (j in n: j != i)
forall (k in m)
c2: C[i][k] + TaskTime[j][k] <= C[j][k] + 10000 * (1 - X[i][j]);
}

I have implemented the same model in other solvers and the problem is solved without any issue.

It is numerically safer to use a (small) data-dependent value for $$M$$. For your case, rewrite as:

C[i][k] + TaskTime[j][k] - C[j][k] <= M[i][j][k] * (1 - X[i][j]);

You want to choose $$M_{i,j,k}$$ to be a (small) upper bound on the left hand side when $$X_{i,j}=0$$. A good choice is $$M_{i,j,k} = U_{i,k} + T_{j,k} - L_{j,k},$$ where $$U_{i,k}$$ is a good upper bound on $$C_{i,k}$$ and $$L_{j,k}$$ is a good lower bound (0?) on $$C_{j,k}$$.

• Thanks for your help. I agree data-dependent values of M will help in terms of efficiency, however, I am wondering why the model cannot be solved with the fixed value. In the example in the OP, there are only two jobs and three machines, but no particular value for M results in solving the instance. Jan 8 '20 at 3:16
• To diagnose infeasibility, I recommend fixing the variables from a known solution and seeing which constraints are violated. Jan 8 '20 at 3:20

with CPLEX 12.10 your model gives a solution with objective 3

If you prefer not to use big M, you could use logical constraints and rewrite

forall (k in m)
c2: C[i][k] + TaskTime[j][k] <= C[j][k] + 10000 * (1 - X[i][j]);

into

forall (k in m)
c2b:(X[i][j]==1) => (C[i][k] + TaskTime[j][k] <= C[j][k]);

But even better, within OPL CPLEX I encourage you to have a look at the CPOptimizer solver that could tackle your problem even faster.

• Thanks Alex. This really helps. I also found out that I can use logical or to rewrite the constraint. Which one do you recommend? Jan 9 '20 at 6:56