Constraining on parts of vector
AnsweredI 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:
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?

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(1z_{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,
Ryuta0 
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 = 1e6for 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 RegardsRoee0 
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,
Ryuta0
Please sign in to leave a comment.
Comments
3 comments