L1 minimization

Answered

L1fe

• September 30, 2021 17:20
• Edited

Hello,

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.

 

0

• 

  Jaromił Najman

  Gurobi Staff

  • October 01, 2021 11:44

  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
• 

  L1fe

  • October 01, 2021 12:59

  

  

  

  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
• 

  Jaromił Najman

  Gurobi Staff

  • October 01, 2021 13:47
  • Edited

  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
• 

  L1fe

  • October 01, 2021 14:06

  

  

  

  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
• 

  Jaromił Najman

  Gurobi Staff

  • October 01, 2021 14:41

  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
• 

  L1fe

  • October 03, 2021 14:13

  

  

  

  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!

  0
• 

  Jaromił Najman

  Gurobi Staff

  • October 04, 2021 07:21
  • Edited

  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.