• Gurobi Staff

Hi,

You can already add a constraint in the form $$||x-c|| \leq r$$ and it will be automatically transformed into a form that Gurobi accepts as a quadratic constraint with convex feasible region (see the script below). Adding auxiliary variables/constraints does not make an optimization problem necessarily more difficult. In general, there is no correlation between problem size and the runtime with Gurobi.

n = 5c = np.random.rand(n)m = gp.Model()x = m.addMVar(n, name="x")r = m.addMVar(1, name="r")m.addConstr(((x - c) * (x - c)).sum() <= r*r, name="c")m.optimize()

Best regards,

Maliheh

Thank you for the answer.

I am actually trying to solve the Weber problem using gurobi: for a set of points $P_1,P_2,\dots, P_n$ find the center of this set in a sense so that the sum of Euclidean distances (not squares, which would be simple) is minimized:

$\min_{C} \sum_{i=1}^N ||P_i-C||_2, \; C \in \mathbb{R}^n$

However I get the following error:

GurobiError: Q matrix is not positive semi-definite (PSD). Set NonConvex parameter to 2 to solve model.

Is it possible to formulate this problem as convex optimisation problem using gurobi (it should be convex as far as I know)?

I am inserting my code in case you would like to take a look.

import gurobipy as gpfrom gurobipy import GRBN = 20np.random.seed(1)Qx = np.random.uniform(size=N)Qy = np.random.uniform(size=N)Q = np.column_stack([Qx, Qy])weights = np.ones(N)m = gp.Model(name='Weber')dist = m.addVars(range(N), vtype=GRB.CONTINUOUS, obj=weights, name="dist", lb=0, ub=GRB.INFINITY)x = m.addVar(vtype=GRB.CONTINUOUS, name="x", lb=-GRB.INFINITY, ub=GRB.INFINITY)y = m.addVar(vtype=GRB.CONTINUOUS, name="y", lb=-GRB.INFINITY, ub=GRB.INFINITY)# point distances to centerfor n in range(N):    constr_name = f"dist_client{n}"    m.addConstr((Qx[n]-x)**2 + (Qy[n]-y)**2 <= dist[n]**2, name=constr_name)        # The objective is to minimize the sum of total distancesm.ModelSense = GRB.MINIMIZE# Solvem.optimize()

If I change

m.addConstr((Qx[n]-x)**2 + (Qy[n]-y)**2 <= dist[n]**2)

to

m.addConstr((Qx[n]-x)**2 + (Qy[n]-y)**2 <= dist[n])

code works fine.

I am also interested as well in multi-Weber formulation problem in gurobi - I have similar issues.

Help appreciated.

Thank you.

Regards,

Mindaugas Kepalas

• Gurobi Staff

Hi,

Sorry, my bad. I missed that you are interested in the sum of the $$l_2$$ norms. Yes, the function $$\sum_i ||x_i-x||_2$$ is convex because any norm function is convex and the sum of the convex functions is also convex.

To model the problem such that Gurobi accepts it as convex, we need to use the original idea you also mentioned. Specifically,

• Define auxiliary variables $$\texttt{zx}$$ and $$\texttt{zy}$$ to represent $$\texttt{Qx-x}$$ and $$\texttt{Qy-y}$$, respectively.
• Replace the quadratic constraint with a second-order cone constraint.

See your modified script below:

import gurobipy as gpfrom gurobipy import GRBN = 20np.random.seed(1)Qx = np.random.uniform(size=N)Qy = np.random.uniform(size=N)Q = np.column_stack([Qx, Qy])weights = np.ones(N)m = gp.Model(name="Weber")dist = m.addVars(    range(N), vtype=GRB.CONTINUOUS, obj=weights, name="dist", lb=0, ub=GRB.INFINITY)x = m.addVar(vtype=GRB.CONTINUOUS, name="x", lb=-GRB.INFINITY, ub=GRB.INFINITY)y = m.addVar(vtype=GRB.CONTINUOUS, name="y", lb=-GRB.INFINITY, ub=GRB.INFINITY)zx, zy = m.addVars(N, name="zx", lb=-GRB.INFINITY, ub=GRB.INFINITY), m.addVars(    N, name="zy", lb=-GRB.INFINITY, ub=GRB.INFINITY)m.addConstrs((zx[n] == Qx[n] - x for n in range(N)))m.addConstrs((zy[n] == Qy[n] - y for n in range(N)))# point distances to centerfor n in range(N):    constr_name = f"dist_client{n}"    m.addConstr(zx[n] ** 2 + zy[n] ** 2 <= dist[n] ** 2, name=constr_name)# The objective is to minimize the sum of total distancesm.ModelSense = GRB.MINIMIZE# Solvem.optimize()

Best regards,

Maliheh