Originally posted by: SystemAdmin

Dear all,
I am using CPLEX 12.0 Concert/C++ on Win 7 to solve Qudratic Assignment Problem, which has been transformed into a pure IP model in my case.

Since I want to reduce the running time so I want to put two expression objects inside one block of 4-nested-for-loop structure. But I kept get infeasible msg after I ran .exe file at the end. Here are the codes:

int transIndx = 0;
int countT = 0;
// add modified Transformed constrains after getting first feasible solution
for (int i = 0; i < h; i++) {
for (int j = i+1; j < h; j++) {
for (int s = 0; s < l; s++) {
for (int t = s + 1; t < l; t++) {
if ( s >= m[i] - x_DQ*l/h && s <= m[i] + x_DQ*l/h && t >= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h) {
//first expression
IloExpr exprT(env);
exprT = ZtransIndx - X[i][s] - X[j][t]; // Z and X are both IloBoolVar
mod.add( exprT >= -1);
exprT.end();
//another expression
IloExpr exprImP(env);
exprImP = X[i][s] + X[j][t];
mod.add( exprImP <= 1);
exprImP.end();
transIndx++;
}
}
}
}
}

Actually, I can split the above code into two similar 4-nested-for-loop piece of code, which worked as expected, but as I said,I wanted to do the above way because I can save half running time for 4-nested-for-loop
Note that I defined a 1-d IloBoolArray for Z variable with a fixed size("numValid_Z") determined in in the following code already.

IloInt numValid_Z=0;
// count how many valid Z's we would define, so that we can define a 1-dim array for
//IloBoolArray Z(env);
for(int i=0; i<h; i++) {
for(int j=i+1; j<h; j++) {
for(int s=0; s<l; s++) {
for(int t=s+1; t<l; t++) {
if (s >= m[i] - x_DQ*l/h && s <= m[i] + x_DQ*l/h && t>= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h){
//ZnumValid_Z = IloBoolVar(env);
numValid_Z++;
}
}
}
}
}

// instead of defining a 4-dim array for Z's, we define only a 1-dim array for Z with size of total # possible Z's

IloArray<IloBoolVar> Z(env, numValid_Z);
for (int i = 0; i < numValid_Z; i++)
{ Z[i] = IloBoolVar(env);
}
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I just saw that the two indices of Z variable in my previous post were recognized as hyperlinks, which should have been written as ZtransIndx and ZnumValid_Z.

Thanks in advance
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

You probably want to repost using the code tags (look at the box on the right of where you type your response)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you Eumpfenbach for your suggestion. But there is nothing on the right of the typing box.
Let me just try to repost everything again in here:

---

Sorry, everyone! I have to
Dear all,
I am using CPLEX 12.0 Concert/C++ on Win 7 to solve Qudratic Assignment Problem, which has been transformed into a pure IP model in my case.

Since I want to reduce the running time so I want to put two expression objects inside one block of 4-nested-for-loop structure. But I kept get infeasible msg after I ran .exe file at the end. Here are the codes:

int tIndx = 0;
int countT = 0;
// add modified Transformed constrains after getting first feasible solution
for (int i = 0; i < h; i++) {
for (int j = i+1; j < h; j++) {
for (int s = 0; s < l; s++) {
for (int t = s + 1; t < l; t++) {
if ( s >= m[i] - x_DQ*l/h && s <= m[i] + x_DQ*l/h && t >= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h) {
//first expression
IloExpr exprT(env);
exprT = ZtIndx - X[i][s] - X[j][t]; // Z and X are both IloBoolVar
mod.add( exprT >= -1);
exprT.end();
//another expression
IloExpr exprImP(env);
exprImP = X[i][s] + X[j][t];
mod.add( exprImP <= 1);
exprImP.end();
tIndx++;
}
}
}
}
}

Actually, I can split the above code into two similar 4-nested-for-loop piece of code, which worked as expected, but as I said,I wanted to do the above way because I can save half running time for 4-nested-for-loop
Note that I defined a 1-d IloBoolArray for Z variable with a fixed size("numValid_Z") determined in in the following code already.

IloInt numValid_Z=0;
// count how many valid Z's we would define, so that we can define a 1-dim array for
//IloBoolArray Z(env);
for(int i=0; i<h; i++) {
for(int j=i+1; j<h; j++) {
for(int s=0; s<l; s++) {
for(int t=s+1; t<l; t++) {
if (s >= m[i] - x_DQ*l/h && s <= m[i] + x_DQ*l/h && t>= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h){
//ZnumValid_Z = IloBoolVar(env);
numValid_Z++;
}
}
}
}
}

// instead of defining a 4-dim array for Z's, we define only a 1-dim array for Z with size of total # possible Z's

IloArray<IloBoolVar> Z(env, numValid_Z);
for (int i = 0; i < numValid_Z; i++)
{ Z[i] = IloBoolVar(env);
}
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Deanna1125 wrote:
> Thank you Eumpfenbach for your suggestion. But there is nothing on the right of the typing box.
> Let me just try to repost everything again in here:
>

---

> Sorry, everyone! I have to
> Dear all,
> I am using CPLEX 12.0 Concert/C++ on Win 7 to solve Qudratic Assignment Problem, which has been transformed into a pure IP model in my case.
>
> Since I want to reduce the running time so I want to put two expression objects inside one block of 4-nested-for-loop structure. But I kept get infeasible msg after I ran .exe file at the end. Here are the codes:
>
> int tIndx = 0;
> int countT = 0;
> // add modified Transformed constrains after getting first feasible solution
> for (int i = 0; i < h; i++) {
> for (int j = i+1; j < h; j++) {
> for (int s = 0; s < l; s++) {
> for (int t = s + 1; t < l; t++) {
> if ( s >= m[i] - x_DQ*l/h && s <= m[i] + x_DQ*l/h && t >= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h) {
> //first expression
> IloExpr exprT(env);
> exprT = ZtIndx - X[i][s] - X[j][t]; // Z and X are both IloBoolVar
> mod.add( exprT >= -1);
> exprT.end();
> //another expression
> IloExpr exprImP(env);
> exprImP = X[i][s] + X[j][t];
> mod.add( exprImP <= 1);
> exprImP.end();
> tIndx++;
> }
> }
> }
> }
> }
>
> Actually, I can split the above code into two similar 4-nested-for-loop piece of code, which worked as expected, but as I said,I wanted to do the above way because I can save half running time for 4-nested-for-loop
> Note that I defined a 1-d IloBoolArray for Z variable with a fixed size("numValid_Z") determined in in the following code already.
>
> IloInt numValid_Z=0;
> // count how many valid Z's we would define, so that we can define a 1-dim array for
> //IloBoolArray Z(env);
> for(int i=0; i<h; i++) {
> for(int j=i+1; j<h; j++) {
> for(int s=0; s<l; s++) {
> for(int t=s+1; t<l; t++) {
> if (s >= m[i] - x_DQ*l/h && s <= m[i] + x_DQ*l/h && t>= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h){
> //ZnumValid_Z = IloBoolVar(env);
> numValid_Z++;
> }
> }
> }
> }
> }
>
> // instead of defining a 4-dim array for Z's, we define only a 1-dim array for Z with size of total # possible Z's
>
> IloArray<IloBoolVar> Z(env, numValid_Z);
> for (int i = 0; i < numValid_Z; i++)
> { Z[i] = IloBoolVar(env);
> }
Regarding the infeasibility error message when you try to solve the model, that suggests that your code is generating constraints different from the ones you have intended. Try calling IloCplex::exportModel to write out a SAV file of the model. Read it into interactive CPLEX and solve it to the point of infeasibility. Then run CPLEX's conflict refiner to examine the cause of the infeasibility. That will give you a minimal subset of constraints causing the infeasibility. By examining those constraints, you hopefully will be able to determine why the constraints are not what you expected, and then correct your
code.

Regarding performance, I don't think you need to create and destroy those IloExprs with each constraint. Instead of

> IloExpr exprT(env);
> exprT = ZtIndx - X[i][s] - X[j][t]; // Z and X are both IloBoolVar
> mod.add( exprT >= -1);
> exprT.end();

Why not do something replace those 4 lines with just

mod.add(Z[tIndx] - X[i][s] - X[j][t] >= -1);

Furthermore, you might get some additional improvement my creating an IloRangeArray or IloConstraintArray that builds up these constraints, then
add that range array to the model, e.g.

IloRangeArray rng(env);
for(int i=0; i<h; i++) {
for(int j=i+1; j<h; j++) {
for(int s=0; s<l; s++) {
for(int t=s+1; t<l; t++) {
...

rng.add((Z[tIndx] - X[i][s] - X[j][t] >= -1);

)
...
}
}
}
} // end depth 4 nested 4 loop
mod.add (rng);

This might help as well.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you so much for your suggestions,Ed!!! I tried both (not creating&destroying expression and creating range array). it seemed both don't give any improvement in my case. But anyway, your insights are worthy trying.

Also, the following code has to keep expression part, right?

// originally //add modified NotEachLowMatched constrains with only possible non-zero X's involved
for (int t = 0; t < l; t++) {
  IloExpr exprL(env);
  for (int j = 0; j < h; j++) {
          if(t >= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h) {
                        exprL += X[j][t] ;
          }
  }
  mod.add(exprL <= 1);
  exprL.end();
}

Btw, I debugged out the root cause of the infeasibility.
Thx again!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

> Deanna1125 wrote:
> Thank you so much for your suggestions,Ed!!! I tried both (not creating&destroying expression and creating range array). it seemed both don't give any improvement in my case. But anyway, your insights are worthy trying.
Is the model generation time significant relative to the model solve time?

>
> Also, the following code has to keep expression part, right?
>

// originally //add modified NotEachLowMatched constrains with only possible non-zero X's involved > 

for (

int t = 0; t < l; t++) 
{ >   IloExpr exprL(env); >   

for (

int j = 0; j < h; j++) 
{ >          

if(t >= m[j] - x_DQ*l/h && t <= m[j] + x_DQ*l/h) 
{ >                    exprL += X[j][t] ; >           
} >   
} >   mod.add(exprL <= 1); >   exprL.end(); > 
}

>
> Btw, I debugged out the root cause of the infeasibility.
> Thx again!
I'm not sure what you mean by 'keep the expression part'. The code
ends the exprL after calling mod.add. That's fine; IloExprs are passed
to the model by value, so deleting or changing an IloExpr that you passed
to an IloModel will not affect the model. Note that IloExprs differ from
IloExtractables such as IloRanges in this regard. IloRanges are added directly
to the model, and changes to an IloRange will result in a notification to
the extracting algorithm of the change.
#CPLEXOptimizers
#DecisionOptimization