Comparing the rows of an array
進行中
Hello, I am a new Gurobi user. I tried searching for an answer to this and although I was able to find similar results, I still couldn't find exactly what I was looking for. I am using Python.
I have a variable
x = m.addMVar(shape=(rows,columns), lb=0, ub=12, vtype=GRB.INTEGER)
Let's set rows to 2 and columns to 6 for the purposes of this example.
How can I constrain this so that if row 1 and row 2 are sorted in ascending order, they will not have the same integers? For example, [[0,1,2,3,4,5],[5,4,3,2,1,0]] would NOT be allowed. It seems Gurobi neither supports sorting the variables or testing inequality. I also can't use a counter, so as an inexperienced user I have no idea where to start with this.
Help is much appreciated. Thank you!
-
Hi Teemu,
Any restriction on the values the decision variables can take should be formulated via adding constraints to the model.
- The Gurobi Python MVar object does not support methods such as sorting.
- You can also check the article Why doesn't Gurobi support strict inequality constraints like x < a?
Let us consider your example problem where \(x_{ij}\) is defined to be an integer variable between 0 and 12 assigned to row \(i\) and column \(j\).
- Further let us assume that there are already constraints enforcing the variables in each row take different values, i.e., \(|x_{ij} - x_{ik}| \geq 1, ~~\forall i, j, k\). To enforce the constraint that two rows cannot contain the exact same values, it would then suffice to add the constraint \(|\sum_j x_{ij} - \sum_j x_{lj}| \geq 1, ~~\forall i, l\). You can use the MVar.sum(axis=1) method to sum along the column axis and use the general constraint helper function abs_() to model the absolute value.
- If the variables in a row can take similar values, it would be likely easier to define new binary decision variable \(y_{ijk}\) to be equal 1 if the integer value \(k\) is assigned to cell \((i, j)\). This definition would allow defining the number of values \(k\) assigned to row \(i\) as \(\sum_{j} y_{ijk}\). To enforce that rows \(i\) and \(l\) do not contain the exact same values, it would then suffice to ensure that there is at least one integer \(k\) that does not appear the exact number of times in both rows \(i\) and \(l\): \(\sum_k |\sum_j y_{ijk} - \sum_j y_{ljk}| \geq 1, ~~\forall i, l\). Of course, we would also need to have constraints in the form \(\sum_k y_{ijk} = 1, ~~\forall i, j\) to ensure exactly one integer value \(k\) is assigned to each cell \((i, j)\).
Hope this helps.
Best regards,
Maliheh
2 -
Thank for for your reply Maliheh! This seems like a great solution, and the second example you give is what I need. It is still quite complicated for a starting Gurobi user. Do you have any tips where to start with the code?
I tried writing the constraint for the first two rows:
x = m.addMVar(shape=(rows, columns), lb=0, ub=12, vtype=GRB.INTEGER)
y = m.addVars(range(rows), range(columns), range(13), vtype=GRB.BINARY)
for i in range(rows):
for j in range(columns):
for k in range(13):
m.addConstr((y[i, j, k] == 1) >> (x[i, j] == k))
m.addConstr(quicksum(abs_(quicksum([y[0, j, k] for j in range(columns)]) - quicksum([y[1, j, k] for j in range(columns)])) for k in range(13)) >= 1)but I am getting an error message:
TypeError: unsupported operand type(s) for +=: 'gurobipy.LinExpr' and 'GenExprAbs'.
What is wrong? It must be clear for a seasoned user, but as I said, I am just starting out.
1 -
Correction: y should of course be
y = m.addMVar(shape=(rows, columns, 13), vtype=GRB.BINARY)
1 -
Hi Teemu,
It would be easier to define variables as Gurobi Var objects and not Gurobi MVar objects. See the script below as an example of how to implement this:
import gurobipy as gp
from gurobipy import GRB
model = gp.Model("example")
rows, columns, K = 2, 6, 13
y = model.addVars(rows, columns, K, vtype=GRB.BINARY, name="y")
# Each cell (i, j) is assigned to exactly one k value
model.addConstrs(
(y.sum(i, j, "*") == 1 for i in range(rows) for j in range(columns)),
name="assign_exactly_one_value",
)
# Define an auxiliary variable z to represent the number of distinct k assigned
# to each row i
z = model.addVars(K, rows, vtype=GRB.INTEGER, name="z")
# Define the number of distinct k per row
model.addConstrs(
(z[k, i] == y.sum(i, "*", k) for i in range(rows) for k in range(K)),
name="num_per_row",
)
# Define auxiliary variables to represent z[k, i] - z[k, l] and its absolute value
diff = model.addVars(
K, rows, rows, lb=-GRB.INFINITY, vtype=GRB.INTEGER, name="diff"
)
diff_abs = model.addVars(K, rows, rows, vtype=GRB.INTEGER, name="diff_abs")
for i in range(rows):
for l in range(i+1, rows):
for k in range(K):
model.addConstr(
diff[k, i, l] == z[k, i] -z[k, l],
name=f"diff_row{i}_row{l}_value{k}",
)
model.addConstr(
diff_abs[k, i, l] == gp.abs_(diff[k, i, l]),
name=f"diff_abs_row{i}_row{l}_value{k}",
)
# Define constraints that two rows do not have the exact same values
for i in range(rows):
for l in range(i+1, rows):
model.addConstr(
diff_abs.sum("*", i, l) >= 1, name=f"distinct_row{i}_row{l}"
)Yes, it is a bit complicated. What is the underlying problem you are trying to solve?
Best regards,
Maliheh
1 -
Thank you again for the reply. I will need to study this code carefully. I am actually trying to solve a musical problem called an all-partition array, which has long interested me. The part of the problem I was first trying to tackle in to generate unique rows in the way I described. There are additional constraints to this (such as that each row needs to sum to 12) but I decided to begin with just this one constraint. There has been some research done on the problem, but I need my own version with a couple differences (my version would try to construct an all-partition array without repetition of pitch classes). I was first testing the code with two rows, but in a final array there would be 58 rows because there are 58 partitions of 12 into six or smaller parts. I was able to solve much smaller arrays in working with some other Python modules, but I thought that Gurobi might be better suited for larger problems.
0
サインインしてコメントを残してください。
コメント
5件のコメント