! Optimize a model with a ratio objective.
Sometimes called fractional or hyperbolic programing.
This example illustrates Dinkelbach's method, which allows integer variables.
This may be a useful approach if the model is linear except for the ratio objective;
! Ref: Dinkelbach, W. (1967) "On nonlinear fractional programming,"
Management Science, 13(7), 492–498;
! Keywords: Dinkelbach, Fractional programming, Hyperbolic programming, Ratio objective;
SUBMODEL dinkel:
! We really want to :
MAX = objn/ objd;
! We instead optimize a weighted sum of objn and objd;
MAX = objlin;
objlin = objn - theta* objd;
objn = y1 + 3*y2 + x1 - x2 + 1;
objd = 2*y1 + y2 + 3*x1 + 5*x2 + 1;
-y1 + 2* y2 <= 9;
4*y1 + y2 <= 21;
y1 - 3*y2 <= 0;
4*y1 + 5*y2 >= 12;
-2*x1 + 6*x2 <= 21;
7*x1 + 4*x2 <= 39;
@GIN( y1);
@GIN( y2);
ENDSUBMODEL
CALC:
! Set some solve parameters;
@SET( 'OROUTE',1); ! 1: Route output immediately to the window line by line;
@SET( 'TERSEO',2); ! Output level (0:verb, 1:terse, 2:only errors, 3:none);
@SET( 'IPTOLR', .005); ! Set ending relative optimality tolerance for individual solves;
@SET( 'TIM2RL', 30); ! Time in seconds to apply optimality tolerance;
! We want to maximize objn/ objd.
Suppose we have a feasible solution with THETA = objn/ objd,
or objn - THETA * objd = 0.
If there is a better solution, objn1/ objd1 > THETA, then
objn1 - THETA * objd1 > 0, and we will find it if we
Maximize objn - THETA* objd.
Applying this idea repeatedly is Dinkelbach's method;
tolopt = 0.000001; ! Final relative optimality tolerance;
theta = -9999;
thet0 = 0.5; ! Guess initial value for the ratio;
iter = 0;
@WHILE( @ABS( theta - thet0)/@SMAX(@ABS( theta),@ABS( thet0)) #GT# tolopt:
iter = iter + 1;
theta = thet0;
! Can we find a solution with a linearized objective > 0;
@SOLVE( dinkel);
thetafeas = objn/ objd;
@WRITE( iter,') Found new feasible solution. Linear obj= ',
objlin,', True obj= ', thetafeas, @NEWLINE(1));
! Write a little solution report;
@WRITE(' Soln has objn= ',
objn, ', objd= ', objd,'. Ratio= ', objn/objd, @NEWLINE(1));
@WRITE( ' y1, y2, x1, x2= ', y1,' ', y2,' ', x1,' ', x2, @NEWLINE(1));
@IFC( objlin #LE# 0:
@WRITE(' An upper bound on theta= ', theta, @NEWLINE(1));
);
thet0 = theta + objlin/ objd;
);
ENDCALC
|