Artificial Variables Removal from Two Phase Method

Daniel Lawand

2025年06月27日 13:24

• 
• 

I want to implement phase 1 from Two Phase method to find a feasible solution for a linear problem as shown in the image.

 

Does gurobi do step 5 automatically in its optimization?

 

Currently, I'm implementing in the following way:
 

def phase_one_gurobi(self, A, b) -> tuple[np.ndarray, np.ndarray, np.ndarray]:
    m, n = A.shape

    # Step: 1 Ensure b >= 0 by flipping rows if needed
    A_mod = A.copy()
    b_mod = b.copy()
    for i in range(m):
        if b_mod[i] < 0:
            A_mod[i, :] *= -1
            b_mod[i] *= -1

    # Create Gurobi model for Phase I
    model = gp.Model("phase_one")
    model.setParam("OutputFlag", 1)

    # Original variables
    x = model.addVars(n, lb=0.0, name="x")

    # Step: 2 Artificial variables
    artificial = model.addVars(m, lb=0.0, name="artificial")

    # Constraints: A_mod @ x + artificial = b_mod
    for i in range(m):
        constr_expr = gp.quicksum(A_mod[i, j] * x[j] for j in range(n)) + artificial[i]
        model.addConstr(constr_expr == b_mod[i], name=f"c_{i}")

    # Objective: minimize sum of artificial variables
    model.setObjective(gp.quicksum(artificial[i] for i in range(m)), GRB.MINIMIZE)
    
    # Solve using primal or dual simplex
    model.setParam("Method", 1)

    # Optimize Phase I
    model.optimize()

    if model.Status != GRB.OPTIMAL:
        print(f"Optimization failed or stopped with status: {model.Status}")
        return None, None, None

    # Step 3: Check if auxiliary costs are positive
    if model.ObjVal > 1e-6:
        print("Original problem is infeasible (artificial objective > 0).")
        return None, None, None

    # Step 4: Check which artificial variables are in the basis with value 0
    redundant_rows = []
    for i in range(m):
        if artificial[i].VBasis == 0:
            if abs(artificial[i].X) < 1e-6:
                print(f"Artificial var artificial[{i}] is in basis with value 0 — constraint {i} is redundant.")
                redundant_rows.append(i)


    # Remove redundant constraints from A and b
    A_clean = np.delete(A_mod, redundant_rows, axis=0)
    b_clean = np.delete(b_mod, redundant_rows, axis=0)

    # Extract feasible x solution (feasible solution to original Ax = b)
    x_vals = np.array([x[j].X for j in range(n)])

    return x_vals, A_clean, b_clean

関連

• Simplex

1

• 

  João Pedro Arroyo

  2025年06月27日 17:37

  • 

  It seems to me that this would not be covered, and that you would need to apply “step 5” after the optimization, instead of just removing the redundant rows.
  PS: I think the condition “ if abs(artificial[i].X) < 1e-6:” can be removed, because if some artificial var. has a non-zero coefficient (≥1e-6) then the condition “ if model.ObjVal > 1e-6:”  is true and the program does not get to the following steps.

  0
• 

  Daniel Lawand

  2025年07月02日 19:38

  • 
  • 

  Thanks for the heads up.

  I don't think Gurobi covers this either. 
  But I'm looking for a definite answer as to whether Gurobi does step 5 automatically in its optimization.
   

  0

サインインしてコメントを残してください。