• Gurobi Staff

Hi,

Currently, to model the L1 norm, you have to make use of the abs general constraint function.

In the upcoming release, there will be a specialized general constraint for the L1 norm. The release is planned for November 2021.

Best regards,
Jaromił

Hi Jaromil,

Thanks! I have two follow up questions if you don't mind.

- How would I write/encode the conditions: (Xi, Yi) != (Xj, Yj) when i !=j ?

- In terms of performance, is it okay to keep the absolute value, or should I try to linearize the equation, e.g. by introducing additional variables and solve something like that intead?

min t0 + t1 where -t0 < Xi - xi < t0 and -t1 < Yi - yi < t1

Thanks.

• Gurobi Staff

Hi,

- How would I write/encode the conditions: (Xi, Yi) != (Xj, Yj) when i !=j ?

Since one cannot access solution point values while constructing the model, you have to model this condition via the usage of binary variables and additional inequalities.

I will provide an example for the condition $$(x_1,y_1) \neq (x_2,y_2)$$. You can use the abs function to create constraints

\begin{align} |x_1 - x_2| &\geq \epsilon\delta_x \\ |y_1 -y_2| &\geq \epsilon\delta_y \\ \delta_x + \delta_y &\geq 1\\ \delta_x,\delta_y &\in \{0,1\} \end{align}

The above states that at least one of the coordinates has to be different by at least $$\epsilon$$, i.e., not equal. Please note that we have to use a tolerance because strict inequality constraints are not supported in Gurobi.

In terms of performance, is it okay to keep the absolute value, or should I try to linearize the equation, e.g. by introducing additional variables and solve something like that intead?

It is OK to keep the absolute value. So you should not see any benefit by linearizing the equations by hand.

Best regards,
Jaromił

Hi Jaromil,

One last question. For the inequalities for all pairs (i,j) i!=j, I should use the same delta x and delta y?

Thanks.

• Gurobi Staff

Hi,

Using the same delta for all pairs would restrict all pairs to either differ in the $$x$$ or in the $$y$$ coordinate or in both. Thus, it is best to introduce separate $$\delta_{x,ij},\delta_{y,ij}$$ for each $$i,j$$ pair.

Best regards,
Jaromił

Hi Jaromil,

How should the epsilon be chosen?

Also, could we write the condition as |Xi - Xj| + |Yi-Yj| >= 1, which would force the pairs to be different as they take integer values?

Thanks!

• Gurobi Staff

Hi,

How should the epsilon be chosen?

$$\epsilon$$ should be some small value which is still above the FeasibilityTol, e.g., $$10^{-5}$$. This small tolerance is only required if $$X,Y$$ are continuous variables.

Since $$X,Y$$ are integers, you can use the constraint you proposed.

Best regards,
Jaromił