Two Phase method

Answered

Shahrzad Valizadeh

• June 11, 2024 03:49

I want to solve the following model using Two-Phase method. 

minz = -x1 + 2x2 - 3x3

x1 + x2 + x3 = 6

-x1 + x2 +2x3 = 4

2x2 + 3x3 = 10

x3 <= 2

i have written the following code, but it gives me infeasibility

import gurobipy as gp
import itertools
import os
from gurobipy import Model, GRB
# Solving the main linear model directly, without implementing Two-Phase and CG
# Create the initial master problem
model = gp.Model("Model Problem")
model.setParam('OutputFlag', 1)
for i in range(3):
    x[i] = model.addVar(vtype=GRB.CONTINUOUS, name=f'x_{i}')
R = {}   
for j in range(4):
    R[j] = model.addVar(lb=0, vtype=GRB.CONTINUOUS, name=f'R_{j}')
model.setObjective(gp.quicksum(R[j] for j in range(4)))

model.addConstr(x[0] + x[1] + x[2] + R[0] == 6, "First_Constraint")

model.addConstr(-1 * x[0] + x[1] + 2 * x[2]  + R[1] == 4, "Second_Constraint")

model.addConstr(2 * x[1] + 3 * x[2]  + R[2] == 10, "Third_Constraint")

model.addConstr(x[2] + R[3] == 2, "Fourth_Constraint")
if model.status == GRB.OPTIMAL:
    # Get the objective value
    objective_value = model.objVal

    # Check if the objective value is approximately zero
    if abs(objective_value) < 1e-6:
        model.remove(model.getConstrByName("First_Constraint"))
        model.remove(model.getConstrByName("Second_Constraint"))
        model.remove(model.getConstrByName("Third_Constraint"))
        model.remove(model.getConstrByName("Fourth_Constraint"))
        
        model.setObjective(0, GRB.MINIMIZE)
        obj = -1 * x[0] + 2 * x[1] -3 * x[2]
        model.setObjective(obj, GRB.MINIMIZE)

        model.addConstr(x[0] + x[1] + x[2] == 6, "First_Constraint")

        model.addConstr(-1 * x[0] + x[1] + 2 * x[2]  == 4, "Second_Constraint")

        model.addConstr(2 * x[1] + 3 * x[2]  == 10, "Third_Constraint")

        model.addConstr(x[2] == 2, "Fourth_Constraint")
        model.optimize()
        for i in range(3):
            variable_value = x[i].X  # Get the value of the variable
            if variable_value > 1e-6:
                non_zero_primal += 1
                print(f"x[{i}] = {x[i].x}")
else:
    print("infeasible")

0

• 

  Simranjit Kaur

  Gurobi Staff

  • June 11, 2024 04:00

  Hi Shahrzad,

  It seems like you forgot to call model.optimize() to solve the model before checking if model.status is GRB.OPTIMAL.

  Best regards,
  Simran

   

  0
• 

  Shahrzad Valizadeh

  • June 11, 2024 04:05

  

  

  Dear Simranjit, thank you for your response. You're right, it was a mistake.

  Overall, is this approach correct for writing the Two-Phase method?

  0
• 

  Simranjit Kaur

  Gurobi Staff

  • June 11, 2024 04:30
  • Edited

  Overall it looks correct. Just two points:

  1. The call model.setObjective(0, GRB.MINIMIZE) in the Phase 2 is not required. The following two lines are enough to set the original objective of the model

  obj = -1 * x[0] + 2 * x[1] -3 * x[2]
  model.setObjective(obj, GRB.MINIMIZE)

  2. In Phase two, instead of removing the constraints and re-adding them again, you can simply change the coefficients of the artificial variables to zero using model.chgCoeff method, for example, if you have 

  c1 = model.addConstr(x[0] + x[1] + x[2] + R[0] == 6, "First_Constraint")

  then to change the coefficient of R[0] to zero in Phase 2, you can call

  model.chgCoeff(c1, R[0], 0)

  0
• 

  Shahrzad Valizadeh

  • June 11, 2024 05:00

  

  

  Thank you so much for your guidance.

  0
• 

  Shahrzad Valizadeh

  • June 11, 2024 06:57

  

  

  Thank you for your valuable responses. 

  0

Please sign in to leave a comment.