Ratios

Constraints

Linear constraints are of the form:

a1 x1 + a2 x2 + a3 x3 + ... >= minimum

a1 x1 + a2 x2 + a3 x3 + ... <= maximum

Where minimum and maximum are constants.

lp_solve can only handle these kind of Linear equations. However sometimes there are tricks to convert an equation that seems non-Linear at first sight to a Linear equation. One of these is ratio's:

a11 x1 + a12 x2 + a13 x3 + ... <= minimum
a21 x1 + a22 x2 + a23 x3 + ...

On condition that a21 x1 + a22 x2 + a23 x3 + ... is positive, this is equal to:

a11 x1 + a12 x2 + a13 x3 + ... <= minimum * (a21 x1 + a22 x2 + a23 x3 + ...)

If the denominator is always negative, then it can be converted to:

a11 x1 + a12 x2 + a13 x3 + ... >= minimum * (a21 x1 + a22 x2 + a23 x3 + ...)

Let's continue with the case that the denominator is positive, then the equation is also equal to:

a11 x1 + a12 x2 + a13 x3 + ... - minimum * (a21 x1 + a22 x2 + a23 x3 + ...) <= 0

(a11 - minimum * a21) x1 + (a12 - minimum * a22) x2 + (a13 - minimum * a23) x3 + ... <= 0

And there we have again a Linear equation. The same can be done for a maximum or equality of course. Don't forget that there is one assumption: the denominator is positive or negative. If it can be both, then this trick cannot be used.

One example of this is for example that it is required that two variables must have a ration of 1/2. For example:

x1 = 1/2
x2

With the formula above, this gives:

x1 - 0.5 x2 = 0

Adding this equation will result in the fact that x2 will be two times larger than x1. Again in the assumption that x2 stays positive.

Oh, and what if the denominator is zero? Division by zero is undefined and cannot give a real value. In the above example with two variables, if x2 is zero, then x1 is also forced to be zero. That is the side effect by converting the non-Linear equation to a Linear equation.

Objective function

max   c0 + c1 x1 + c2 x2 + c3 x3 + ...
      d0 + d1 x1 + d2 x2 + d3 x3 + ...

s.t.  ai1 x1 + ai2 x2 + ai3 x3 + ... <= bi
      xj >= 0

Note that c0 and d0 are constants. They are optional and not required for this solution.
Also note that the explanation uses <= constraints, but they can as well be >= constraints without any modification.
And as a last note, this text uses maximization of the objective function, but minimization works as good without any modification.

Linear programming only accepts models with equations in the first degree. The objective function however has a numerator and denominator so this seems not possible to solve with pure linear programming. However there is a trick to overcome to this problem. This model can be transformed to another model that is pure linear. When the solution is found to this transformed model, the results can be recalculated back to the original model.

There is only one condition to make this possible: the denominator must be strictly positive (or negative, but in that case you can multiply numerator and denominator by -1 such that the denominator becomes positive).

      d0 + d1 x1 + d2 x2 + d3 x3 + ... > 0

Again note the > sign. The denominator may also not become zero. If the transformed model returns a solution saying that it is zero, then the solution is invalid.

Now with this assumption in mind, we can introduce a new variable y0:

      y0 =                   1               
            d0 + d1 x1 + d2 x2 + d3 x3 + ...

Then the model can also be written as:

max   c0 y0 + c1 x1 y0 + c2 x2 y0 + c3 x3 y0 + ...

s.t.  ai1 x1 + ai2 x2 + ai3 x3 + ... <= bi
      y0 =                   1               
            d0 + d1 x1 + d2 x2 + d3 x3 + ...
      y0, xj >= 0

The constraints can also be multiplied by y0 and the y0 constraint can be written differently:

max   c0 y0 + c1 x1 y0 + c2 x2 y0 + c3 x3 y0 + ...

s.t.  ai1 x1 y0 + ai2 x2 y0 + ai3 x3 y0 + ... <= bi y0
      d0 y0 + d1 x1 y0 + d2 x2 y0 + d3 x3 y0 + ... = 1
      y0, xj y0 >= 0

Note again that this can only be done if y0 > 0

Now also make following substitution:

      yj = xj y0

Also put the bi y0 term to the left:

max   c0 y0 + c1 y1 + c2 y2 + c3 y3 + ...

s.t.  -bi y0 + ai1 y1 + ai2 y1 + ai3 y3 + ... <= 0
      d0 y0 + d1 y1 + d2 y2 + d3 y3 + ... = 1
      yj >= 0

All yj are variables (j starting from 0)

This new transformed model is an exact transformation of the original model, but with the advantage that it is a pure linear model. Also note that this model has one extra variable (y0) with coefficients in the matrix which are the negative of the right hand side (-bi y0). A constraint is also added requiring the constant term in the denominator times the new variable (d0 y0) plus the denominator terms involving the transformed variables to equal 1. The transformed model uses the same aij's as the original. Its right hand sides are all 0's except the one in the new constraint. The objective function does not have a denominator term and the objective function altered to include the numerator constant times the new variable y0.
This model can now be solved with lp_solve. Then to get the solution of the original model we must do a reverse transformation of this solution. This can be easily done:

      yj = xj y0
      
So:

      xj = yj / y0

Example

Suppose that it is desirable to solve the following problem.

max         1.8 x1 + 1.7 x2  
       10 + 4.0 x1 + 4.1 x2

s.t.  1.5 x1 +   x2 <= 6
      3.0 x1 + 4 x2 <= 20
      x1, x2 >= 0

Then the transformed problem is:

max            1.8 y1 + 1.7 y2

s.t.   -6 y0 + 1.5 y1 +     y2 <= 0
      -20 y0 + 3.0 y1 +   4 y2 <= 0
       10 y0 + 4.0 y1 + 4.1 y2 = 1
          y0, y1, y2 >= 0

The solution of this transformed model is:

Value of objective function: 0.289916

Actual values of the variables:
y1                      0.0420168
y2                        0.12605
y0                      0.0315126

Dual values with from - till limits:
                           Dual value            From            Till
R1                           0.342437     -0.03278689       0.1090909
R2                         0.04222689      -0.3076923       0.1156069
R3                           0.289916               0          1e+030
y1                                  0         -1e+030          1e+030
y2                                  0         -1e+030          1e+030
y0                                  0         -1e+030          1e+030

The value of the objective function of this transformed model is also the value of the objective function of the original model. The values of the original xi variables are calculated by dividing the yi values by y0:

x1 = y1 / y0 = 0.0420168 / 0.0315126 = 1.33333333
x2 = y2 / y0 = 0.12605 / 0.0315126 = 4

Plugging back into the original problem, the numerator equals 9.2; the denominator, 31.73, and their fraction 0.289916 (the objective function value reported). One may also recover the dual values or reduced costs. In this case since the rows are multiplied by one over the denominator, the original values may be recovered by dividing through by the denominator (1 / y0 or multiplying them by y0). Thus the effective dual value for constraint 1 is 0.01079, and constraint 2 is 0.0013307. Constraint 3 has no analogue in the original problem, and thus, is not transformed. The From - Till limits can also be recalculated back by dividing them by y0 and correcting these values with the bi y0 term.

Comments

This is an exact transformation as long as the denominator remains strictly positive. The formulation fails if y0 equals zero in the optimal solution. Much research has been done on fractional programming. The original development appears in Charnes and Cooper (1962). A historical perspective and literature review can be found in Schaible and Ibaraki.