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.

Integer variables

Extra complexity arises if there are integer variables in the original model. Ie, one or more of the xi variables must be integer. Remember that:

yj = xj y0

and

y0 = 1 / denominator

Because of the latter, y0 is a real number. So yj is real, even if xj is integer. None of the xj variables are in the transformed model and from above you can see that you can't make the yj variables integer to have xj integer. So is it then not possible to define something that xj become integer?
Remember that

xj = yj / y0

Suppose that xj must take an integer value i:

yj / y0 = i

yj = i * y0

Unfortunately, this constraint can't be handled by lpsolve since it is quadratic.
However a special case of integer variables can be solved:

Binary variables

Binary variables are a special kind of integer variables. They can only take 0 or 1 values. From the previous section we know that

yj = i * y0

In this case is i either zero or one. If zero, then yj must be zero. If one, then yj = y0. If we can put this into the formulation, then the xj variables will be binary.

To make this possible, you must introduce extra binary variables: zj

When zj = 0, then it must make yj = 0 and when zj = 1, then it must make yj = y0

One way to make this possible is by doing the following.
First you must determine a constant value f1 for which you know that f1 > yj in all cases and f2 for which you know that f2 > y0 in all cases.

Then you can write:

yj <= f1 zj
yj - y0 - f2 zj >= -f2
yj - y0 + f2 zj <= f2

Two cases have to be considered:

1) zj = 0

yj <= 0
yj - y0 >= -f2
yj - y0 <= f2

yj = 0
-y0 >= -f2
-y0 <= f2

yj = 0
y0 <= f2
y0 >= -f2

since you have chosen the constant f2 such that it is always larger than y0, equations 2 and 3 are redundant in this case and yj is indeed 0. And from above, this means that xj will be 0.

2) zj = 1

yj <= f1
yj - y0 - f2 >= -f2
yj - y0 + f2 <= f2

yj <= f1
yj - y0 >= 0
yj - y0 <= 0

since you have chosen the constant f1 such that it is always larger than yj, equation 1 is redundant. Equations 2 and 3 together make that yj equals y0. And from above, this means that xj will be 1.

Of course your model becomes alot more complex. Per xj integer variable, you must introduce an extra binary variable zj and add 3 constraints for each. And you must have a guess for f1 and f2. Don't take a very very large number like 1e10 or something like this because that would make the model very unstable because of scaling/rouding errors. You must deduce from your model what these two factors can be. Maybe by first solving the model without integer constraints and determine f1 and f2 from this real result.

Using the example from above, now requiring that both x1 and x2 are integer. The result of the real model is:

Value of objective function: 0.289916

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

From this, choose f1 and f2 being 10.

Now add the following constraints to this model:

y1 <= 10 z1
y1 - y0 - 10 z1 >= -10
y1 - y0 + 10 z1 <= 10

y2 <= 10 z2
y2 - y0 - 10 z2 >= -10
y2 - y0 + 10 z2 <= 10

int z1, z2

The solution of this model is:

Value of objective function: 0.19337

Actual values of the variables:
y1                      0.0552486
y2                      0.0552486
y0                      0.0552486
z1                              1
z2                              1

x1 = y1 / y0 = 1
x2 = y2 / y0 = 1

Indeed binary values.