Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
Expand all | Collapse all

objective is not convexe :error 5002

  • 1.  objective is not convexe :error 5002

    Posted 01/12/17 08:53 AM

    Originally posted by: Rym


    Hi

    I tried to create a model for my problem but i have as a result an "objective is not convex"

     

     

    dvar boolean lumda[V][P];
    dexpr int cpuc[j in P]= cpum-(sum(i in V,j in P) lumda[i][j]*cpui[i]);
    dexpr int ramc[j in P]= ramm-(sum(i in V,j in P) lumda[i][j]*rami[i]);
    dexpr int diskc[j in P]= diskm-(sum(i in V,j in P) lumda[i][j]*diski[i]);
    dexpr int R1[j in P]=cpuc[j];
    dexpr int R2[j in P]=ramc[j];
    dexpr int R3[j in P]=diskc[j];
    dexpr int R[i in D,j in P]=(i==1)?R1[j]:((i==2)?R2[j]:(R3[j]));
    dexpr int minx[j in P] = minl(cpuc[j],(minl(ramc[j],diskc[j])));
    dvar boolean phy[P];
    dexpr int O = sum( i in V, j in P) lumda[i][j];
    dexpr int RW = sum (i in V,j in P,l in D,k in D:l!=k) (R[j][l]-min(k in 1..3)(R[j][k]));
    minimize RW;


    //constraint

    subject to{ 
    //une machine virtuelle est hébergée par au plus une seule pm
      limit:
       forall( i in V)
         sum( j in P ) lumda[i][j] <= 1;
        

    //la quantité de cpu consommée par les vms ne depasse la la quantité de cpu de la pm j
       cpur:
          forall( j in P)
           sum( i in V) cpui[i]*lumda[i][j] <= cpuj[j];
            

    //la quantité de ram consommée par les vms ne depasse la la quantité de ram de la pm j
        ramr:
         forall( j in P)
           sum( i in V) rami[i]*lumda[i][j] <= ramj[j];

    //la quantité de disk consommée par les vms ne depasse la la quantité de disk de la pm 

        diskr: 
         forall( j in P)
           sum( i in V) diski[i]*lumda[i][j] <= diskj[j];
           
         

     

     

    dvar boolean lumda[V][P];

    dvar boolean phy[P];
    dexpr int cpuc[j in P]= cpum-(sum(i in V,j in P) lumda[i][j]*cpui[i]);
    dexpr int ramc[j in P]= ramm-(sum(i in V,j in P) lumda[i][j]*rami[i]);
    dexpr int diskc[j in P]= diskm-(sum(i in V,j in P) lumda[i][j]*diski[i]);
    dexpr int R1[j in P]=cpuc[j];
    dexpr int R2[j in P]=ramc[j];
    dexpr int R3[j in P]=diskc[j];
    dexpr int R[i in D,j in P]=(i==1)?R1[j]:((i==2)?R2[j]:(R3[j]));
    dexpr int minx[j in P] = minl(cpuc[j],(minl(ramc[j],diskc[j])));
    dexpr int O = sum( i in V, j in P) lumda[i][j];
    dexpr int RW = sum (j in P,l in D,k in D:l!=k) phy[j]*(R[j][l]-min(k in 1..3)(R[j][k]));
    minimize RW;


    //constraint

    subject to{ 
    //une machine virtuelle est hébergée par au plus une seule pm
      limit:
       forall( i in V)
         sum( j in P ) lumda[i][j] <= 1;
        

    //la quantité de cpu consommée par les vms ne depasse la la quantité de cpu de la pm j
       cpur:
          forall( j in P)
           sum( i in V) cpui[i]*lumda[i][j] <= cpuj[j];
            

    //la quantité de ram consommée par les vms ne depasse la la quantité de ram de la pm j
        ramr:
         forall( j in P)
           sum( i in V) rami[i]*lumda[i][j] <= ramj[j];

    //la quantité de disk consommée par les vms ne depasse la la quantité de disk de la pm 

        diskr: 
         forall( j in P)
           sum( i in V) diski[i]*lumda[i][j] <= diskj[j];

          
    //quand est ce que pm prends un

        phyone:
          forall ( i in V, j in P)
          lumda[i][j]<= phy[j] ;

    //quand est ce que pm prends zero

        phynull:
          forall (j in P)
             phy[j]<= sum (i in V) lumda[i][j];}
            

    Thanks


    #DecisionOptimization
    #MathematicalProgramming-General


  • 2.  Re: objective is not convexe :error 5002

    Posted 01/12/17 08:56 AM

    Hi,

    if you post your .mod and .dat other users will be able to help you

    regards


    #DecisionOptimization
    #MathematicalProgramming-General


  • 3.  Re: objective is not convexe :error 5002

    Posted 01/12/17 05:09 PM

    Originally posted by: Rym


    The .mod is attatched bellow

    /*********************************************
     * OPL 12.6.3.0 Model
     * Author: Regaieg
     * Creation Date: 11 janv. 2017 at 11:36:52
     *********************************************/


    int v = 10;
    range V = 1..v;
    int p=5;
    int d=3;
    range P = 1..p;
    range D = 1..d;
    int cpui[V];
    int rami[V];
    int diski[V];
    int cpuj[P];
    int ramj[P];
    int diskj[P];
    int VMmin=1;
    int VMmax=4;
    int cpum=21;
    int ramm=40;
    int diskm=1000;
    string S[VMmin..VMmax]=["s","m","l","xl"];
    {string} VMTypes={S[v] | v in VMmin..VMmax};
    int VM[i in V]=1+(rand() % (4 - 1+ 1));
    string vms[i in V]=S[VM[i]];
    tuple PM
    {
      int npm;
      string nvm;
      }

     
    {PM} indexes={<i,j> | i in P,j in VMTypes}; 


    int countPVX[indexes];
    execute VMS
    {
    var ofilevms = new IloOplOutputFile("resvmss.txt");
     writeln("vms=",vms);
    for (var i in vms)
    { ofilevms.write("'",vms[i],"',");

    if(vms[i]=="s")

      {
       cpui[i]=1;
       rami[i]=2;
       diski[i]=50;

       }
       
     else if(vms[i]=="m")
     {
       cpui[i]=2;
       rami[i]=4;
       diski[i]=105;
     
        
        }
        
      else if(vms[i]=="l")
      
      { cpui[i]=4;
       rami[i]=7;
       diski[i]=150;

     }   
       else
       
      {
       cpui[i]=8;
       rami[i]=14;
       diski[i]=250 ;

       
       } 
       
       
    }
    writeln(cpui);
    writeln(rami);
    writeln(diski);

    };


    execute PMS
    {
     

    for (var i in P)


       cpuj[i]=21;
       ramj[i]=40;
       diskj[i]=1000;
       
       }

       

    writeln(cpuj);
    writeln(ramj);
    writeln(diskj);

    };
     

     

    //the model/problem definition

    dvar boolean lumda[V][P];
    dvar int R[P][D];
    dexpr float cpuc[j in P]= (cpum-(sum(i in V,j in P) lumda[i][j]*cpui[i]))/21;
    dexpr float ramc[j in P]= (ramm-(sum(i in V,j in P) lumda[i][j]*rami[i]))/40;
    dexpr float diskc[j in P]= (diskm-(sum(i in V,j in P) lumda[i][j]*diski[i]))/1000;
    dexpr float minx[j in P] = minl(cpuc[j],(minl(ramc[j],diskc[j]))); 
    dexpr int mini[j in P]=(minx[j]==cpuc[j])*(1) +(minx[j]==ramc[j])*(2)+(3)*(minx[j]==diskc[j]);
    dexpr float RW = sum (j in P,l in D) sum(minij in 1..3) (minij==mini[j])*(R[j][l]-R[j][minij]);
    minimize RW;


    //constraint

    subject to{ 
    //une machine virtuelle est hébergée par au plus une seule pm
      limit:
       forall( i in V)
         sum( j in P ) lumda[i][j] <= 1;
        

    //la quantité de cpu consommée par les vms ne depasse la la quantité de cpu de la pm j
       cpur:
          forall( j in P)
           sum( i in V) cpui[i]*lumda[i][j] <= cpuj[j];
            

    //la quantité de ram consommée par les vms ne depasse la la quantité de ram de la pm j
        ramr:
         forall( j in P)
           sum( i in V) rami[i]*lumda[i][j] <= ramj[j];

    //la quantité de disk consommée par les vms ne depasse la la quantité de disk de la pm 

        diskr: 
         forall( j in P)
           sum( i in V) diski[i]*lumda[i][j] <= diskj[j];
           
         
    //la somme des vms hebergèes ne depasse pas le nombre des demandes satisfaites

         //glob:
         //fo-((fo*10)/100) <= sum (i in V, j in P) lumda[i][j];
         
         // glob:
      //fo <= sum (i in V, j in P) lumda[i][j];
          
    //quand est ce que pm prends un
    /*
        phyone:
          forall ( i in V, j in P)
          lumda[i][j]<= phy[j] ;

    //quand est ce que pm prends zero

        phynull:
          forall (j in P)
             phy[j]<= sum (i in V) lumda[i][j];*/
             
             
             }
            


    execute
    {

    writeln(R);
    }
     


    #DecisionOptimization
    #MathematicalProgramming-General


  • 4.  Re: objective is not convexe :error 5002

    Posted 01/13/17 04:54 AM

    Hi,

    what you could do is use CPO and write "using CP;" at the beginning of your .mod

    Or you could use CPLEX, see tutu.mod

    where I turned

    //dexpr float cpuc[j in P]= (cpum-(sum(i in V) lumda[i][j]*cpui[i]))/21;
    //dexpr float ramc[j in P]= (ramm-(sum(i in V) lumda[i][j]*rami[i]))/40;
    //dexpr float diskc[j in P]= (diskm-(sum(i in V) lumda[i][j]*diski[i]))/1000;

    into

    dvar float cpuc[j in P];
    dvar float ramc[j in P];
    dvar float diskc[j in P];

    regards

     

     


    #DecisionOptimization
    #MathematicalProgramming-General


  • 5.  Re: objective is not convexe :error 5002

    Posted 01/13/17 08:06 AM

    Originally posted by: Rym


    Not working, the problem in cpuc[P], ramc[P],  diskc[P] . They are set as an assignment and not an equality. 


    #DecisionOptimization
    #MathematicalProgramming-General


  • 6.  Re: objective is not convexe :error 5002

    Posted 01/13/17 08:32 AM

    Hi,

    I object: it works much better. You do not get a solution but it works better.

    If you add some bounds to R like

    dvar int R[P][D] in 1..3;

    then you will get a solution.

    regards


    #DecisionOptimization
    #MathematicalProgramming-General


  • 7.  Re: objective is not convexe :error 5002

    Posted 01/16/17 02:21 AM

    I think your problem comes from the fact that you are using the truth value of the expression minij==mini[j] and multiply this with a variable. This results in a quadratic objective (product of two variables) which is not convex. I think you can replace

    dexpr float RW = sum (j in P,l in D) sum(minij in 1..3) (minij==mini[j])*(R[j][l]-R[j][minij]);

    by this construct

    dvar float replace[1..3][P][D];
    dexpr float RW = sum (j in P,l in D) sum(minij in 1..3) replace[minij][j][l];

    and these additional constraints

      forall(j in P,l in D) {
        forall (minij in 1..3) {
          mini[j] == minij => replace[minij][j][l] == (R[j][l]-R[j][minij]);
          mini[j] <= minij - 1 => replace[minij][j][l] == 0;
          mini[j] >= minij + 1 => replace[minij][j][l] == 0;        
        }
      }

    I am not sure I got everything right but you should get the idea: don't use the truth value of mini[j]==minij in the expression, instead explicitly force some auxiliary variable in case mini[j]==minij.


     


    #DecisionOptimization
    #MathematicalProgramming-General


  • 8.  Re: objective is not convexe :error 5002

    Posted 01/16/17 10:48 AM

    Originally posted by: Rym


    i tried the correction , but it gives unbounded solution.

     

     


    #DecisionOptimization
    #MathematicalProgramming-General


  • 9.  Re: objective is not convexe :error 5002

    Posted 01/16/17 11:45 AM

    When I run CPLEX for some time on the modified problem I indeed see a lot of unbounded nodes but eventually CPLEX finds a feasible solution with objective 0.

    Can you put some (potentially large) bounds on the R variables? Or force them to be non-negative? At first glance it looks odd that these variables have no bounds and do not appear in any constraint (but I did not try to understand your model in detail).

    Edit: More precisely, can you define a bound

    int bound = ...;

    so that you can write

    dvar int R[P][D] in 0..bound;

    Then you can also write

    dvar float replace[1..3][P][D] in -bound..bound;

    and your model will no longer have unbounded nodes. The smaller the bound, the better, I would guess.


    #DecisionOptimization
    #MathematicalProgramming-General


  • 10.  Re: objective is not convexe :error 5002

    Posted 01/16/17 12:02 PM

    And by the way, as far as I can tell, your model is unbounded as soon as there is a feasible solution with RW<0. In that case you can for example just multiply all R variables by 10 (they are not bounded and do not appear in any constraint) to get solution with objective of value 10*RW. Since RW<0 this is better than the previous solution.

    So maybe there is something missing in your model?


    #DecisionOptimization
    #MathematicalProgramming-General


  • 11.  Re: objective is not convexe :error 5002

    Posted 01/17/17 05:45 AM

    Originally posted by: Rym


    Hi, 

    Thanks for this long explication, but can you explain me the meaning of this block:

     

      forall(j in P,l in D) {
        forall (minij in 1..3) {
          mini[j] == minij => replace[minij][j][l] == (R[j][l]-R[j][minij]);
          mini[j] <= minij - 1 => replace[minij][j][l] == 0;
          mini[j] >= minij + 1 => replace[minij][j][l] == 0;        
        }
      }

     

    The problem now is ,When I run my model I obtain the correct result but that obtained by the engine is diffrent from my objective function ( My R is bounded)

     

    The model  before your suggestion

     

    dvar boolean lumda[V][P];
    dexpr int O = sum( i in V, j in P) lumda[i][j];
    dvar float R[P][D] in 0..1;
    dexpr float minx[j in P] = minl(R[j][1],(minl(R[j][2],R[j][3]))); 
    dexpr int mini[j in P]=(minx[j]==R[j][1])*(1)+((minx[j]==R[j][2])&&(abs(minx[j]-R[j][1])>=epsilon))*(2)+((minx[j]==R[j][3])&&(abs(minx[j]-R[j][1])>=epsilon)&&(abs(minx[j]-R[j][2])>=epsilon))*(3);
    dexpr float RW = sum (j in P,l in D) sum(minij in 1..3) (minij==mini[j])*(R[j][l]-R[j][minij]);
    minimize RW;

     

    subject to{ 


    //une machine virtuelle est hébergée par au plus une seule pm
      limit:
       forall( i in V)
         sum( j in P ) lumda[i][j] <= 1;
        


       
    forall(j in P)
      {
    res1: R[j][1]==(cpum-(sum(i in V) lumda[i][j]*cpui[i]))/cpum;

    res2 :R[j][2]==(ramm-(sum(i in V) lumda[i][j]*rami[i]))/ramm;

    res3: R[j][3]==(diskm-(sum(i in V) lumda[i][j]*diski[i]))/diskm;


    //la quantité de cpu consommée par les vms ne depasse pas la quantité de cpu de la pm j
       cpur:
          forall( j in P)
           sum( i in V) cpui[i]*lumda[i][j] <= cpuj[j];
            

    //la quantité de ram consommée par les vms ne depasse pas la quantité de ram de la pm j
        ramr:
         forall( j in P)
           sum( i in V) rami[i]*lumda[i][j] <= ramj[j];

    //la quantité de disk consommée par les vms ne depasse pas la quantité de disk de la pm 

        diskr: 
         forall( j in P)
           sum( i in V) diski[i]*lumda[i][j] <= diskj[j];
           

    }

     

    The result in the script journal : 

    // solution (optimal) with objective -1.1
    lumda=  [[0 1]
             [0 1]
             [0 1]
             [1 0]
             [1 0]]
    R = [[0.4 0.4 0.6]
             [0 0 0.35]]
    minx=  [0.4 0]
    mini=  [1 1]
    RW=0.55

    --> The RW is different from the result of CPLEX engine

    Ps: the formula of objective function is the following : 

    M   D

    ∑   ∑  (Rjl −Rjk), l ̸= k;

    j=1 l=1

    May be CPLEX engine calculates the RW by the following way

    RW= //the first line of R//((0.4-.0.4)+(0.4-0.6)+(0.4-0.4)+(0.4-0.6))+//the second line for R// ((0-0.35)+(0-0)+(0-0.35)= -1.1

     

     

    After your suggestion ( the file is attatched below)

     

    The result is always 0 but it's not necessary to have a zero RW in each instance. Thanks

     

     

     

     

     


    #DecisionOptimization
    #MathematicalProgramming-General


  • 12.  Re: objective is not convexe :error 5002

    Posted 01/18/17 12:57 PM

    This smells like a bug. Of course, the objective value reported in the engine log and in the solution browser should match the value for RW printed. I have filed a bug report for this.

    However, something seems odd with your model:

    As far as I can tell, lumda=0 is always a feasible solution. Constraints diskr, cpur, ramr, limit are trivially satisfied (the left-hand side is 0). Constraints resX will force R[j][X]=1. Hence all values in R will be 1 and thus the objective value for this solution is 0.

    On the other hand, the expression RW is a sum over non-negative elements (the expression "(minij==mini[j])*(R[j][l]-R[j][minij])" is always >=0 as far as I understand your model), so any feasible solution will have an objective >=0. Consequently, lumda=0 is always an optimal solution to your model.

    Did I miss anything or are you missing a constraint that would force at least some lumda to be different from 0?

    Assuming I did not miss anything, a solution value of -1.1 reported in the scripting log seems very odd since the objective should always be non-negative.

    Finally, the objective function formula you stated above looks quite different from RW in your .mod. Why do you need this mini and minij in your .mod? It does not appear in your formula.


    #DecisionOptimization
    #MathematicalProgramming-General


  • 13.  Re: objective is not convexe :error 5002

    Posted 01/19/17 03:43 PM

    Originally posted by: Rym


    Thanks for this long explication

     

    Yes A zero is an optimal solution for my model, so i must add a new constraint to oblige CPLEX to accept more Lumda and so the RW will be different from ZERO. Thanks


    #DecisionOptimization
    #MathematicalProgramming-General


  • 14.  Re: objective is not convexe :error 5002

    Posted 01/20/17 07:01 AM

    Once you have fixed that, you may also want to consider the following alternative (but equivalent) formulation of your model:

    You use the mini[j] expression to indicate which of the R[j][*] values is the minimal value. You have correctly coded this up using logical constraints and the minl() function. The same thing could also be formulated more directly by enumerating the 3 possible values for mini[j]:

    dvar float minx[P];
    dvar int mini[P] in 1..3;

      forall (j in P) {
        mini[j] == 1 => R[j][1] <= R[j][2];
        mini[j] == 1 => R[j][1] <= R[j][3];
        mini[j] == 1 => minx[j] == R[j][1];

        mini[j] == 2 => R[j][2] <= R[j][1];
        mini[j] == 2 => R[j][2] <= R[j][3];
        mini[j] == 2 => minx[j] == R[j][2];
        mini[j] == 2 => R[j][2] <= R[j][1] - epsilon;
        
        mini[j] == 3 => R[j][3] <= R[j][1];
        mini[j] == 3 => R[j][3] <= R[j][2];
        mini[j] == 3 => minx[j] == R[j][3];
        mini[j] == 3 => R[j][3] <= R[j][1] - epsilon;
        mini[j] == 3 => R[j][3] <= R[j][2] - epsilon;
      }

    When I tried this here, it seemed to work better than your formulation. Since minx[j] is smaller than any R[j][*], it may also help in general to add the constraint minx[j]<=R[j][l] for each l in D. This constraint is implied by your formulation but is sort of "hidden" in the logical constraints. Stating it explicitly seemed to help performance a little here (though I did not run a lot of tests).


    #DecisionOptimization
    #MathematicalProgramming-General


  • 15.  Re: objective is not convexe :error 5002

    Posted 01/20/17 07:09 AM

    Originally posted by: Rym


    I tried the follwing modfication

     

       dvar boolean lumda[V][P];
        dexpr int O = sum( i in V, j in P) lumda[i][j];
        dvar float R[P][D] in 0..1;
        dvar float ro[P] in 0..1;
        dexpr float RW = sum (j in P,l in D) (!(R[j][l]==ro[j]))*(R[j][l]-ro[j]);
        minimize RW;

     

    Subject to 

    {

     

    ubject to{ 

    //une machine virtuelle est hébergée par au plus une seule pm
      limit:
       forall( i in V)
         sum( j in P ) lumda[i][j] <= 1;
     
    //la somme des vms hebergèes ne depasse pas le nombre de demandes satisfaites

       /* forall(j in P) (mini[j]==1)==(minx[j]==R[j][1]);
        forall(j in P) (mini[j]==2)==((minx[j]==R[j][2]) && !(minx[j]==R[j][1]));
        forall(j in P) (mini[j]==3)==((minx[j]==R[j][3]));*/
    forall(j in P) 
    {cv:

    R[j][1]==(cpum-(sum(i in V) lumda[i][j]*cpui[i]))/cpum;
    R[j][2]==(ramm-(sum(i in V) lumda[i][j]*rami[i]))/ramm;
     R[j][3]==(diskm-(sum(i in V) lumda[i][j]*diski[i]))/diskm;

    }

       
    //la quantité de cpu consommée par les vms ne depasse pas la quantité de cpu de la pm j
       cpur:
          forall( j in P)
           sum( i in V) cpui[i]*lumda[i][j] <= cpuj[j];
            

    //la quantité de ram consommée par les vms ne depasse pas la quantité de ram de la pm j
        ramr:
         forall( j in P)
           sum( i in V) rami[i]*lumda[i][j] <= ramj[j];

    //la quantité de disk consommée par les vms ne depasse pas la quantité de disk de la pm 

        diskr: 
         forall( j in P)
           sum( i in V) diski[i]*lumda[i][j] <= diskj[j];  
           
            forall(j in P,k in D)
    { cps: ro[j]<=R[j][k];


      
     fo: v<=sum(i in V,j in P) lumda [i][j];
    }

     

    The performance now is more better by the reduction of the exeution time. But i hoped that the fo (number of lumda to be fixed)  will be generate automatically.

     


    #DecisionOptimization
    #MathematicalProgramming-General


  • 16.  Re: objective is not convexe :error 5002

    Posted 01/21/17 01:34 PM

    Sorry, I don't understand. What do you mean you hoped that fo would be generated automatically?


    #DecisionOptimization
    #MathematicalProgramming-General