Originally posted by: SystemAdmin

[ph mooraa said:]

Hi all,

I am writing a CPLEX optimization program for job scheduler. In every time slot only a certain jobs can be scheduled simultaneously and objective is to minimize time slots (t) needed for completing all jobs.

Every time slot is a 2-d array (matrix) and third dimension (t) is optimized by filling more and more jobs in every time slot while obeying certain constraints. here is the code -

IloModel mymodel(env1);
                typedef IloArray<IloNumVarArray> NumVarMatrix;
                typedef IloArray<NumVarMatrix> NumVar3Matrix;

                NumVar3Matrix sched(env1,4);

                IloNumVar t(env1,0,IloInfinity,ILOINT);

                for(int p=0;p<4;p++) {<br />                        sched [p] = NumVarMatrix(env1,4);
                        for(int j=0;j<4;j++) {<br />                                sched [p][j] = IloNumVarArray(env1,t);        /*error*/
                                for(int k=0;k<t;k++) {<br />                                        sched [p][j][k] = IloNumVar(env1,0,1,ILOINT);
                                }
                        }
                }

This gives me errors while defining the 3rd dimension. My problem is I am trying to define an array of a certain size t which itself is a decision variable.

How to do so? Is there a way to "not" mention size of the array because it is what you are optimizing?

Any help would be really appreciated.

Thanks, phm
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[ph mooraa said:]

I think I presented my question in a rather complicated way..

My question is how do I define an array in such a way that its size itself is optimized.

I have -

IloNumVar t(env1,0,IloInfinity,ILOINT); I want to minimize "t" which in turn is the size of an array. I use this array in constraints.

How do I do it?

Thanks, phm
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

The model that's handed off to the solver will need to have fixed size arrays.  So you'll need to declare the array with outer dimension T, where T is a valid (constant) upper bound for t.

Let's say I've got a variable vector x (I'll stick to one dimension for simplicity), and I want to minimize the needed dimension of x, which I assume equates to minimizing the number of nonzero entries.  I declare x to have constant dimension T.  Let's also assume that x[j] is nonnegative and has known upper bound U[j].  Then I can declare binary variables y[1]...y[T] and add the following constraints to the model:

x[j] <= U[j]*y[j] (j=1,...,T)<br />t >= j*y[j] (j=1,...,T)

Minimizing t will minimize the number of nonzero entries in x (and also compel them to be restricted to the first t rows of x).

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[ph mooraa said:]

Hi Paul,

I really appreciate your reply. Thanks.

I think what you mean by these constraints are sort of understandable to me in 1 dimension. But I am not able to clarify it in more dimensions. It will be great if you please see the following code snippet -

                IloModel mymodel(env1);
IloCplex mycplex(mymodel);

typedef IloArray<IloNumVarArray> NumVarMatrix;
typedef IloArray<NumVarMatrix> NumVar3Matrix;

NumVar3Matrix sched(env1,4);

[b]IloInt T=100;[/b]
IloNumVar t(env1,0,1000,ILOINT);
                                                                                /*(part 1) 3D array initialization*/
for(int i=0;i<4;i++) {<br /> sched[ i] = NumVarMatrix(env1,4);
for(int j=0;j<4;j++) {<br /> sched[ i][j] = IloNumVarArray[b](env1,T)[/b];
for(int k=0;k<[b]T[/b];k++) {
sched[ i][j][k] = IloNumVar(env1,0,1,ILOINT);
}
}
}

                ...
                // file read in DO[26][4]
                // file read in A[4][4]
                ...

                mymodel.add(IloMinimize(env1,t));              /*obective*/

for(IloInt m=0;m<4;m++) {                       /*constraint - 1*/
for (IloInt n=0;n<4;n++) {<br /> IloExpr r(env1);
for(IloInt o=0;[b]o<mycplex.getValue(t);[/b]o++) {
r+=sched[m][n][ o];                                   
}
mymodel.add(r==A[m][n]);                          /*meeting the total requirements over all slots*/
}
}

for(IloInt x=0;[b]x<mycplex.getValue(t)[/b];x++) {                /*constraint - 2*/
for(IloInt y=0;y<26;y++) {                                    /*there are 26 conflicts*/
mymodel.add(sched[DO[y][0]][DO[y][1]][ x] + sched[DO[y][2]][DO[y][3]][ x] <= 1);      /*only one or none is scheduled*/<br /> }
}

mycplex.solve();

the achieved job schedule is represented as 3D array. Basically it is an array of matrices where each matrix represent every time slot. Every time slot (matrix) is J x J where J (currently 4 as above) is total number of workers. Each job requires 2 workers ij and when it is scheduled that ij element of t th slot is set to 1, otherwise 0. This way 4 x 4 x t cube is all binary and objective is to minimize t.

Total job requirement to met in t slots are mentioned as constraint 1 in A[4][4] matrix. There are conflict between workers and only one out of certain pairs of workers can be scheduled in the same slot. This is mentioned in DO matrix in constraint 2 as (W1,W2)(W3,W4). This shows that either W1,W2 or W3,W4 pair can be scheduled in the same time slot.

Issue 1- Both the constraints require use of 3rd dimension (t) while mentioning the constraints. Currently I am doing this with mycplex.getValue(t) which I think might also be causing problems.

Issue 2- The first constraint you explained is sort of implicit as upper bound in this 3D array is 1 only. But I am not sure how to add the "shrinking" constraint where t scheduled time slots will be at the start.

Current output of the program (after adding T) says no solution exists.

Any pointers would be really helpful. I am not sure what I am doing wrong.
Thanks once again.




#CPLEXOptimizers
#DecisionOptimization