Charnes-Cooper transformation

Optimization - Charnes-Cooper transformation

Charnes-Cooper is a mathematical trick used to convert a linear fractional programming problem into a linear programming problem — so that we can solve it with standard LP or MILP solvers.

Fractional problems — like those with a ratio in the objective or constraint — are nonlinear, non-convex, and hard for solvers to handle. But if both the numerator and denominator are linear, then Charnes-Cooper can linearize it.

An example optimization problem:

   objective = maximize{(2x1+3x2)/(x1 + x2)}

   constraint: x1+x2<=10, x1,x2>=0

Now need to the objective to linear terms

step 1, create a new variable as 1/denominator

Let:

  t = 1/(x1+x2)

this is just a scaling factor, don't worry about it's meaning.

step2, re-define every existing variable x1, x2 ... using the new t variable

Let:

  y1 = x1*t

  y2 = x2*t

to enforce the non-linear definition of t = 1/(x1+x2), replace x1, x2 with y1/t and y2/t,

  t = 1/(x1+x2) becomes:

  t = 1/(y1/t + y2/t) 

  which is:

    1 = 1/(y1+y2) => y1+y2 = 1

This cleverly defines a non-linear term by a linear constraint.

For the objective function, replacing x1,x2 with y1,y2, the objective becomes:

  (2x1+3x2)/(x1 + x2) = (2y1/t+3y2/t) * t = 2y1+3y2

The converted optimization problem:

   objective = maximize(2y1+3y2)

   variables: t, y1, y2

   constraints:

   x1+x2<=10  => y1+y2 <= 10t

   x1,x2>=0   => y1, y2>=0

   t > 0 (denominator must be positive)

   y1+y2 = 1 (the extra constraint)

Note here the t is unbounded, as long as it is positive, it can be 1 or 1000 or 1m. It doesn't matter.

However, whatever value t is, it doesn't impact the solution for y1, y2. the t is simply a scaling factor.

So make sure that t=1/(x1+x2) is larger than 0, e.g. if x1,x2 are binary variables, and then set t = 1

   objective = maximize(2y1+3y2)

   variables: y1, y2

   constraints:

   x1+x2<=10  => y1+y2 <= 10

   x1,x2>=0   => y1, y2>=0

   y1+y2 = 1 (the extra constraint)

Done!

What if the numerator and denominator have different variables? e.g.

objective: maximize{(2x1+3x2)/(3y1+4y2)}

constraints: x1+x2+y1+y2<=10, x1,x2,y1,y2>=0

Again, use 1/denominator as a new variable

   t = 1/(3y1+4y2)

redefine all the existing variables x1,x2,y1,y2 using the t

   z1=x1*t

   z2=x2*t

   z3=y1*t

   z4=y2*t

create a new constraint for enforcing t = 1/(3y1+4y2) so we have:

   t=1(3z3/t + 4z4/t) 

   =>  3z3 + 4z4 = 1

The converted problem becomes:

    objective:

    maximize(2z1+3z2)

    variables: 

            z1, z2, z3, z4

    constraints:

    z1+z2+z3+z4<=10

z1,z2,z3,z4>=0

3z3+4z4=1

Done!

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver('SCIP')

# Define variables z1, z2, z3, z4 >= 0

z1 = solver.NumVar(0, solver.infinity(), 'z1')

z2 = solver.NumVar(0, solver.infinity(), 'z2')

z3 = solver.NumVar(0, solver.infinity(), 'z3')

z4 = solver.NumVar(0, solver.infinity(), 'z4')

# Objective: Maximize 2*z1 + 3*z2

solver.Maximize(2 * z1 + 3 * z2)

# Constraint 1: z1 + z2 + z3 + z4 <= 10

solver.Add(z1 + z2 + z3 + z4 <= 10)

# Constraint 2: 3*z3 + 4*z4 = 1 (normalization constraint)

solver.Add(3 * z3 + 4 * z4 == 1)

# Solve the problem

status = solver.Solve()

# Output results

if status == pywraplp.Solver.OPTIMAL:

    print('Optimal solution found:')

    print(f'z1 = {z1.solution_value():.4f}')

    print(f'z2 = {z2.solution_value():.4f}')

    print(f'z3 = {z3.solution_value():.4f}')

    print(f'z4 = {z4.solution_value():.4f}')

    print(f'Objective value = {solver.Objective().Value():.4f}')

else:

    print('No optimal solution found.')