Dual Variable for Facility Loaction Problem

Phi Long Nguyen

• July 04, 2024 09:04

Hello,

I am trying to solve the Facility Location Problem using Benders Decomposition. However, I noticed that the FLP is not particularly in standard form. I want to use .getAttr("Pi") to get the dual variable of the subproblem. However, I am unsure if I can retrieve the dual variable for such problems. In addition, is it possible to get the dual variable with equality and inequality constraints?

Is there a workaround or what should I do?

 

Here is the code if it helps:

 

import gurobipy as gp
from gurobipy import GRB
from itertools import product
import numpy as np
import matplotlib.pyplot as plt


class Benders_FLP():
    def __init__(self, num_customers, num_facilities, customers, facilities, setup_cost) -> None:
        self.cartesian_prod = list(product(range(num_customers), range(num_facilities)))
        self.shipping_cost = {(c,f) : compute_distance(customers[c], facilities[f]) for c, f in self.cartesian_prod}
        self.num_customers = num_customers
        self.num_facilities = num_facilities
        self.customers = customers
        self. facilities = facilities
        self.setup_cost = setup_cost

    def RMP(self):
        model = gp.Model()
        model.setParam("LogToConsole", 0)
        select_facilities = model.addVars(self.num_facilities, vtype=GRB.BINARY)
        theta = model.addMVar(1, lb = 0, vtype=GRB.CONTINUOUS)
        model.setObjective(select_facilities.prod(self.setup_cost)+ theta, GRB.MINIMIZE)
        model.update()

        model.optimize()
        select = get_selected_locations(select_facilities, self.num_facilities)
        return model.ObjVal, select_facilities, theta.x, select

    def SP(self, select_facilities):
        sub = gp.Model()
        sub.setParam("LogToConsole", 0)

        assign_customers = sub.addVars(self.cartesian_prod,ub=1,lb=0, vtype=GRB.CONTINUOUS)
        sub.addConstrs((assign_customers[(c,f)] <= select_facilities[f] for c,f in self.cartesian_prod), name='Setup2ship')
        sub.addConstrs((gp.quicksum(assign_customers[(c,f)] for f in range(self.num_facilities)) == 1 for c in range(self.num_customers)), name='Demand')
        sub.setObjective(assign_customers.prod(self.shipping_cost), GRB.MINIMIZE)
        return sub.ObjVal, assign_customers

 

The code does not run, since I ran into some errors.

 

Kind regards

 

Phi Long Nguyen

Related to

• Bender's

0

• 

  Alison Cozad

  Gurobi Staff

  • July 25, 2024 19:51
  • Edited

   

  Your subproblem is a Linear Program (LP), which is advantageous because dual values (pi values) can be retrieved for convex, continuous models. This capability applies to both equality and inequality constraints. This is true whether or not the model is written in standard or cononical form.

  To retrieve the dual values, the model must be optimized and have a feasible solution. In your code, it's important to ensure that the sub.optimize() method is called after setting the objective function in your subproblem.
  
  

  To retrieve pi values

  1. Define your model
  2. Optimize it using the Model.optimize() method
  3. Retrieve the dual values using the Constraint.getAttr("Pi") method.

  Example with afiro.mps

  Here is an example using the afiro.mps model, which comes prepackaged with Gurobi:

  import gurobipy as gp
  from gurobipy import GRB
  
  # Read/build model
  # Here I am using the example LP model afiro that comes prepackaged with Gurobi
  m = gp.read('afiro.mps')
  
  # Optimize model
  m.optimize()
  
  # Print all dual values
  for c in m.getConstrs():
      print(f"Constraint '{c.ConstrName}' has a pi value of {c.getAttr('Pi')}")

  For more details on the pi attribute, see Pi - Gurobi Optimization.

  0

Please sign in to leave a comment.