Avoid unnecessary constraints

Answered

December 05, 2021 18:50 Edited

Hi. Among others, I have the following variables/fixed values:

z = m.addMVar((n, n), name="z")
x = np.random.rand(n)
products=m.addMVar((n,n))

and would like to have some constraints (I am simplifying some things here) which I wrote in this form

m.addConstrs(products[i,j]==z[i,j]*x[i] for i in range(n) for j in range(n))

for k in range(n):

     m.addConstr(products[:,:k+1].sum() <= 0)

However, this turns out to be "too complicated " for the optimizer, so it gives unfeasible model error even if it is obvious that the model is feasible. The problem is in the definition of product which is now a constraint, but there must be a way to write it without that. Any advice?

Comments

7 comments

Official comment
Simranjit Kaur

Gurobi Staff

June 23, 2025 02:43 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?.
Maliheh Aramon

Gurobi Staff

December 07, 2021 06:57
Hi Ivana,

Running the script above gives the optimal solution of 0 as expected. All decision variables are defined to be non-negative and the only solution that satisfies the last constraint (the sum over $\texttt{products}$ variables should be non-positive) is all zeros. Could you please elaborate more on when he model results in infeasibility? It might be a good idea to share the mathematical representation of the constraint that you would like to implement without defining the $\texttt{products}$ variables.

Best regards,

Maliheh
1

Ivana Rajkovic

December 07, 2021 18:05

Hi, Maliheh. Let me try to give you all the details. I will add the exact case when the error happened.

First, the general thing that does work:

n = 4

m = Model()

z = m.addMVar((n, n), name="z")
x = np.array([9,6,4,1])
y= np.array([5,5,5,5])
alfa= m.addMVar(1, name="alfa")
beta= m.addMVar(1,name="beta")

m.addConstr(beta >=0)
m.addConstr( alfa <=0)

for i in range(n):
     m.addConstr(z[i, :].sum() == 1, name="row"+str(i))
     m.addConstr(z[:, i].sum() == 1, name="col"+str(i))

for i in range(n):
    for j in range(n): 
        m.addConstr(z[i,j]>=0)

products=m.addMVar((n,n))



m.addConstrs(products[i,j]==z[i,j]*x[i] for i in range(n) for j in range(n))

for k in range(n):
     m.addConstr(products[:,:k+1].sum() - y[:k].sum() <= beta)
     m.addConstr(products[:,:k+1].sum() - y[:k+1].sum() >= alfa)

m.setObjective(beta - alfa , gurobipy.GRB.MINIMIZE)

As I said this does work. However, what I am interested in is a sort of iterative rounding ie. first going through the first column, fixing an element to be 1, and others 0 and solving LP $n$ times Then pick the index of the best optimum, fix 1 there and repeat for the next column. I do this in the following way

available=[i for i in range(n)]
for j in range(n):
  optValue=1000
  optIndex=-1
  for i in available:
    m.addConstr(z[i,j]-1==0, name="fix"+str(i) ) 
    m.optimize()
    value=beta.x - alfa.x
    if value < optValue:
       optValue=value
       optIndex=i
   m.remove(m.getConstrByName("fix"+str(i)))
  m.update()
  m.addConstr(z[optIndex,j]==1)
  available.remove(optIndex)

However, this stops at some point and I checked that the first problem happens for j=0,i=2. Bz calling computeIIS() I saw that it chooses to relax the product constraint, ie. product is not equal to z*x.

However, the feasible solution can easily be constructed by hand.

The mathematical formulation of the constraint/s I am interested in is following :

for all k in range(n) : sum_{j=1 to k} sum_{i=1 to n} z_{ij}*x_{i} - sum{j=1 to k-1}y_{j} <= beta

for all k in range(n) : sum_{j=1 to k} sum_{i=1 to n} z_{ij}*x_{i} - sum{j=1 to k}y_{j} >= alfa

*indices start from 1

Best regards,

Ivana

Maliheh Aramon

Gurobi Staff

December 08, 2021 21:42
Hi Ivana,

Thanks for the further clarification.

If we write the result of the Model.computeIIS() method for $i=2$ and $j=0$ into a file, we see the following:
```
Minimize

Subject To
col0: z[0] + z[4] + z[8] + z[12] = 1
R26: - 9 z[0] + C18 = 0
R30: - 6 z[4] + C22 = 0
R34: - 4 z[8] + C26 = 0
R38: - z[12] + C30 = 0
R43: - alfa[0] + C18 + C22 + C26 + C30 >= 5
fix2: z[8] = 1
Bounds
z[0] free
z[8] free
C18 free
C22 free
C26 free
C30 free
End
```
Setting $\texttt{z[8]=1}$ forces $\texttt{z[0]}$, $\texttt{z[4]}$, and $\texttt{z[12]}$ to 0 because of the constraint $\texttt{col0}$. The constraints $\texttt{R26}$, $\texttt{R30}$, $\texttt{R34}$, and $\texttt{R38}$ then force the variables $\texttt{C18}$, $\texttt{C22}$, $\texttt{C26}$, and $\texttt{C30}$ to 0, 0, 4, and 0, respectively (these are the $\texttt{products}$ variables). Constraint $\texttt{R43}$ is then $\texttt{-alfa[0] >= 5 - 4}$ meaning that the variable $\texttt{alfa}$ should take a negative value. However, the lower bound for this variable is defined to be 0 (note that the default lower bound when using the Model.addMVar() method is 0). To address this, you need to allow the variable $\texttt{alfa}$ take negative values by changing its lower bound to $\texttt{-GRB.INIFINITY}$ or a larger negative value that makes sense for your application.

Best regards,

Maliheh
0
Ivana Rajkovic

December 09, 2021 09:35
Dear Maliheh,

I am afraid that does not help. I added
```
m.addConstr( alfa>= -1000)
```
after the already existing constraint that alfa is non-positive, but the same error happened.

What I get when I print the products matrix after IIS is that the first column is 0,1,4,0, so that this 1 is obviously wrong. That is why I asked about ways how to write the product conditions in some simple way. Is there something like z[:,:k]*x so that I do not have to write the definition of products as a constraint?

Best,

Ivana
0
Maliheh Aramon

Gurobi Staff

December 09, 2021 18:13 Edited
Hi Ivana,

You need to change the lower bound of the variable $\texttt{alfa}$ when you are defining it. Specifically, you need to change:
alfa= m.addMVar(1, name="alfa")
to:
```
alfa= m.addMVar(1, lb=-1000, ub=GRB.INFINITY, name="alfa")
```
The constraint below in your code snippet implies that there is the upper bound 0 on the variable $\texttt{alfa}$ as well. If this is the case, you can remove this constraint and change $\texttt{ub=GRB.INFINITY}$ to $\texttt{ub=0}$.
```
m.addConstr(alfa <=0)
```
I could successfully run your code snippet after making these changes.

What I get when I print the products matrix after IIS is that the first column is 0,1,4,0, so that this 1 is obviously wrong. That is why I asked about ways how to write the product conditions in some simple way. Is there something like z[:,:k]*x so that I do not have to write the definition of products as a constraint?

I am not sure that I truly understand your question here. It is not possible to retrieve variable values when the model is infeasible. The variables $\texttt{products}$ are auxiliary variables and you do not need to necessarily define them. The constraints involving the $\texttt{products}$ variables can be re-written as below:
for k in range(n):
m.addConstr(
gp.quicksum(z[i, j] * x[i] for i in range(n) for j in range(k + 1))
- y[:k].sum()
<= beta[0]
)
m.addConstr(
gp.quicksum(z[i, j] * x[i] for i in range(n) for j in range(k + 1))
- y[: k + 1].sum()
>= alfa[0]
)
However, regardless of how these constraints are implemented, the real issue is that the bounds of the variable $\texttt{alfa}$ needs to be set properly.
Let us know if you still cannot run your code.

Best regards,

Maliheh
1
Ivana Rajkovic

December 09, 2021 19:19
Dear Maliheh,

Your suggestion regarding the constraint with alfa did work, thank you very much.

Best,

Ivana
0

Post is closed for comments.

Avoid unnecessary constraints

Comments

Didn't find what you were looking for?