Creating complex constraint with Python API

回答済み

tjs

2020年10月29日 17:11 編集済み

I'm attempting to create a constraint using the Gurobi Python API and having an issue. Here is a knapsack example problem that illustrates the issue:

Objective: Maximize dollars of chosen shapes

Constraints:

One of each shape must be chosen
Total weight of chosen shapes must be less than 20
The chosen triangle and the chosen circle must have the same top_color

I'm having issues with the last constraint.

shapes = ['triangle', 'square', 'circle', 'rectangle', 'triangle', 'square', 'circle', 'rectangle', 'triangle', 'square', 'circle', 'rectangle', 'triangle', 'cirlce']
top_color = ['blue', 'red', 'yellow', 'blue', 'red', 'yellow', 'blue', 'red', 'yellow', 'blue', 'red', 'yellow', 'yellow', 'yellow']
bottom_color = ['yellow', 'blue', 'red', 'blue', 'yellow', 'red', 'red', 'yellow', 'blue', 'yellow', 'blue', 'red', 'yellow', 'yellow']
unique_colors = ['yellow', 'blue', 'red']
weight = [2, 3, 4, 7, 6, 4, 5, 7, 8, 2, 1, 3, 1, 2]
dollars = [3 ,3 ,5 ,4 ,3, 8, 6, 7, 7, 5, 6, 4, 7, 7]
weight_limit = 20
n = len(shapes)

model = gp.Model()
model.params.LogToConsole = True
decision_v_shapes = model.addVars(range(n), vtype=GRB.BINARY)

#Maximize Dollars
model.setObjective(gp.quicksum(decision_v_shapes[i] * dollars[i] for i in range(n)), GRB.MAXIMIZE)

#Constraints - Choose only one of each shape
model.addConstr(gp.quicksum(decision_v_shapes[i] for i in range(n) if shapes[i] == 'triangle') == 1)
model.addConstr(gp.quicksum(decision_v_shapes[i] for i in range(n) if shapes[i] == 'square') == 1)
model.addConstr(gp.quicksum(decision_v_shapes[i] for i in range(n) if shapes[i] == 'circle') == 1)
model.addConstr(gp.quicksum(decision_v_shapes[i] for i in range(n) if shapes[i] == 'rectangle') == 1)
model.addConstr(gp.quicksum(decision_v_shapes[i]  for i in range(n)) == 4)

#Constraint - Weight must be under 20
model.addConstr(gp.quicksum(decision_v_shapes[i] * weight[i] for i in range(n)) <= weight_limit)

#Constraint - enforce that the selected triangle and the selected circle have the same top_color
model.addConstr((gp.quicksum(decision_v_shapes[i] + decision_v_shapes[j] for i in range(n) if shapes[i] == 'triangle' for j in range(1, n) if shapes[j] == 'circle' and top_color[i] == top_color[j])) >= 2)
#model.addConstr((gp.quicksum(decision_v_shapes[i] + decision_v_shapes[j] for i in range(n) for j in range(1, n) if shapes[i] == 'triangle' if shapes[j] == 'circle' if top_color[i] == top_color[j])) >= 2)

model.optimize()
print(model.status)

selected_shapes = [str(i) + ' ' + shapes[i] + ' ' + top_color[i] + ' ' + bottom_color[i] + ' ' + str(weight[i]) + ' ' + str(dollars[i]) for i in range(n) if decision_v_shapes[i].X > 0.1]
total_weight = sum(weight[i] for i in range(n) if decision_v_shapes[i].X > 0.1)
print(selected_shapes)
print(model.getObjective().getValue())
print(total_weight)

# 5 square yellow red 4 8
# 7 rectangle red yellow 7 7
# 10 circle red blue 1 6
# 12 triangle yellow yellow 1 7
# 28.0
# 13

#But the chosen circle's top_color (red) doesn't match the chose triangle's top color (yellow)

I don't receive an error, but the solution violates the last constraint.

Something is off with this constraint:

model.addConstr((gp.quicksum(decision_v_shapes[i] + decision_v_shapes[j] for i in range(n) if shapes[i] == 'triangle' for j in range(1, n) if shapes[j] == 'circle' and top_color[i] == top_color[j])) >= 2)

I'm attempting to loop through the decision variables twice and make sure that the triangle and circle that are chosen for the solution have the same top_color.

Any help is greatly appreciated.

3件のコメント

正式なコメント
Simranjit Kaur

Gurobi Staff

2025年06月23日 03:05 編集済み
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?.
Eli Towle

Gurobi Staff

2020年10月30日 02:53 編集済み
There is a typo in the definition of $ \texttt{shapes} $; the last element should be $ \texttt{'circle'} $ instead of $ \texttt{'cirlce'} $.

In the constraint you pointed out, we generate the pairs of indices $ \texttt{(i, j)} $ such that $ \texttt{shapes[i]} $ is a triangle, $ \texttt{shapes[j]} $ is a circle, and the top colors of the two shapes match. The $ \texttt{(i, j)} $ pairs that satisfy this condition are:
```
[(0, 6), (4, 10), (8, 2), (8, 13), (12, 2), (12, 13)]
```
Let $x$ be the model variables. Based on these tuples, the constraint we want is:

$$\begin{align*}x_0 + x _6 = 2 \lor x_4 + x_{10} = 2 \lor \ldots \lor x_{12} + x_{13} = 2,\end{align*}$$

where $ \lor $ is the logical "or." However, the constraint you identified just sums together all of the variables in the list of tuples:

$$\begin{align*}x_0 + 2 x_2 + x_4 + x_6 + 2x_8 + x_{10} + 2 x_{12} + 2 x_{13} &\geq 2.\end{align*}$$

Not only is this constraint not we want, but it also doesn't even affect the feasible region of the model. This constraint is implied by the constraints requiring us to select one triangle shape and one circle shape:

$$\begin{alignat*}{2}x_0 + x_4 + x_8 + x_{12} &= 1 \quad && \textrm{(pick one triangle)} \\ x_2 + x_6 + x_{10} + x_{13} &= 1 && \textrm{(pick one circle).}\end{alignat*}$$

To model the desired constraint, we can create a special weight for our $ n $ variables based on the top color of the corresponding shapes:
```
# yellow: 1, blue: 2, red: 3
tc_weight = {i: unique_colors.index(top_color[i]) + 1 for i in range(n)}
```
This gives us a mapping from variable index to top-color weight:
```
>>> tc_weight
{0: 2, 1: 3, 2: 1, 3: 2, 4: 3, 5: 1, 6: 2, 7: 3, 8: 1, 9: 2, 10: 3, 11: 1, 12: 1, 13: 1}
```
Exactly one triangle and exactly one circle will be chosen. If we want the top colors of the two chosen shapes to match, we can add a constraint that the top-color weighted sum of the triangle variables equals the top-color weighted sum of the circle variables:
```
model.addConstr(gp.quicksum(tc_weight[i] * decision_v_shapes[i] for i in range(n) if shapes[i] == 'triangle') == gp.quicksum(tc_weight[i] * decision_v_shapes[i] for i in range(n) if shapes[i] == 'circle'))
```
This produces the following constraint:

$$\begin{align*}2x_0 + 3x_4 + x_8 + x_{12} &= x_2 + 2x_6 + 3x_{10} + x_{13}\end{align*}$$

Since the $ x $ variables are binary and the (unweighted) variables on each side sum to $ 1 $, the only way this constraint is satisfied is if

$$\begin{align*}x_0 + x _6 = 2 \lor x_4 + x_{10} = 2 \lor \ldots \lor x_{12} + x_{13} = 2.\end{align*}$$

as desired. The solution is:
```
 i      shape     top  bottom  weight  price
--------------------------------------------
 5     square  yellow     red       4      8
 7  rectangle     red  yellow       7      7
12   triangle  yellow  yellow       1      7
13     circle  yellow  yellow       2      7
                           TOTAL:  14     29
```
Finally, because you have constraints that require one of each shape to be chosen, the constraint requiring a total of four shapes to be chosen is redundant.
1
tjs

2020年10月30日 17:50
Thank you very much for the detailed explanation and answer!
0

投稿コメントは受け付けていません。

Creating complex constraint with Python API

コメント

お探しのものを見つけられませんでしたか？