Gurobi counting: set constraint to a percentage of grid values

Answered

Tobias Etter

August 07, 2021 08:23

• 
• 

hi Gurobi community

we are using a grid (2 dimensional array). in every cell we calculate a double value.

is there a way to define a constraint in gurobi that makes sure that only 5% of all cells are allowed to be greater than a certain value?

maybe we can build something like this:

δ(i,j) = 0 ==> x(i,j) ≤ threshold
sum((i,j),δ(i,j)) ≤ 0.05 * gridsize
δ(i,j) ∈ {0,1}

δ(i,j) would be something like a binary variable and tell us, if x(i,j) is inside the range.


We tried to build it but we don't know how to use "==>" operator in Gurobi.
So we get a temporary constraint for every point. And with this type of values we cannot build a sum.

We are coding in c# but i guess it should be similar in all languages.

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  June 23, 2025 02:50 Edited

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Jaromił Najman

  • Gurobi Staff

  August 09, 2021 10:01 Edited

  Hi Tobias,

  For simplicity, let's assume that your grid variables are given by positive and bounded continuous variables \(x_{i,j}\), \(i \in \{1,\dots,N\}, j \in \{1,\dots,M\}\).

  For each variable \(x_{i,j}\), we introduce a binary variable \(\delta_{i,j}\). Let \(T\) be the constant threshold value. The constraints

  \[\begin{align}
  x_{i,j} &\leq T + \delta_{i,j}\cdot C\\
  x_{i,j} &\geq T - C \cdot (1-\delta_{i,j})
  \end{align}\]

  state that if \(delta_{i,j} = 1\) then \(x_{i,j} \geq T\) and if \(delta_{i,j} = 0\) then \(x_{i,j} \leq T\). \(C\) is a large constant, preferably something not too large, e.g., \(C= 2\cdot T\) or the maximal upper bound of the \(x_{i,j}\) variables. We now additionally need the constraint

  \[\sum \delta_{i,j} \leq 0.05\cdot N\cdot M\]

  to make sure that at most 5% of \(x_{i,j}\) variables is \(\geq T\). Note that Gurobi cannot work with strict inequality constraints, thus if you really need \(> T\), then you would have to introduce a small tolerance, e.g., \(10^{-5}\). However, in your case, the tolerance should not be necessary.

  Please note that there might be a better formulation for your particular problem and is not guaranteed to be the best.

  Best regards,
  Jaromił

  0

Post is closed for comments.