Constraining on parts of vector

Answered

Roee Idan

• July 31, 2024 18:35

I am working on a Gurobi model where I have defined a vector y as a constraint using other variables. Here is the relevant part of my code:

python

Copy code

index_sets = [{0, 1, 2}, {3, 4}, {2, 6, 7}]

m = gp.Model("model", env=env)

x = m.addMVar(shape=len_directions, lb=0.0, name="x")
y = m.addMVar(shape=len(numpy_h), lb=-gp.GRB.INFINITY, name="y")

# Add the constraint y = h - g @ x using matrix operations
m.addConstr(y == numpy_h - (numpy_g @ x), name="c")
m.addConstr(y >= 0, name="geq_zero")

I have an additional requirement where I need to impose a constraint that, for each set of indices in a list of sets, there should be at least one value in the corresponding subset of y that is equal to zero.

For example, given a list of sets index_sets = [{0, 1, 2}, {3, 4}, {2, 6, 7}], I want to ensure that in each subset of y specified by these sets, there is at least one element that is zero.

Could you please advise on the best way to implement this constraint in Gurobi?

0

• 

  Ryuta Tamura

  Gurobi Staff

  • August 05, 2024 09:42
  • Edited

  Hi Roee,

  I don't know if this is the best approach, but here's an idea. First, estimate the upper limit for the variable. The program you have written does not have upper bounds on variables, but in general, specifying upper bounds has a positive effect on solving performance.

  Then define a new binary variable z. When this variable is 1, the corresponding y value is suppressed to 0. This can be achieved by using the following constraint:
  \[\begin{align*} y_{i} \leq M(1-z_{i}) \quad \forall i \end{align*}\]
  where M is a sufficiently large constant, for example, the upper bound on y estimated earlier can be used.

  The constraint that at least one of the subsets of y must be zero is satisfied by:
  \[\begin{align*} \sum_{i \in I} z_{i} = 1 \quad \forall I \in \text{index_sets} \end{align*}\]
  Here index_sets comes from your program, so the set \( I \) will loop {0, 1, 2}, {3, 4}, {2, 6, 7}.

  Is this helpful?

  Regards,
  Ryuta

   

  0
• 

  Roee Idan

  • August 14, 2024 06:53

  

  

  Hi Ryuta,

  Thank you very much  for the reply,

  Do you mean something like this:

  b = m.addMVar(shape=len(numpy_h), vtype=gp.GRB.BINARY, name="b")

  epsilon = 1e-6

  for i in range(len(numpy_h)):

          m.addGenConstrIndicator(b[i], True, y[i] == 0, name=f"indicator_y_zero_b_one_{i}")

          m.addGenConstrIndicator(b[i], False, y[i] >= epsilon, name=f"indicator_y_nonzero_b_zero_{i}")

   

  for idx, index_list in enumerate(paths_edges_indexs):

         m.addConstr(gp.quicksum(b[i] for i in index_list ) >= 1, f"at_least_one_zero_{idx}")

   

  From what I understood I should try to avoid indexing individual elements of the MVar, is there a more efficient way to do it?

   

  Best Regards

  Roee

  0
• 

  Ryuta Tamura

  Gurobi Staff

  • August 14, 2024 14:24
  • Edited

  Hi Roee,

  As described in this post, addGenConstrIndicator() should support MVar. Therefore, you can write like this:

  m.addGenConstrIndicator(b, True, y == 0, name=f"indicator_y_zero_b_one")
  m.addGenConstrIndicator(b, False, y >= epsilon, name=f"indicator_y_nonzero_b_zero")

  For the second constraint, it may be sufficient to create the corresponding matrix.

  import scipy.sparse as sp
  
  index_sets = [{0, 1, 2}, {3, 4}, {2, 6, 7}]
  row = [0, 0, 0, 1, 1, 2, 2, 2]
  col = [0, 1, 2, 3, 4, 2, 6, 7]
  A = sp.csr_matrix(([1 for i in range(len(row))], (row, col)), shape=(len(index_sets), len(numpy_h)))
  m.addConstr(A @ b >= 1)

  Here, A is a scipy.sparse matrix whose corresponding part of the index_sets has the value 1.

  Regards,
  Ryuta

  0

Please sign in to leave a comment.