Finding best new point using Euclidean distance- gurobipy.QuadExpr error

Answered

Jayesh Yevale

September 29, 2023 14:39

• 
• 
• 

Hi,

I encountered a error when I coded the above problem?

here is my code:

from gurobipy import *
from itertools import *
from math import *
import logging

# create empty model
m = Model("Problem")
# Defining Euclidean distance between two points.
def compute_distance(loc1, loc2):
    dx = loc1[0] - loc2[0]
    dy = loc1[1] - loc2[1]
    return sqrt(dx**2 + dy**2)

loc = [(358,309),(275,126),(424,154)] #location
loads = [8,5,8] #weights
cost = [4,6,5] #costs

# add variables
x = m.addVars(2)

if len(loc)==len(loads)==len(cost):
    number_of_loc = len(loc)
    # set objective function
    m.setObjective(quicksum(loads[i]*cost[i]*compute_distance(x,loc[i]) for i in range(number_of_loc)), GRB.MINIMIZE)
else:
    logging.basicConfig(format='%(message)s')
    log = logging.getLogger(__name__)
    log.warning('Missing Values - Please debug')


# solve model
m.optimize()

# print the optimal objective value
print('\n Cost is equal to ',m.objVal)

# print the optimal solution
m.printAttr('X')

I am getting the error below. Can someone assist me with this? Thank you so much. I was able to solve this using excel easily but want to try using gurobi.

TypeError: must be real number, not gurobipy.QuadExpr

0

• 

  Jayesh Yevale

  September 29, 2023 14:43

  • 
  • 
  • 

  I understood the error as it cannot accept the gurobi variables as provided. I need help what should I look for to solve such problems? Thank you.

  0
• 

  Eli Towle

  • Gurobi Staff

  September 29, 2023 21:37

  You see this error because Python's \(\texttt{math.sqrt}\) function does not know what to do with the Gurobi QuadExpr object you passed it. Square root relationships must be modeled using quadratic constraints. See the article What types of models can Gurobi solve? for more information.

  For each point \(i \in \{1, 2, 3\}\), let \((\bar{x}_i, \bar{y}_i)\) be the corresponding coordinates, let \(w_i\) be the corresponding load/weight, and let \(c_i\) be the corresponding cost. Your model is currently formulated as follows:

  $$\begin{alignat*}{2}\min_{x,y}\ & \sum_{i=1}^3 w_i c_i \sqrt{(\bar{x}_i - x)^2 + (\bar{y}_i - y)^2} \\ \textrm{s.t.}\ & \enspace x,y \geq 0\end{alignat*}$$

  We can rewrite this model as a quadratic program using auxiliary variables. There are many different ways we could reformulate the model. Below is a formulation that Gurobi will recognize as convex, which should help Gurobi solve the problem more efficiently. There are more succinct formulations, though Gurobi may not recognize them as convex.

  $$\begin{alignat*}{3}\min_{x,y,u,v,w}\ &&\sum_{i=1}^3 & w_i c_i u_i \\ \textrm{s.t.}\ && u_i^2 &\geq v_i^2 + w_i^2 \qquad && i = 1, 2, 3 \\ && v_i &= \bar{x}_i - x \qquad && i = 1, 2, 3 \\ && w_i &= \bar{y}_i - y \qquad && i = 1, 2, 3 \\ && x,y &\geq 0 \\ && \enspace u_i & \geq 0 \quad && i = 1, 2, 3.\end{alignat*}$$

  What do auxiliary variables \(u\), \(v\), and \(w\) represent in this formation? For each \(i = 1, 2, 3\):

  • \(v_i\) is equal to horizontal (x-axis) difference between point \( i \) and the point we select: \(v_i = \bar{x}_i - x\).
  • \(w_i\) is equal to the vertical (y-axis) difference between point \( i \) and the point we select: \(w_i = \bar{y}_i - y\).
  • The objective function pushes \(u_i\) to be as small as possible. At the optimal solution, \( u_i \) will equal \(\sqrt{v_i^2 + w_i^2}\) = \(\sqrt{(\bar{x}_i - x)^2 + (\bar{y}_i - y)^2}\).

  Here is the Python formulation:

  import gurobipy as gp
  from gurobipy import GRB
  
  m = gp.Model()
  
  loc = [(358, 309), (275, 126), (424, 154)]
  loads = [8, 5, 8]
  cost = [4, 6, 5]
  n = len(loc)
  
  x, y = m.addVar(name="x"), m.addVar(name="y")
  u = m.addVars(n, name="u")
  xdiff = m.addVars(n, lb=-GRB.INFINITY, name="xdiff")
  ydiff = m.addVars(n, lb=-GRB.INFINITY, name="ydiff")
  
  m.setObjective(gp.quicksum(loads[i] * cost[i] * u[i] for i in range(n)), GRB.MINIMIZE)
  
  for i in range(n):
      m.addConstr(xdiff[i] == loc[i][0] - x, name=f"define_xdiff[{i}]")
      m.addConstr(ydiff[i] == loc[i][1] - y, name=f"define_ydiff[{i}]")
      m.addConstr(u[i] ** 2 >= xdiff[i] ** 2 + ydiff[i] ** 2, name=f"define_u[{i}]")
  
  m.optimize()
  
  print("Cost:", m.ObjVal)
  print(f"Optimal solution: x={x.X}, y={y.X}")

  0
• 

  Jayesh Yevale

  September 29, 2023 23:05

  • 
  • 
  • 

  Hi Eli,

  This makes more sense now. I appreciate your help reformulating the model and making it more compliant to the gurobi solver.

  Thank you and Best,
  Jayesh

  0

Please sign in to leave a comment.