Originally posted by: chrisJia

Hi everyone, here I have a very simple problem but I don't know to implement it using cplex in C# environment. There are N jobs to be processed and the processing time of the i-th job is t(i). There are also a set of time windows W, from which I must choose one time window to start processing a job and one time window to end processing a job. My goal is to minimize the sum of the completion times of all the jobs. 

I think the problem can be modeled as follows:

minimize: sum(i in N)(e(i))

s.t. e(i)-s(i)>=t(i), for all i in N

a(w)x(i,w)<=s(i)<=M(1-x(i,w))+b(w), for all i in N; w in W

a(w)y(i,w)<=e(i)<=M(1-y(1,w))+b(w), for all i in N; w in W

sum(w in W)(x(i,w))=1, for all i in N

sum(w in W)(y(i,w))=1, for all i in N

s(i), e(i)>=0; x(i,w), y(i,w) in {0, 1}

where s(i), e(i) are the processing start and end times for job i, a(w), b(w) are the start and end times of time window w. x(i,w)=1 if job i starts processing in time window w, and y(i,w)=1 if job i finishes processing in time window w. I have implemented the model using concert technology, but as I run the program, I always get infeasibility message from the engine, and I just don't know how to deal with it. The fact is that there exists a lot of feasible solutions for my problem instances. The following is my implementation, can anybody tell me what is wrong with it :)

INumVar[] s = cplex.NumVarArray(N, 0, maxTime, NumVarType.Float); //start time
INumVar[] e = cplex.NumVarArray(N, 0, maxTime, NumVarType.Float); //finish time
INumVar[][] x = new INumVar[N][]; //select a time window to start
INumVar[][] y = new INumVar[N][]; //select a time window to finish
for (int i = 0; i < N; i++)
    {
        x[i] = cplex.NumVarArray(W, 0, 1, NumVarType.Bool);
        y[i] = cplex.NumVarArray(W, 0, 1, NumVarType.Bool);
    }
double M=maxTime;
//constraint 1
for (int i = 0; i < N; i++)
    {
        ILinearNumExpr exp1 = cplex.LinearNumExpr();
        exp1.AddTerm(1, e[i]);
        exp1.AddTerm(-1, s[i]);
        cplex.AddGe(exp1, t(i));
    }
//constraint 2 and 3
for (int i = 0; i < N; i++)
    {
        ILinearNumExpr exp2_1 = cplex.LinearNumExpr();
        ILinearNumExpr exp2_2 = cplex.LinearNumExpr();
        ILinearNumExpr exp3_1 = cplex.LinearNumExpr();
        ILinearNumExpr exp3_2 = cplex.LinearNumExpr();
        
        for (int j = 0; j < W; j++)
            {
                exp2_1.AddTerm(1, s[i]);
                exp2_1.AddTerm(-1 * timeWindows[j][0], x[i][j]);
                cplex.AddGe(exp2_1, 0);
                
                exp2_2.AddTerm(1, s[i]);
                exp2_2.AddTerm(M, x[i][j]);
                cplex.AddLe(exp2_2, M + timeWindows[j][1]);
                
                exp3_1.AddTerm(1, e[i]);
                exp3_1.AddTerm(-1 * timeWindows[j][0], y[i][j]);
                cplex.AddGe(exp3_1, 0);
                
                exp3_2.AddTerm(1, s[i]);
                exp3_2.AddTerm(M, y[i][j]);
                cplex.AddLe(exp2_2, M + timeWindows[j][1]);
            }
    }
//constraint 4 and 5
for (int i = 0; i < N; i++)
    {
        ILinearNumExpr exp4 = cplex.LinearNumExpr();
        ILinearNumExpr exp5 = cplex.LinearNumExpr();
        
        for (int j = 0; j < W; j++)
            {
                exp4.AddTerm(1, x[i][j]);
                exp5.AddTerm(1, y[i][j]);
            }
        cplex.AddEq(exp4, 1);
        cplex.AddEq(exp5, 1);
    }
//objective
ILinearNumExpr obj = cplex.LinearNumExpr();
for (int i = 0; i < N; i++)
    obj.AddTerm(1, e[i]);
cplex.AddMinimize(obj);
cplex.solve();

Any easy way to debug this is to select a known feasible solution and fix all variables to those values (by setting lower bound = upper bound = value for each variable). Run the solver and confirm that it claims infeasibility, then run the conflict refiner to identify a set of constraints and bounds that collectively cannot be satisfied. Assuming your solution really is feasible, at least one of those constraints or bounds contains an error.

Originally posted by: chrisJia

many thanks to Paul, I think I know what's wrong with the implementation now :)