Lindo Systems

! 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