There are lots of variations on DEA, and I am not an expert, but last year I wrote a small program to solve a basic DEA problem, wherein we solve a series of LP problems, one for each Decision Making Unit. Maybe this could be done entirely in GNU MathProg, but the way I did it was to use the C API to GLPK. The code and a sample problem are attached. The sample problem is the one for automobile dealerships presented in Paul Williams book "Model Building in Mathematical Programming".
Maybe this example will be helpful to someone. dea.mod is the model in Mathprog dea.c solves the series of LPs auto.dat is the sample data from Willams' book makefile is to help with compilation Darin On Sun, Jan 08, 2012 at 08:40:45PM +0300, Andrew Makhorin wrote: > -------- Forwarded Message -------- > From: Amogh Tolay <[email protected]> > To: [email protected] > Subject: Using GLPK for DEA > Date: Sun, 8 Jan 2012 20:35:18 +0530 > > Dear Sir/Madam > > > I have been trying to use GLPK to solve a Data Envelopment Problem using > the CCR model. I am a novice and I was unable to find the way to > implement such problems with GLPK. It would be great if you could help > me out! The problem is to find the CCR efficiency of a two-input and > two-output problem which is something as follows: > Labels: A B C D > Input1: 20, 19, 25, 27 > Input2: 151, 131, 160, 168 > > > Output1: 100, 150, 160, 180 > Output2: 90, 50, 55, 72 > > > I need to maximize the efficiency and find the corresponding weights. > That is, I need to apply the CCR model with variable weights to optimize > this problem. Thus, for Label A, the set of equations are: > (where u1, u2 are the weights for inputs of A and v1, v2 are the weights > for outputs of A.) > > > maximize 100v1+90v2; > > > subject to: > 20u1+151u2=1; > 100v1+90v2<=20u1+151u2; > 150v1+50v2<=19u1+131u2; > 160v1+55v2<=25u1+160u2; > 180v1+72v2<=27u1+168u2; > > > where u1, u2, v1 and v2 are all greater than 0. > > > I haven't been able to figure out as to how to implement this problem > using GLPK without converting it to Standard Form. Is it necessary to > convert such equations to Standard Form before using GLPK? If so, can > you please guide me to convert such problems into a format that GLPK can > handle? > I tried searching for documentation for such problems, but unfortunately > I couldnt find anything. If I am missing some online > resources/documentations which specifically deal with such problems, I > would be glad if you could point them out to me. > It would be really kind of you if you could help a novice like me. :) > > Thank You > -------- > Amogh > > > > _______________________________________________ > Help-glpk mailing list > [email protected] > https://lists.gnu.org/mailman/listinfo/help-glpk
auto.dat
Description: MOPAC data
/*
* A program to perform Data Envelopment Analysis. The problem
* formulation is read from a GMPL model in the file dea.mod.
* This program solves the LP for each DMU and collects the resulting
* information
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <glpk.h>
/* given a string of the form "inputs[space]", return a string of the form "space" */
char *pretty(char *name) {
char *beg, *end;
beg = strchr(name, '[');
end = strchr(name, ']');
if (beg == NULL || end == NULL)
return NULL;
else {
*end = '\0';
return beg+1;
}
}
int main(void) {
glp_prob *lp;
glp_tran *tran;
int ret, ret1;
int i, j, colw, n, m;
int *ind, *ind1;
double *val, *val1;
int num_outputs;
char symbol[50];
char *sep = ",";
FILE *of;
lp = glp_create_prob();
tran = glp_mpl_alloc_wksp();
ret = glp_mpl_read_model(tran, "dea.mod", 1);
if (ret != 0) {
fprintf(stderr, "Error on translating model\n");
goto skip;
}
ret = glp_mpl_read_data(tran, "totpt.dat");
if (ret != 0) {
fprintf(stderr, "Error on translating data\n");
goto skip;
}
ret = glp_mpl_generate(tran, NULL);
if (ret != 0) {
fprintf(stderr, "Error on generating model\n");
goto skip;
}
glp_mpl_build_prob(tran, lp);
ret = glp_write_prob(lp, 0, "dea.txt"); /* write the problem in GLPK LP/MIP format */
if (ret != 0)
fprintf(stderr, "Error when writing problem\n");
n = glp_get_num_rows(lp);
m = glp_get_num_cols(lp);
ind = calloc(n, sizeof(int));
val = calloc(n, sizeof(double));
ind1 = calloc(n, sizeof(int));
val1 = calloc(n, sizeof(double));
glp_create_index(lp);
colw = glp_find_col(lp, "w"); /* column number for column w */
ret1 = glp_get_mat_col(lp, colw, ind1, val1); /* store the column for w */
num_outputs = ret1 - 1; /* there is one nonzero entry for w itself */
/* open the output file and print the header */
of = fopen("totpt.csv", "w");
fprintf(of, "dmu"); fprintf(of, sep);
fprintf(of, "efficiency"); fprintf(of, sep);
for (i = 1; i <= n; ++i) {
if (glp_get_row_type(lp, i)==GLP_LO || glp_get_row_type(lp, i)==GLP_UP) {
strcpy(symbol, glp_get_row_name(lp, i));
fprintf(of, "%s", pretty(symbol));
if (i < n) fprintf(of, sep);
}
}
fprintf(of, "\n");
/* solve the LP for each DMU */
for (j = 1; j <= m; ++j) {
if (strcmp(glp_get_col_name(lp, j), "w")==0) continue;
ret = glp_get_mat_col(lp, j, ind, val); /* store the column for the dmu represented by column j */
for (i = 1; i <= num_outputs; ++i)
val1[i] = -val[i];
glp_set_mat_col(lp, colw, ret1, ind1, val1); /* set the new output coefficients in the column for w */
/* set the new RHS, i.e. the new input coefficients */
for (i = 1; i <= n; ++i) {
if (glp_get_row_type(lp, i) == GLP_UP) /* only want rows corresponding to inputs */
glp_set_row_bnds(lp, i, GLP_UP, 0.0, val[ind[i]]); /* set the new RHS for the input constraints */
}
glp_simplex(lp, NULL);
strcpy(symbol,glp_get_col_name(lp, j));
fprintf(of, "%s", pretty(symbol)); /* DMU name */
fprintf(of, sep);
fprintf(of, "%f", 1/glp_get_obj_val(lp)); /* efficiency number */
fprintf(of, sep);
for (i = 1; i <= n; ++i) { /* weights obtained as the dual values */
if (glp_get_row_type(lp, i)==GLP_UP) {
fprintf(of, "%f", glp_get_row_dual(lp, i));
if (i < n) fprintf(of, sep);
}
if (glp_get_row_type(lp, i)==GLP_LO) { /* a nonzero dual value will be negative here */
fprintf(of, "%f", -glp_get_row_dual(lp, i));
if (i < n) fprintf(of, sep);
}
}
fprintf(of, "\n");
}
fclose(of);
skip: glp_mpl_free_wksp(tran);
glp_delete_prob(lp);
return 0;
}
# Data Envelopment Analysis following the formulation given
# in Williams, "Model Building in Mathematical Programming".
#
set DMU;
set Input;
set Output;
param ipar {DMU, Input};
param opar {DMU, Output};
param k symbolic in DMU;
var w >= 1;
var x {DMU} >= 0;
maximize z: w;
s.t. inputs {i in Input}: sum {j in DMU} ipar[j,i]*x[j] <= ipar[k,i];
s.t. outputs {i in Output}: sum {j in DMU} opar[j,i]*x[j] >= opar[k,i]*w;
dea.o: dea.c
gcc -c -g dea.c
dea: dea.o
gcc dea.o -o dea -lglpk -lm -L/usr/local/lib
clean:
rm -f *.o dea
_______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
