Avoid unnecessary constraints
回答済み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?
-
正式なコメント
-
Gurobi Staff
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?. -
-
-
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 -
-
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 1Best regards,
Ivana
0 -
-
-
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
EndSetting \(\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,Maliheh0 -
-
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 -
-
-
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):
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.
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]
)Let us know if you still cannot run your code.Best regards,Maliheh1 -
-
Dear Maliheh,
Your suggestion regarding the constraint with alfa did work, thank you very much.
Best,
Ivana
0 -
投稿コメントは受け付けていません。
コメント
7件のコメント