Decision Optimization

 View Only
Expand all | Collapse all

Data Envelopment Analysis (DEA) in OPL

ALEX FLEISCHER

ALEX FLEISCHERFri October 28, 2016 12:27 PM

  • 1.  Data Envelopment Analysis (DEA) in OPL

    Posted Fri October 28, 2016 12:27 PM

    Hi,

     

    DEA is a very useful tool for efficiency analysis : https://en.wikipedia.org/wiki/Data_envelopment_analysis

    "Data envelopment analysis (DEA) is a nonparametric method in operations research and economics for the estimation of production frontiers. It is used to empirically measure productive efficiency of decision making units (or DMUs). Although DEA has a strong link to production theory in economics, the tool is also used for benchmarking in operations management, where a set of measures is selected to benchmark the performance of manufacturing and service operations."

    Good tutorial at http://mat.gsia.cmu.edu/classes/QUANT/NOTES/chap12.pdf

    Let me share here a tiny OPL model that can help compute efficiency for any data set:

    .mod

    int nbDMU=...;
     
     int nbInputs= ...;
     int nbOutputs=...;
     
     range DMU=1..nbDMU;
     range Input=1..nbInputs;
     range Output=1..nbOutputs;
     
     // Input
     float X[DMU][Input]=...;
     // Output
     float Y[DMU][Output]=...;
     
     int refDMU=...; // We want to measure efficiency of that DMU
     
     assert refDMU in DMU;
     
     dvar float+ theta;
     dvar float+ lambda[DMU];
     
     minimize theta;
     
     subject to
     {
     
     forall(j in Input)  
         ctInput:
             sum(i in DMU) (lambda[i]*X[i][j]) <= theta*X[refDMU][j];
     forall(j in Output)
         ctOutput:
             sum(i in DMU) (lambda[i]*Y[i][j]) >= Y[refDMU][j];
             
     }
     
     execute
     {
     writeln("theta= ",theta);
     if (theta==1) writeln("Efficient DMU");
     else writeln("Not efficient DMU");
     writeln("lambda=",lambda);
     writeln();
     }
     
     // Loop to measure efficiency for all DMU
     main
     {
     thisOplModel.generate();
     
     for(var dmu in thisOplModel.DMU)
     {
         writeln("DMU",dmu);
         for(j in thisOplModel.Input) thisOplModel.ctInput[j].setCoef(thisOplModel.theta,-thisOplModel.X[dmu][j]);
         for(j in thisOplModel.Output) thisOplModel.ctOutput[j].LB=thisOplModel.Y[dmu][j];
         cplex.solve();
         thisOplModel.postProcess();
         
     }
     
     }
     

    .dat

    nbDMU=3;

    refDMU=1;

    nbInputs=2;
    nbOutputs=3;

    X=[[5 14][8 15][7 12]];
    Y=[[9 4 16][5 7 10][4 9 13]];

    which gives

    DMU1
    theta= 1
    Efficient DMU
    lambda= [1 0 0]

    DMU2
    theta= 0.773333333
    Not efficient DMU
    lambda= [0.26154 0 0.66154]

    DMU3
    theta= 1
    Efficient DMU
    lambda= [0 0 1]

    NB: changing the .dat is enough to adapt to any data set

     

    Alex Fleischer

    PS:

    Many how to with OPL at https://www.linkedin.com/pulse/how-opl-alex-fleischer/

    Many examples from a very good book : https://www.linkedin.com/pulse/model-building-oplcplex-alex-fleischer/

    Making optimization simple : https://www.linkedin.com/pulse/making-decision-optimization-simple-alex-fleischer/



  • 2.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Sun October 30, 2016 07:56 AM

    Originally posted by: KatyaY


    Good start for DEA users in OPL: radial input-oriented DEA model developed by  CharnesCooper & Rhodes (1978)



  • 3.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Thu November 10, 2016 11:32 AM

    And with this model we can solve the Efficiency Analysys example from Model Building in Mathematical Programming by H.P. Williams.

    Newbury is still an efficient garage:

    DMU6 Garage Newbury
    theta= 1
    Efficient DMU
    lambda= [0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

    regards

     

    Attachment(s)

    mod
    deahp.mod   1 KB 1 version
    dat
    HP.dat   1 KB 1 version


  • 4.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Sun November 13, 2016 03:33 AM

    Originally posted by: KatyaY


    Free DEA tutorials for beginners:

    http://deazone.com/en/resources/tutorial

    http://deafrontier.net/whatisdea.html

     



  • 5.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Thu February 02, 2017 03:05 PM

    Thanks. Let me quote Banker, Charnes and Cooper:

    In management contexts, mathematical programming is usually used to evaluate a collection of possible alternative courses of action en route to selecting one which is best. In this capacity, mathematical programming serves as a planning aid to management. Data Envelopment Analysis reverses this role and employs mathematical programming to obtain ex post facto evaluations of the relative efficiency of management accomplishments, however they may have been planned or executed. Mathematical programming is thereby extended for use as a tool for control and evaluation of past accomplishments as well as a tool to aid in planning future activities

     



  • 6.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Fri November 17, 2017 04:05 AM

    Originally posted by: Galih Pambudi


    Good afternoon Mr. AlexFleischer, I'm Galih Pambudi, I would like to ask about DEA applied in OPL, I have tried using your suggest as above using looping program and I have a problem when I want to convert the results in spreadsheet automatically, the results cannot be shows every DMU, they just shows the latest DMU and have error while processing

     

    Thank you

     

    warm regards



  • 7.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Fri November 17, 2017 04:18 AM

    Hi,

    the SheetWrite you wrote in the .dat will write into the same cells for all DMUs I guess. You should make sure you change line when you move to a new DMU.

    regards

    PS: See https://www.ibm.com/developerworks/community/forums/html/topic?id=b84f0aff-970f-4c26-a2aa-41614b08c560



  • 8.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Tue November 28, 2017 06:36 AM


  • 9.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Sun April 07, 2019 04:11 AM

    Originally posted by: wuguancen


     hi,Mr AlexFleischer

    Would you please explain a problem in the Loop ?

    when i run your model.

    there is a problem:
    Not a model element "j", use 'var' to declare local scripting variables.    

     

    how can i think and resolve it ?

    thank you !



  • 10.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Sun April 07, 2019 04:47 AM

    Hi,

    only a warning. If you change

    for(j in thisOplModel.Input) thisOplModel.ctInput[j].setCoef(thisOplModel.theta,-thisOplModel.X[dmu][j]);

    to

    for(var j in thisOplModel.Input) thisOplModel.ctInput[j].setCoef(thisOplModel.theta,-thisOplModel.X[dmu][j]);

    the warning should go away

    regards



  • 11.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Mon April 08, 2019 10:23 PM

    Originally posted by: wuguancen


    yes,it did.

    I really appreciate your help. 

    Thank you!



  • 12.  RE: Re: Data Envelopment Analysis (DEA) in OPL

    Posted Wed January 26, 2022 10:56 AM
    Hi,
    Really valuable information. Thank you for sharing.

    ------------------------------
    louis adele
    ------------------------------



  • 13.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Mon January 15, 2018 12:46 PM

    Originally posted by: Nathalia R.


    Hi, Mr Alex. Would you please explain the Loop ?



  • 14.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Mon January 15, 2018 02:50 PM

    Hi

    // Loop to measure efficiency for all DMU
     main
     {
     thisOplModel.generate();
     
     for(var dmu in thisOplModel.DMU)
     {
         writeln("DMU",dmu," Garage ",Opl.item(thisOplModel.garage,dmu-1).name_garage);
         for(j in thisOplModel.Input) thisOplModel.ctInput[j].setCoef(thisOplModel.theta,-thisOplModel.X[dmu][j]);
         for(j in thisOplModel.Output) thisOplModel.ctOutput[j].LB=thisOplModel.Y[dmu][j];
         cplex.solve();
         thisOplModel.postProcess();
         
     }
     
     }

    I wrote a loop for all DMU and then for each DMU

    for(j in thisOplModel.Input) thisOplModel.ctInput[j].setCoef(thisOplModel.theta,-thisOplModel.X[dmu][j]);

    sets in constraint ctInput[j] the multiplier of theta to -thisOplModel.X[dmu][j]


    for(j in thisOplModel.Output) thisOplModel.ctOutput[j].LB=thisOplModel.Y[dmu][j];

    sets in constraint ctOutput[j] the lower bound to Y[dmu][j]

    For a simpler example of incremental changes see

    https://www.ibm.com/developerworks/community/forums/html/topic?id=0289cdc7-a237-4442-91f3-9c8e2944a8a7&ps=25

    in

    https://www.linkedin.com/pulse/how-opl-alex-fleischer/

    regards

     

     



  • 15.  Re: Data Envelopment Analysis (DEA) in OPL

    Posted Mon October 01, 2018 11:46 PM

    Originally posted by: Galih Pambudi


    Greeting Sir, could you help me to make a loop from maximize DEA model
    Warm Regard

    maximize sum (j in Output) v[refDMU][j]*Y[refDMU][j];

    //constraints
    subject to 
    {
      forall (d in DMU) 
      u_input : sum ( i in Input) u[d][i]*X[d][i]==1;
      
      forall (j in Output, i in Input, d in DMU)
       v_output : 
       sum (j in Output) v[d][j]*Y[d][j]-sum(i in Input) u[d][i]*X[d][i]<=0;
      
      forall (j in Output, d in DMU)
         nonnegativity : v[d][j]>=0;
         forall (i in Input, d in DMU)
         u[d][i]>=0;
    }



  • 16.  Re: Data Envelopment Analysis (DEA) in OPL



  • 17.  RE: Re: Data Envelopment Analysis (DEA) in OPL

    Posted Fri February 18, 2022 02:28 PM
    Dear Mister Fleischer,

    i read the example and tried to develop a new loop for the DEA primal model. But it does not work.
    Could you help me please??




    int nbDMU=...;
    int refDMU=...; // We want to measure efficiency of that DMU
    int nbInputs= ...;
    int nbOutputs=...;


    // Ranges
    range DMU=1..nbDMU;
    range Input=1..nbInputs;
    range Output=1..nbOutputs;

    // Parameters

    float X[DMU][Input] = ...; // valores dos inputs compartilhados do estagio k no periodo t
    float Y[DMU][Output] = ...;//valores das saídas do estagio do estagio k no periodo t

    assert refDMU in DMU;

    // Variables
    dvar float+ v[Input];
    dvar float+ u[Output];

    dexpr float eff = sum(i in Input) (v[i] * X[refDMU][i]);

    minimize eff ;

    subject to{

    //restricao linear
    CtLinear:sum(j in Output) (u[j]*Y[refDMU][j]) == 1;

    forall(n in DMU) //restricao inputs compartilhados
    CtSistema:sum(j in Output) (u[j]* Y[n][j]) - sum(i in Input)(v[i] * X[n][i])<= 0;

    forall (i in Input)
    CtNaonegatividadeInput: v[i]>=0;

    forall (j in Output)
    CtNaonegatividadeOutput: u[j]>=0;

    }

    execute
    {
    writeln("efficiency ",eff);
    writeln("v=",v);
    writeln("u=",u);
    writeln();
    }

    main{
    thisOplModel.generate();

    for(var dmu in thisOplModel.DMU)
    {
    writeln("DMU",dmu);
    for(var j in thisOplModel.Output) thisOplModel.CtLinear[j].setCoef(thisOplModel.u[j],thisOplModel.Y[dmu][j]);
    cplex.solve();
    thisOplModel.postProcess();

    }
    }

    ------------------------------
    Livia Torres
    ------------------------------



  • 18.  RE: Re: Data Envelopment Analysis (DEA) in OPL

    Posted Mon February 21, 2022 04:08 AM
    Hi,

    first, I would rewrite your constraint into

    CtLinear: (u[1]*Y[refDMU][1])+(u[2]*Y[refDMU][2])+(u[3]*Y[refDMU][3]) ==1;​

    because if you have a sum you won t be able to use setCoef

    and then in the flow control

    for(var j in thisOplModel.Output) thisOplModel.CtLinear.setCoef(thisOplModel.u[j],thisOplModel.Y[dmu][j]);
    


    since ctLinear is not an array but a constraint.

    So what works fine:

    .mod

    int nbDMU=...;
    int refDMU=...; // We want to measure efficiency of that DMU
    int nbInputs= ...;
    int nbOutputs=...;
    
    
    // Ranges
    range DMU=1..nbDMU;
    range Input=1..nbInputs;
    range Output=1..nbOutputs;
    
    // Parameters
    
    float X[DMU][Input] = ...; // valores dos inputs compartilhados do estagio k no periodo t
    float Y[DMU][Output] = ...;//valores das saídas do estagio do estagio k no periodo t
    
    assert refDMU in DMU;
    
    // Variables
    dvar float+ v[Input];
    dvar float+ u[Output];
    
    dexpr float eff = sum(i in Input) (v[i] * X[refDMU][i]);
    
    minimize eff ;
    
    subject to{
    
    //restricao linear
    CtLinear: (u[1]*Y[refDMU][1])+(u[2]*Y[refDMU][2])+(u[3]*Y[refDMU][3]) ==1;
    
    
    forall(n in DMU) //restricao inputs compartilhados
    CtSistema:sum(j in Output) (u[j]* Y[n][j]) - sum(i in Input)(v[i] * X[n][i])<= 0;
    
    forall (i in Input)
    CtNaonegatividadeInput: v[i]>=0;
    
    forall (j in Output)
    CtNaonegatividadeOutput: u[j]>=0;
    
    }
    
    execute
    {
    writeln("efficiency ",eff);
    writeln("v=",v);
    writeln("u=",u);
    writeln();
    }
    
    main{
    thisOplModel.generate();
    
    for(var dmu in thisOplModel.DMU)
    {
    writeln("DMU",dmu);
    for(var j in thisOplModel.Output) thisOplModel.CtLinear.setCoef(thisOplModel.u[j],thisOplModel.Y[dmu][j]);
    cplex.solve();
    thisOplModel.postProcess();
    
    }
    }


    .dat

    nbDMU=3;
    
        refDMU=1;
    
        nbInputs=2;
        nbOutputs=3;
    
        X=[[5 14][8 15][7 12]];
        Y=[[9 4 16][5 7 10][4 9 13]];


    PS:

    Many other examples in Model Building



    ------------------------------
    [Alex] [Fleischer]
    [EMEA CPLEX Optimization Technical Sales]
    [IBM]
    ------------------------------



  • 19.  RE: Re: Data Envelopment Analysis (DEA) in OPL

    Posted Tue February 22, 2022 09:20 PM
    Dear Mister Alex Fleischer,

    First, I would like to thank you for your comments. I appreciate it, and it worked.
    I realized that another "for" was necessary to change the coefficients in the objective function, and I wrote it here in case other colleagues might need it.
    I'm sorry to bother you again, but I have another question. Is it possible to write the loop for a generic formulation? Because when we write the objective function and this Linear constraint in this manner, if we want to use this model for another instance, we must rewrite it. Therefore, the use of sum(i in Input) v[i]*X[refDMU][i] would be better than v[1]*X[refDMU][1]+ v[2]*X[refDMU][2].
    Thank you again and i look forward for your reply.

    Lívia Torres

    ------------------------------
    Livia Torres
    ------------------------------



  • 20.  RE: Re: Data Envelopment Analysis (DEA) in OPL

    Posted Tue February 22, 2022 09:22 PM
    int nbDMU=...;
    int refDMU=...; // We want to measure efficiency of that DMU
    int nbInputs= ...;
    int nbOutputs=...;


    // Ranges
    range DMU=1..nbDMU;
    range Input=1..nbInputs;
    range Output=1..nbOutputs;

    // Parameters

    float X[DMU][Input] = ...; // valores dos inputs compartilhados do estagio k no periodo t
    float Y[DMU][Output] = ...;//valores das saídas do estagio do estagio k no periodo t

    assert refDMU in DMU;

    // Variables
    dvar float+ v[Input];
    dvar float+ u[Output];


    minimize v[1]*X[refDMU][1]+ v[2]*X[refDMU][2];

    subject to{

    //restricao linear
    CtLinear:u[1]*Y[refDMU][1] + u[2]*Y[refDMU][2]+ u[3]*Y[refDMU][3] == 1;

    forall(n in DMU) //restricao inputs
    CtSystem:sum(j in Output) (u[j]* Y[n][j]) - sum(i in Input)(v[i] * X[n][i]) <= 0;

    forall (i in Input)
    CtNonnegativeinput: v[i]>=0;

    forall (j in Output)
    CtNonnegativeoutput: u[j]>=0;

    }


    main
    {
    thisOplModel.generate();

    for(var dmu in thisOplModel.DMU)
    {
    writeln("DMU",dmu);
    for(var j in thisOplModel.Input)cplex.setObjCoef(thisOplModel.v[j],thisOplModel.X[dmu][j]);
    for(var i in thisOplModel.Output) thisOplModel.CtLinear.setCoef(thisOplModel.u[i],thisOplModel.Y[dmu][i]);
    cplex.solve();
    writeln("v", thisOplModel.v);
    writeln("u", thisOplModel.u);
    writeln("Solution value = " + cplex.getObjValue());
    thisOplModel.postProcess();

    }

    }


    ------------------------------
    Livia Torres
    ------------------------------



  • 21.  RE: Data Envelopment Analysis (DEA) in OPL

    Posted Wed January 19, 2022 08:01 AM
    Hello,

    I am looking for a similar DEA model in OPL for the weights' formulation. Do you have that?
    Thanks

    ------------------------------
    [Hermilio] [Vilarinho]
    ------------------------------