GAMS/DEA modeling via GUSS

	[ Home \| Support \| Sales \| Solvers \| Documentation \| Model Libraries \| Search \| Contact Us ]

GAMS/DEA

DEA Modeling in GAMS via GUSS

Data Envelopment Analysis (DEA) models can be solved most efficiently in GAMS using the Gather-Update-Solve-Scatter (GUSS) facility. This is the preferred method since release 23.7 of GAMS and hence the GAMS/DEA solver is no longer available.

A paper with the title "GUSS: Solving Collections of Data Related Models within GAMS" that contains two additional application examples for GUSS is available here.

The GUSS documentation can be found here.

Introduction

The basic (CCR) DEA model is a collection of models indexed by k and defined by

(2)	max_u,v	u^TY_*,k	(objective slice)
	subject to		v^TX_*,k = 1	(slice constraint)
		u^TY <= v^TX	(core constraint)
		u,v >= 0	(core constraint)

where X,Y are data matrices.

Without using GUSS in GAMS, a model would be defined and solved in a loop over k, requiring the model to be generated multiple times with different instances for each value of k. GUSS is an alternative (and more efficient) way to define the individual programs and pass them to any underlying GAMS solver. In this way, individual programs are not re-generated, but are instead defined as data modifications of each other. This reduces overall model generation time. Further, previous solutions can be used as starting points in later solves to speed up overall processing time.

Some DEA examples compare the two formulations. The actual source code for both of these formulations is available here.

DEA Examples

Original GAMS formulation (without GUSS): In all these models the model setup and data are given at the top of the file and the code of interest is in the last 10 or so lines. In this setting we loop over the set k and change the data in the objective function and the first constraint of the model explicitly before each solve. We only output a minimal summary of the solution.

$title Data  Envelopment Analysis - DEA

$ontext
Data Envelopment Analysis (DEA) is a technique for measuring the relative
performance of organizational units where presence of multiple inputs and
outputs makes comparison difficult.

            efficiency = weighted sum of output / weighted sum of input

Find weights that maximize the efficiency for one unit while ensuring
that no other units has an efficiency < 1 using these weights. A primal
and dual formulation is presented.


Dyson, Thanassoulis, and Boussofiane, A DEA Tutorial.
Warwick Business School

$offtext

Sets  i     units / Depot1*Depot20 /
      j     inputs and outputs / stock, wages, issues, receipts, reqs /
      ji(j) inputs             / stock, wages                         /
      jo(j)            outputs /               issues, receipts, reqs /;
alias(i,k);


Table data(i,j)
         stock  wages  issues  receipts  reqs
Depot1     3      5      40       55      30
Depot2     2.5    4.5    45       50      40
Depot3     4      6      55       45      30
Depot4     6      7      48       20      60
Depot5     2.3    3.5    28       50      25
Depot6     4      6.5    48       20      65
Depot7     7     10      80       65      57
Depot8     4.4    6.4    25       48      30
Depot9     3      5      45       64      42
Depot10    5      7      70       65      48
Depot11    5      7      45       65      40
Depot12    2      4      45       40      44
Depot13    5      7      65       25      35
Depot14    4      4      38       18      64
Depot15    2      3      20       50      15
Depot16    3      6      38       20      60
Depot17    7     11      68       64      54
Depot18    4      6      25       38      20
Depot19    3      4      45       67      32
Depot20    3      6      57       60      40
;

Parameter slice(j) slice of data
          eff_k(i)  efficiency report;

Positive variables v(ji) input weights
                   u(jo) output weights;

Variable eff efficiency;


Equations defe    efficiency definition - weighted output
          denom   weighted input
          lime(i) 'output / input < 1';

defe..    eff =e= sum(jo, u(jo)*slice(jo));

denom..   sum(ji, v(ji)*slice(ji)) =e= 1;

lime(i).. sum(jo, u(jo)*data(i,jo)) =l= sum(ji, v(ji)*data(i,ji));

model dea /defe, denom, lime /;

set headers / modelstat, solvestat, objval /;
parameter rep(k,headers) solution report summary;
option limrow=0, limcol=0, solprint=silent,
       solvelink=%Solvelink.LoadLibrary%;
loop(k,
  slice(j) = data(k,j);
  solve dea using lp max eff;
  rep(k,'modelstat') = dea.modelstat;
  rep(k,'solvestat') = dea.solvestat;
  rep(k,'objval'   ) = dea.objval;
);
display rep;

The DEA problem formulated using GUSS: In this setting, the solve statement includes an extra keyword scenario that points to a new set called dict. The contents of this set are directives to GUSS that state the scenario index is k, the parameter slice is populated from the parameter data and the values of the variable eff are stored into the parameter eff_k for each scenario solved. More details follow below.

$title Data Envelopment Analysis - DEA Sets i units / Depot1*Depot20 / j inputs and outputs / stock, wages, issues, receipts, reqs / ji(j) inputs / stock, wages / jo(j) outputs / issues, receipts, reqs /; alias(i,k); Table data(i,j) stock wages issues receipts reqs Depot1 3 5 40 55 30 Depot2 2.5 4.5 45 50 40 Depot3 4 6 55 45 30 Depot4 6 7 48 20 60 Depot5 2.3 3.5 28 50 25 Depot6 4 6.5 48 20 65 Depot7 7 10 80 65 57 Depot8 4.4 6.4 25 48 30 Depot9 3 5 45 64 42 Depot10 5 7 70 65 48 Depot11 5 7 45 65 40 Depot12 2 4 45 40 44 Depot13 5 7 65 25 35 Depot14 4 4 38 18 64 Depot15 2 3 20 50 15 Depot16 3 6 38 20 60 Depot17 7 11 68 64 54 Depot18 4 6 25 38 20 Depot19 3 4 45 67 32 Depot20 3 6 57 60 40 ; Parameter slice(j) slice of data eff_k(i) efficiency report; Positive variables v(ji) input weights u(jo) output weights; Variable eff efficiency; Equations defe efficiency definition - weighted output denom weighted input lime(i) 'output / input < 1'; defe.. eff =e= sum(jo, u(jo)*slice(jo)); denom.. sum(ji, v(ji)*slice(ji)) =e= 1; lime(i).. sum(jo, u(jo)*data(i,jo)) =l= sum(ji, v(ji)*data(i,ji)); model dea /defe, denom, lime /; set headers report / modelstat, solvestat, objval /; parameter scenrep(k,headers) solution report summary scopt / SkipBaseCase 1 /; set dict / k .scenario.'' slice .param. data eff .level. eff_k scopt .opt. scenrep /; slice(j) = 0; option lp=cplexd; solve dea using lp max eff scenario dict; display scenrep,eff_k;

In the GUSS version we indicate the collection of models to be solved using the set dict. The first element of dict determines the set to be used for the scenario (collection) index, in this case k. The second element of dict then details that in each scenario k, the parameter slice is instantiated using a slice of the parameter data. Essentially, this corresponds to the GAMS statement:

slice(j) = data(k,j)

Note the scenario index k must appear as the first index of the parameter data. The third element of dict allows the modeler to collect information from each solve and store it into a GAMS parameter. Essentially, the third element of dict corresponds to the GAMS statement:

eff_k(k) = eff.l

that gets executed immediately after the solve of scenario k.

More complex scenario models can also be formulated using GUSS, including multiple equations being updated. This is shown by the dual of the basic DEA model, given by

(3) min_z,lambda z (objective)

subject to X*lambda <= zX_*,k (slice constraint)

Y*lambda >= Y_*,k (slice constraint)

lambda >= 0 (core constraint)
The next example compares the two formulations for this model. The actual source code for both of these formulations is available here.

Original GAMS formulation (without GUSS):

$title Data Envelopment Analysis - DEA (traditional) sets i units / Depot1*Depot20 / j inputs and outputs / stock, wages, issues, receipts, reqs / ji(j) inputs / stock, wages / jo(j) outputs / issues, receipts, reqs /; alias(k,i); Table data(i,j) stock wages issues receipts reqs Depot1 3 5 40 55 30 Depot2 2.5 4.5 45 50 40 Depot3 4 6 55 45 30 Depot4 6 7 48 20 60 Depot5 2.3 3.5 28 50 25 Depot6 4 6.5 48 20 65 Depot7 7 10 80 65 57 Depot8 4.4 6.4 25 48 30 Depot9 3 5 45 64 42 Depot10 5 7 70 65 48 Depot11 5 7 45 65 40 Depot12 2 4 45 40 44 Depot13 5 7 65 25 35 Depot14 4 4 38 18 64 Depot15 2 3 20 50 15 Depot16 3 6 38 20 60 Depot17 7 11 68 64 54 Depot18 4 6 25 38 20 Depot19 3 4 45 67 32 Depot20 3 6 57 60 40 ; parameter slice(j) slice of data eff_k(i) efficiency report; Variables z efficiency lam(i) dual weights; positive variables lam; Equations dii(ji) input duals dio(jo) output dual; * dual model dii(ji).. sum(i, lam(i)*data(i,ji)) =l= z*slice(ji); dio(jo).. sum(i, lam(i)*data(i,jo)) =g= slice(jo); model deadc dual with CRS / dii, dio /; parameter rep summary report; option limrow=0, limcol=0, solprint=silent, lp=cplexd, solvelink=%Solvelink.LoadLibrary%; loop(k, slice(j) = data(k,j); solve deadc using lp minimizing z ; rep(k,'modelstat') = deadc.modelstat; rep(k,'solvestat') = deadc.modelstat; rep(k,'objval') = deadc.objval; ); display rep;

Dual (CRS) DEA model formulated using GUSS: The key modeling statements occur in the last 10 lines below.

$title Data Envelopment Analysis - DEA (dual,GUSS) sets i units / Depot1*Depot20 / j inputs and outputs / stock, wages, issues, receipts, reqs / ji(j) inputs / stock, wages / jo(j) outputs / issues, receipts, reqs /; alias(k,i); Table data(i,j) stock wages issues receipts reqs Depot1 3 5 40 55 30 Depot2 2.5 4.5 45 50 40 Depot3 4 6 55 45 30 Depot4 6 7 48 20 60 Depot5 2.3 3.5 28 50 25 Depot6 4 6.5 48 20 65 Depot7 7 10 80 65 57 Depot8 4.4 6.4 25 48 30 Depot9 3 5 45 64 42 Depot10 5 7 70 65 48 Depot11 5 7 45 65 40 Depot12 2 4 45 40 44 Depot13 5 7 65 25 35 Depot14 4 4 38 18 64 Depot15 2 3 20 50 15 Depot16 3 6 38 20 60 Depot17 7 11 68 64 54 Depot18 4 6 25 38 20 Depot19 3 4 45 67 32 Depot20 3 6 57 60 40 ; parameter slice(j) slice of data eff_k(i) efficiency report; Variables z efficiency lam(i) dual weights; positive variables lam; Equations dii(ji) input duals dio(jo) output dual; * dual model dii(ji).. sum(i, lam(i)*data(i,ji)) =l= z*slice(ji); dio(jo).. sum(i, lam(i)*data(i,jo)) =g= slice(jo); model deadc dual with CRS / dii, dio /; set headers report / modelstat, solvestat, objval /; parameter scenrep(k,headers) solution report summary scopt / SkipBaseCase 1 /; set dict / k. scenario.'' scopt. opt. scenrep slice. param. data z. level. eff_k /; slice(j) = 0; option lp=cplexd; solve deadc using lp min z scenario dict; display scenrep,eff_k;

Extensions of these models to formulations with weighted outputs or variable returns to scale are easy to formulate with the scenario solver within GAMS. This extended model can be downloaded here.

The DEA model in the model library is similar to the extended model, but does not make use of GUSS.

GUSS Options

The execution of GUSS can be parameterized using some options. Options are not passed through a solver option file but via another tuple in the dict set. The keyword in the second position of this tuple is opt. A one dimensional parameter is expected in the first position (or the label ''). This parameter may contain some of the following labels with values:

OptfileInit: Option file number for the first solve

Optfile: Option file number for subsequent solves

LogOption: Determines amount of log output
0 - Moderate log (default)
1 - Minimal log
2 - Detailed log

SkipBaseCase: Switch for solving the base case (0 solves the base case)

UpdateType: Determines amount of log output
0 - Set everything to zero and apply changes (default)
1 - Reestablish base case and apply changes
2 - Build on top of last scenario and apply changes

Restart Type: Determines restart point for the scenarios
0 - Restart from last solution (default)
1 - Restart from solution of base case
2 - Restart from input point

For the DEA model the UpdateType setting would mean:

UpdateType=0:  loop(s, A(i,j) = A_s(s,i,j))
UpdateType=1:  loop(s, A(i,j) = A_base(i,j); A(i,j) $= A_s(s,i,j))
UpdateType=2:  loop(s, A(i,j) $= A_s(s,i,j))

The option SkipBaseCase=1 allows to skip the base case. This means only the scenarios are solved and there is no solution reported back to GAMS in the traditional way. The third position in the opt-tuple can contain a parameter for storing the scenario solution status information, e.g. model and solve status, or needs to have the label ''. The labels to store solution status information must be known to GAMS, so one needs to declare a set with such labels. The following solution status labels can be reported:

domusd     iterusd   objest      nodusd      modelstat   numnopt
numinfes   objval    resusd      robj        solvestat   suminfes

The following example shows how to use some of the GUSS options and the use of a parameter to store some solution status information:

Set h solution headers / modelstat, solvestat, objval /; Parameter o / SkipBaseCase 1, UpdateType 1, Optfile 1 / r_s(s,h) Solution status report; Set dict / s. scenario. '' o. opt. r_s a. param. a_s x. lower. xlo_s x. level. xl_s e. marginal. em_s /; solve mymodel min z using lp scenario dict;