L1 minimization
AnsweredHello,
I have a set of points in the 2D plane with float coordinates (x, y) and I want to snap them to a grid of points with integer coordinates (X, Y). Two points cannot share the same grid point.
I am trying to solve for the minimal displacement with L1 norm, i.e.
min sum_i (  Xi  xi  + Yi  yi  ) s.t. (Xi, Yi) != (Xj, Yj) when i !=j.
Is there a good way to code that in Gurobi API (preferentially C++)?
Thanks.

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ł0 
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.
0 
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ł0 
Hi Jaromil,
Thank you a lot for your quick answer!
One last question. For the inequalities for all pairs (i,j) i!=j, I should use the same delta x and delta y?
Thanks.
0 
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ł0 
Hi Jaromil,
How should the epsilon be chosen?
Also, could we write the condition as Xi  Xj + YiYj >= 1, which would force the pairs to be different as they take integer values?
Thanks!
0 
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ł0
Please sign in to leave a comment.
Comments
7 comments