epscm.gms : eps-Constraint Method for Multiobjective Optimization

Description

The eps-Constraint Method

This is a GAMS implementation of the augmented eps-constraint method
for generating the efficient (Pareto optimal, nondominated) solutions
in multiobjective problems. The eps-constraint method optimizes one of
the objective functions using the remaining objective functions as
constraints, varying their right hand side.

The generated optimal solutions proved to be efficient solutions of
the multiobjective problem under certain conditions.

The eps-constraint method consists of two phases:
1. Creation of the payoff table
2. Use the ranges from the payoff table in order to apply the method

The augmented eps-constraint uses lexicographic optimization in the
construction of the payoff table (in order to secure the Pareto
optimality of the individual optima) and a slightly modified objective
function in order to ensure the production of Pareto optimal (and not
weakly Pareto optimal) solutions. In addition, it performs early exit
from infeasible loops improving the performance of the algorithm in
multi-objective problems with several objective functions.

The algorithm can work also with MIP models. Actually the advantages
of the eps-constraint method over the weighting method are more
apparent for MIP problems where the non supported Pareto optimal
solutions can be produced.

A simplified power generation problem is used to illustrate the
method:

Four types of power generation units are considered in a region,
namely, lignite fired, oil fired, natural gas fired and units
exploiting renewable energy sources (RES) which are mostly small hydro
and wind.  The power generation characteristics of these units are
shown in table pdata.

The yearly demand is 64000 GWh and is characterized by a load duration
curve which can be divided into three type of loads: base load (60%),
medium load (30%) and peak load (10%). The lignite fired units can be
used only for base and middle load, the oil fired units for middle and
peak load, the RES units for base and peak load and the natural gas
fired units for all type of loads. The endogenous sources are lignite
and RES.

We consider three objective functions: the minimization of production
cost, the minimization of CO2 emissions and the minimization of
external dependence (i.e. oil and natural gas) by maximizing the
endogenous energy sources.  The task is to generate the payoff table
and the Pareto optimal (efficient, non-dominated) solutions of the
problem.

Additional information can be found at:

http://www.gams.com/modlib/adddocs/epscm.pdf


Reference

  • Mavrotas, G, Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems. Applied Mathematics and Computation 213, 2 (2009), 455-465.

Small Model of Type : LP


Category : GAMS Model library


Main file : epscm.gms

$title eps-Constraint Method for Multiobjective Optimization (EPSCM,SEQ=319)

$onText
The eps-Constraint Method

This is a GAMS implementation of the augmented eps-constraint method
for generating the efficient (Pareto optimal, nondominated) solutions
in multiobjective problems. The eps-constraint method optimizes one of
the objective functions using the remaining objective functions as
constraints, varying their right hand side.

The generated optimal solutions proved to be efficient solutions of
the multiobjective problem under certain conditions.

The eps-constraint method consists of two phases:
1. Creation of the payoff table
2. Use the ranges from the payoff table in order to apply the method

The augmented eps-constraint uses lexicographic optimization in the
construction of the payoff table (in order to secure the Pareto
optimality of the individual optima) and a slightly modified objective
function in order to ensure the production of Pareto optimal (and not
weakly Pareto optimal) solutions. In addition, it performs early exit
from infeasible loops improving the performance of the algorithm in
multi-objective problems with several objective functions.

The algorithm can work also with MIP models. Actually the advantages
of the eps-constraint method over the weighting method are more
apparent for MIP problems where the non supported Pareto optimal
solutions can be produced.

A simplified power generation problem is used to illustrate the
method:

Four types of power generation units are considered in a region,
namely, lignite fired, oil fired, natural gas fired and units
exploiting renewable energy sources (RES) which are mostly small hydro
and wind.  The power generation characteristics of these units are
shown in table pdata.

The yearly demand is 64000 GWh and is characterized by a load duration
curve which can be divided into three type of loads: base load (60%),
medium load (30%) and peak load (10%). The lignite fired units can be
used only for base and middle load, the oil fired units for middle and
peak load, the RES units for base and peak load and the natural gas
fired units for all type of loads. The endogenous sources are lignite
and RES.

We consider three objective functions: the minimization of production
cost, the minimization of CO2 emissions and the minimization of
external dependence (i.e. oil and natural gas) by maximizing the
endogenous energy sources.  The task is to generate the payoff table
and the Pareto optimal (efficient, non-dominated) solutions of the
problem.

Additional information can be found at:

http://www.gams.com/modlib/adddocs/epscm.pdf


Mavrotas, G, Effective implementation of the eps-constraint method in
Multi-Objective Mathematical Programming problems.
Applied Mathematics and Computation 213, 2 (2009), 455-465.

Keywords: linear programming, eps-constraint method, multiobjective optimization
$offText

$inlineCom [ ]
$eolCom //

$stitle Example Model Definitions
Set
   p       'power generation units' / Lignite, Oil, Gas, RES /
   i       'load areas'             / base, middle, peak     /
   pi(p,i) 'availability of unit for load types' / Lignite.(base,middle)
                                                   Oil.(middle,peak), Gas.set.i
                                                   RES.(base, peak)            /
   es(p)   'endogenous sources'  / Lignite, RES /
   k       'objective functions' / cost, CO2emission, endogenous /;

$set min -1
$set max +1

Parameter dir(k) 'direction of the objective functions'
                 / cost %min%, CO2emission %min%, endogenous %max% /;

Set pheader / capacity, cost, CO2emission /;

Table pdata(pheader,p)
                         Lignite    Oil    Gas    RES
   capacity [GWh]          31000  15000  22000  10000
   cost [$/MWh]               30     75     60     90
   CO2emission [t/MWh]      1.44   0.72   0.45      0;

Parameter
   ad        'annual demand in GWh'          / 64000 /
   df(i)     'demand fraction for load type' / base 0.6, middle 0.3, peak 0.1 /
   demand(i) 'demand for load type in GWh';

demand(i) = ad*df(i);

Variable
   z(k)      'objective function variables';

Positive Variable
   x(p,i)    'production level of unit in load area in GWh';

Equation
   objcost   'objective for minimizing cost in K$'
   objco2    'objective for minimizing CO2 emissions in Kt'
   objes     'objective for maximizing endogenous sources in GWh'
   defcap(p) 'capacity constraint'
   defdem(i) 'demand satisfaction';

* Objective functions
objcost..   sum(pi(p,i), pdata('cost',p)*x(pi)) =e= z('cost');

objco2..    sum(pi(p,i), pdata('CO2emission',p)*x(pi)) =e= z('CO2emission');

objes..     sum(pi(es,i), x(pi)) =e= z('endogenous');

defcap(p).. sum(pi(p,i), x(pi))  =l= pdata('capacity',p);

defdem(i).. sum(pi(p,i), x(pi))  =g= demand(i);

Model example / all /;

$STitle eps-Constraint Method
Set
   k1(k)  'the first element of k'
   km1(k) 'all but the first elements of k';

k1(k)$(ord(k) = 1) = yes;
km1(k)  = yes;
km1(k1) =  no;

Set kk(k) 'active objective function in constraint allobj';

Parameter
   rhs(k)     'right hand side of the constrained obj functions in eps-constraint'
   maxobj(k)  'maximum value from the payoff table'
   minobj(k)  'minimum value from the payoff table';

Variable
   a_objval   'auxiliary variable for the objective function'
   obj        'auxiliary variable during the construction of the payoff table';

Positive Variable
   sl(k)      'slack or surplus variables for the eps-constraints';

Equation
   con_obj(k) 'constrained objective functions'
   augm_obj   'augmented objective function to avoid weakly efficient solutions'
   allobj     'all the objective functions in one expression';

con_obj(km1).. z(km1) - dir(km1)*sl(km1) =e= rhs(km1);

* We optimize the first objective function and put the others as constraints
* the second term is for avoiding weakly efficient points
augm_obj.. sum(k1,dir(k1)*z(k1)) + 1e-3*sum(km1,sl(km1)/(maxobj(km1) - minobj(km1))) =e= a_objval;

allobj..   sum(kk, dir(kk)*z(kk)) =e= obj;

Model
   mod_payoff    / example, allobj /
   mod_epsmethod / example, con_obj, augm_obj /;

option limRow = 0, limCol = 0, solPrint = off, solveLink = %solveLink.CallModule%;

Parameter payoff(k,k) 'payoff tables entries';

Alias (k,kp);

* Generate payoff table applying lexicographic optimization
loop(kp,
   kk(kp) = yes;
   repeat
      solve mod_payoff using lp maximizing obj;
      payoff(kp,kk) = z.l(kk);
      z.fx(kk)      = z.l(kk); // freeze the value of the last objective optimized
      kk(k++1)      = kk(k);   // cycle through the objective functions
   until kk(kp);
   kk(kp) = no;
*  release the fixed values of the objective functions for the new iteration
   z.up(k) =  inf;
   z.lo(k) = -inf;
);

if(mod_payoff.modelStat <> %modelStat.optimal% and
   mod_payoff.modelStat <> %modelStat.feasibleSolution%,
   abort 'no feasible solution for mod_payoff');

display payoff;

minobj(k) = smin(kp,payoff(kp,k));
maxobj(k) = smax(kp,payoff(kp,k));

$set fname p.%gams.scrext%

File fx 'solution points from eps-method' / "%gams.scrdir%%fname%" /;

$if not set gridpoints $set gridpoints 10

Set
   g         'grid points' / g0*g%gridpoints% /
   grid(k,g) 'grid';

Parameter
   gridrhs(k,g) 'rhs of eps-constraint at grid point'
   maxg(k)      'maximum point in grid for objective'
   posg(k)      'grid position of objective'
   firstOffMax  'counter'
   lastZero     'counter'
   numk(k)      'ordinal value of k starting with 1'
   numg(g)      'ordinal value of g starting with 0';

lastZero = 1;
loop(km1,
   numk(km1) = lastZero;
   lastZero  = lastZero + 1;
);
numg(g) = ord(g) - 1;

grid(km1,g) = yes; // Here we could define different grid intervals for different objectives
maxg(km1)   = smax(grid(km1,g), numg(g));
gridrhs(grid(km1,g))$(%min% = dir(km1)) = maxobj(km1) - numg(g)/maxg(km1)*(maxobj(km1) - minobj(km1));
gridrhs(grid(km1,g))$(%max% = dir(km1)) = minobj(km1) + numg(g)/maxg(km1)*(maxobj(km1) - minobj(km1));
display gridrhs;

* Walk the grid points and take shortcuts if the model becomes infeasible
posg(km1) = 0;
repeat
   rhs(km1) = sum(grid(km1,g)$(numg(g) = posg(km1)), gridrhs(km1,g));
   solve mod_epsmethod maximizing a_objval using lp;

   if(mod_epsmethod.modelStat <> %modelStat.optimal%,  // not optimal is in this case infeasible
      lastZero = 0;
      loop(km1$(posg(km1)  > 0 and lastZero = 0), lastZero = numk(km1));
      posg(km1)$(numk(km1) <= lastZero) = maxg(km1); // skip all solves for more demanding values of rhs(km1)
   else
      loop(k, put fx z.l(k):12:2); put /;
   );

*  Proceed forward in the grid
   firstOffMax = 0;
   loop(km1$(posg(km1) < maxg(km1) and firstOffMax = 0),
      posg(km1)   = posg(km1) + 1;
      firstOffMax = numk(km1);
   );
   posg(km1)$(numk(km1) < firstOffMax) = 0;
until sum(km1$(posg(km1) = maxg(km1)),1) = card(km1) and firstOffMax = 0;
putClose fx; // close the point file

* Get unique solutions from the point file using some Posix Tools (awk, (g)sort, uniq) that come with GAMS
$set awkscript awk.%gams.scrext%
File fa / "%gams.scrdir%%awkscript%" /;
put  fa 'BEGIN { printf("Table solutions(*,*)\n$ondelim\nsol';
loop(k, put ',' k.tl:0);
putClose '\n"); }' / '{ print NR,$0 }' / 'END { print ";" }';
$if     %system.filesys% == UNIX execute 'cd "%gams.scrdir%" && sort %fname% | uniq | awk -f %awkscript% > g.%gams.scrext% && gams g.%gams.scrext% o=gx.%gams.scrext% lo=0 gdx=soleps';
$if not %system.filesys% == UNIX execute 'cd "%gams.scrdir%" && gsort %fname% | uniq | awk -f %awkscript% > g.%gams.scrext% && gams g.%gams.scrext% o=gx.%gams.scrext% lo=0 gdx=soleps';
execute 'mv -f "%gams.scrdir%soleps.gdx" .';

Set s 'solutions' / 1*50 /;

Parameter solutions(s,k) 'unique solutions';

execute_load 'soleps', solutions;
display solutions;

$exit

$onText
The display should produce a table with 18 unique solutions:

----    203 PARAMETER solutions  Unique solutions

          cost  CO2emissi~  endogenous

1  3075000.000   62460.000   31000.000
2  3078000.000   62316.000   31200.000
3  3099000.000   61308.000   32600.000
4  3111000.000   60732.000   33400.000
5  3120000.000   60300.000   34000.000
6  3141000.000   59292.000   35400.000
7  3147000.000   59004.000   35800.000
8  3162000.000   58284.000   36800.000
9  3183000.000   57276.000   38200.000
10 3204000.000   56268.000   39600.000
11 3219000.000   55548.000   40600.000
12 3225000.000   55260.000   41000.000
13 3315000.000   53820.000   39000.000
14 3423000.000   52092.000   36600.000
15 3531000.000   50364.000   34200.000
16 3639000.000   48636.000   31800.000
17 3747000.000   46908.000   29400.000
18 3855000.000   45180.000   27000.000
$offText