Pricing out - Idea used in Column Generation

pricingOut.py

from ortools.linear_solver import pywraplp

'''
Pricing out: 
- This idea is used in Column Generation 
- Course: https://www.edx.org/course/optimization-methods-for-business-analytics, Week5

==============================================================================

Idea
-----
 
Minimize
 Obj: X + Y 
Subject to
 Ct1: 2 X + Y >= 3
 Ct2: X + 2 Y >= 3
Bounds
 0 <= X
 0 <= Y
End
 
Running this, we get:
`````````````````````
Objective = 2 
X = 1.0
Y = 1.0 
 
Dual values:
````````````
Ct1 0.3333
Ct2 0.3337
 
Dual values tell us:
````````````````````
how much is the increase in objective value 
when we increase rhs of the constraint by 1 unit & vice-versa 
 
==============================================================================
 
I have a new variable Z,
- has cost = 1.9, 
- will be added in Ct1, Ct2 with coeff of 3
 
- I want to know whether or not Z will take 
  non-zero value in the optimal solution  
 
How the model would look like with Z:
`````````````````````````````````````
Minimize
 Obj: X + Y + 1.9 Z 
Subject to
 Ct1: 2 X + Y + 3 Z >= 3
 Ct2: X + 2 Y + 3 Z >= 3
Bounds
 0 <= X
 0 <= Y
 0 <= Z
End
 
==============================================================================
 
Pricing out variable Z
``````````````````````
Assume Z=1. Model would then be 
 
Minimize
 Obj: X + Y + 1.9  
Subject to
 Ct1: 2 X + Y >= 3 - 3
 Ct2: X + 2 Y >= 3 - 3
Bounds
 0 <= X
 0 <= Y
 0 <= Z
End
 
Change in objective when Z=1:
`````````````````````````````
+ 1.9 of cost to the objective 
- 0.333 * 3 (because we are decreasing the rhs of ct1 by 3)
- 0.333 * 3 (again, we are decreasing the rhs of ct2 by 3)
== -0.098 
 
This means, 
Z has a negative reduced cost of -0.098
and it would decrease the objective 
 
Since we are minimizing,
the optimal value would change 
and Z will get a non-zero value 
 
Running with Z gives:
`````````````````````
Objective: 1.9
X 0.0
Y 0.0
Z 1.0
Z has non-zero value
'''


def buildModelAndSolve(hasZVariable):

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

    x = solver.NumVar(0, solver.Infinity(), "X")
    y = solver.NumVar(0, solver.Infinity(), "Y")
    if hasZVariable:
        z = solver.NumVar(0, solver.Infinity(), "Z")

    if not hasZVariable:
        ct1 = solver.Add(2*x + y >= 3, "Ct1")
        ct2 = solver.Add(x + 2*y >= 3, "Ct2")
    else:
        ct1 = solver.Add(2*x + y + 3*z >= 3, "Ct1")
        ct2 = solver.Add(x + 2*y + 3*z >= 3, "Ct2")

    objective = solver.Objective()
    objective.SetCoefficient(x, 1)
    objective.SetCoefficient(y, 1)
    if hasZVariable:
        objective.SetCoefficient(z, 1.9)
    objective.SetMinimization()

    print(solver.ExportModelAsLpFormat(False))
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print("Objective: ", objective.Value())
        print(x.name(), x.SolutionValue())
        print(y.name(), y.SolutionValue())
        if hasZVariable:
            print(z.name(), z.SolutionValue())

        print(ct1.name(), ct1.dual_value())
        print(ct2.name(), ct2.dual_value())



if __name__ == '__main__':

    # Set this to True if you want Z to be in the model
    hasZVariable = False

    buildModelAndSolve(hasZVariable)