Originally posted by: Rym

 Hi,

I have the following ILP model.

If I give  enough quantity of PDCWB for the first constraint, the model is solved successfully . But if i give insufficient resources for the parameter PDCBW, the model can't be solved. Normally, if there is no enough resources of PDCBW, the model is solved and the result (objective fucntion) is ZERO. Could you help me to solve my problem, please. My be i have wrong constraints

 

I explain a little the model:
I'm looking to maximize the number of accepted VDC requtes. To satisfy a VDC request, we should satisfy all its links' bandwidth requirements, which is represented by the array LR. in other words, an LR of a VDC request takes the form of 
LR=[<1,2>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>,<3,1>,<3,2>,<3,4>,<4,1>,<4,2>,<4,3>];

**the decision variable  lumdabw[N][liaisonp][ND][ND] prensents if the virtual link "l(liaisonp)" of the ith VDC request(N)" is embedded in the physical link "i,j(ND,ND)". 

The model is: 

int n=1;
int p=4;
range N=1..n;
int nd=8;
range ND=1..nd;
range P=1..p;

// the physical link relations
int PDC[1..nd][1..nd]=[ 
                         [0,0,0,0,1,0,0,0],
                         [0,0,0,0,1,0,0,0],
                         [0,0,0,0,0,1,0,0],
                         [0,0,0,0,0,1,0,0],
                         [1,1,0,0,0,0,1,1],
                         [0,0,1,1,0,0,1,1],
                         [0,0,0,0,1,1,0,0],
                         [0,0,0,0,1,1,0,0]
                        
                                   
                   ];
                   
                   
                   ;

int pi[i in N]=3;
tuple edge // link definition
{
int i;
int j;
}
{edge} liaisonp = { <i,j> | i in 1..p,j in 1..p:i!=j};

int LR[N][liaisonp]= [[0, 0, 48, 0, 0, 0, 0, 0, 0, 48, 0, 0]];
int LRb[N][liaisonp]=[[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0]];

 

int PDCBW=10;

 

//Definition of the model
dvar boolean lumdabw[N][liaisonp][ND][ND];
dvar boolean Vd[N];
dexpr int lumdij[i in ND][j in ND]=sum(f in N,l in liaisonp)lumdabw[f][l][i][j]*LR[f][l];
dexpr int maxbw=max(i,j in ND)lumdij[i][j];
dexpr int o= sum(f in N) Vd[f];
maximize o;;

subject to
{

 

//capacity pyhical link constraint
clc:
forall (i in ND, j in ND)
 sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW;

//flow constraint

//flc:

forall(f in N,l in liaisonp,i in ND)
 { (i==l.i) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==LRb[f][l]);
  (i==l.j) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==-LRb[f][l]);
 ((i!=l.i)&&(i!=l.j)) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==0);     
}
 //A virtual link can be embedded into only one physical path(a set of physical links, insplitted paths)
   
   forall(f in N,l in liaisonp,i in ND)
      sum(j in ND)(lumdabw[f][l][i][j])<=1; 
   
 // a virtual link can be embedded into only  a existing  physical link  
  forall(f in N, l in liaisonp,i,j in ND) 
     lumdabw[f][l][i][j]<=PDC[i][j];

  forall(f in N,l in liaisonp,i,j in ND) 
     lumdabw[f][l][i][j]<=LRb[f][l];

// A VDC requests can be satisfied if only all its links' bw requirements are satisfied
     forall(f in N,l in liaisonp)
   sum(j in ND)lumdabw[f][l][l.i][j]<= Vd[f];
}

 

 

execute xss
{
writeln("max=\n",o);       
writeln("Vd",Vd);
}

 

 

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

if you rewrite your physical constraint into

forall (i in ND, j in ND)
 clc:sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW;

then you ll get a relaxed solution and the relaxation is

Line    Original    Relaxed    Element (8)
59    [-Infinity,10]    [-Infinity,48]    clc[1][5]
59    [-Infinity,10]    [-Infinity,48]    clc[4][6]
59    [-Infinity,10]    [-Infinity,48]    clc[5][1]
59    [-Infinity,10]    [-Infinity,48]    clc[5][8]
59    [-Infinity,10]    [-Infinity,48]    clc[6][4]
59    [-Infinity,10]    [-Infinity,48]    clc[6][8]
59    [-Infinity,10]    [-Infinity,48]    clc[8][5]
59    [-Infinity,10]    [-Infinity,48]    clc[8][6]

regards

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Rym

Hi Alex,

 

I didn't catch the difference between my writed constraint and your proposition. Thanks

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

I changed

clc:
forall (i in ND, j in ND)
 sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW;

into

forall (i in ND, j in ND)
 clc:sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW;

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Rym

Always gives me 

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

which cplex version do you use ?

Do you use the IDE ?

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Rym

hi,

I'm using  IBM ILOG CPLEX Optimization Studio 12.6.3 version

#DecisionOptimization
#OPLusingCPLEXOptimizer

Then within the IDE you should see

#DecisionOptimization

Originally posted by: Rym

Hi,

I can't see this result in relaxation table. Is-it strange ? What did you propose ?

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

can you post your entire project ?

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Rym

Hi,

 

you find the projet in attached file. Thanks

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

you use a flow control and the sub model is not feasible.

If you want the relaxation , you could write

subOpl.addDataSource(subData);
//subOpl.applyOpsSettings(null, "C:/Users/rim.regaieg/Desktop/80/259/mix2.ops");
//Generate the second model
subOpl.generate();
 ( subCplex.solve())
    {
    var o=new IloOplOutputFile("dat.dat");     
    o.write(subOpl.printExternalData());
    o.close();
    
    var x=subCplex.getObjValue();
    writeln("the number of accepted VDC requests is",x);
          subOpl.postProcess();
  }

in gen.mod

and then you ll be able to call the sub model and you will get the following relaxation:

Line    Original    Relaxed    Element (4)
75    [-Infinity,0]    [-Infinity,123]    clc[3][4]
75    [-Infinity,0]    [-Infinity,123]    clc[4][3]
92    [-Infinity,0]    [-Infinity,1]    thn#0#8#2#3
92    [-Infinity,0]    [-Infinity,1]    thn#0#11#3#2

 

Let me attach the full project
regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Rym

Hi,

 

the problem that i should find an optimal solution without a relaxation, but i would like to understand what did you mean by  "you use a flow control and the sub model is not feasible. Should I correct the flow control constraints or what did you propose ? 

 

Thanks

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

you got an error because the sub model model2 had no solution.

If in that model you apply the relaxation and change

//capacity link constraint
forall (i in ND, j in ND)
clc:sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW[i][j];

into

//capacity link constraint
forall (i in ND, j in ND)
clc:sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW[i][j]+100;

then you ll get a solution and your flow control (block with keyword "main") will work fine

regards

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Rym

Thanks a lot Alex,

 

Did you have a proposition in modifying some constraints in order to have a feasible submodel, even to have ZERO as an optimal solution and without changing

 

//capacity link constraint
forall (i in ND, j in ND)
clc:sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW[i][j];

to

//capacity link constraint
forall (i in ND, j in ND)
clc:sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW[i][j]+100;

 

 

 

the submodel is:

 

 

int M=10000000000;
int n=1;
int p=4;
range N=1..n;
int nd=8;
range ND=1..nd;

int PDCBW[ND][ND];
int PDC[1..nd][1..nd]=[ 
                         [0,0,0,0,1,0,0,0],
                         [0,0,0,0,1,0,0,0],
                         [0,0,0,0,0,1,0,0],
                         [0,0,0,0,0,1,0,0],
                         [1,1,0,0,0,0,1,1],
                         [0,0,1,1,0,0,1,1],
                         [0,0,0,0,1,1,0,0],
                         [0,0,0,0,1,1,0,0]
                        
                                   
                   ];
                   
                   
                   ;
int PDCBWx=10;
execute xc
{
for (var x=1;x<=nd;x++)
  {
   for(var y=1;y<=nd;y++)
    {
     if(PDC[x][y]==1)
     {
       PDCBW[x][y]= PDCBWx;
      }        
    
   }    
  

}
//writeln("P=",PDCBW);
}

tuple edge // link definition
{
int i;
int j;
}
{edge} liaisonp = { <i,j> | i in 1..p,j in 1..p:i!=j};

int LR[N][liaisonp]=[[0, 0, 48, 0, 0, 0, 0, 0, 0, 48, 0, 0]];
int LRb[N][liaisonp]=[[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0]];

 

//Definition of the model
dvar boolean lumdabw[N][liaisonp][ND][ND];
dvar boolean Vd[N];
dexpr int lumdij[i in ND][j in ND]=sum(f in N,l in liaisonp)lumdabw[f][l][i][j]*LR[f][l];
dexpr int maxbw=max(i,j in ND)lumdij[i][j];
dexpr int o= sum(f in N) Vd[f];
dvar boolean vdf[N];
maximize o;;

subject to
{

 

//capacity link constraint

clc:
forall (i in ND, j in ND)
sum(f in N,l in liaisonp)(lumdabw[f][l][i][j])*LR[f][l]<=PDCBW[i][j];
//flow constraint

flc:

forall(f in N,l in liaisonp,i in ND)
 {(i==l.i) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==LRb[f][l]);
(i==l.j) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==-LRb[f][l]);
((i!=l.i)&&(i!=l.j)) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==0);     
}
 //A virtual link can be embedded into one physical path(a set of physical links)
    rgv:
   forall(f in N,l in liaisonp,i in ND)
     sum(j in ND)(lumdabw[f][l][i][j])<=1; 
   
 // a virtual link can be embedded into only  a existing  physical link  
   thn:
  forall(f in N, l in liaisonp,i,j in ND) 
    lumdabw[f][l][i][j]<=PDC[i][j];

//lumdaBw existe si seulement si LR existe
yhj:
  forall(f in N,l in liaisonp,i,j in ND) 
     lumdabw[f][l][i][j]<=LRb[f][l];

   
   forall(f in N)
  (1/M)*(sum(i,j in ND,l in liaisonp)lumdabw[f][l][i][j])<=Vd[f];
       
}

 

Thanks

#DecisionOptimization
#OPLusingCPLEXOptimizer

Hi,

if you change

//flow constraint

flc:

forall(f in N,l in liaisonp,i in ND)
 {(i==l.i) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==LRb[f][l]);
(i==l.j) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==-LRb[f][l]);
((i!=l.i)&&(i!=l.j)) => ((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==0);     
}

into

//flow constraint

flc:

forall(f in N,l in liaisonp,i in ND)
 {
 
 
 aqw:(i==l.i) <= (((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==LRb[f][l]));
 zdx:(i==l.j) <= (((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==-LRb[f][l]));
edv:((i!=l.i)&&(i!=l.j)) <= (((sum(j in ND) (lumdabw[f][l][i][j])-  sum(j in ND) (lumdabw[f][l][j][i]))==0));     
}

then you ll get another relaxation:

Line    Original    Relaxed    Element (8)
82    [-Infinity,-1]    [-Infinity,0]    aqw[1][<2,4>][2]
82    [-Infinity,-1]    [-Infinity,0]    aqw[1][<4,2>][4]
82    [-Infinity,-1]    [-Infinity,0]    zdx[1][<2,4>][4]
82    [-Infinity,-1]    [-Infinity,0]    zdx[1][<4,2>][2]
82    [-Infinity,-1]    [-Infinity,0]    aqw[1][<2,4>][2]
82    [-Infinity,-1]    [-Infinity,0]    zdx[1][<2,4>][4]
82    [-Infinity,-1]    [-Infinity,0]    zdx[1][<4,2>][2]
82    [-Infinity,-1]    [-Infinity,0]    aqw[1][<4,2>][4]

regards

 

#DecisionOptimization
#OPLusingCPLEXOptimizer

Originally posted by: Rym

Thanks a lot Alex.

 

#DecisionOptimization
#OPLusingCPLEXOptimizer