model outputs wrong value for some variables
回答済みI am trying to use `gurobipy` to solve a mapping problem with three objective functions.
Here is my program:
import gurobipy as gp
from gurobipy import GRB
from gurobipy import *
m = gp.Model()
# x: mapping from set A (size 2) to set B (size 3)
x = m.addVars(2,3, vtype=GRB.BINARY)
c = m.addVars(3, vtype=GRB.BINARY)
# c indicates the number of item in set B that is mapped
for j in range(3):
m.addGenConstrIndicator(c[j], True, x.sum('*', j), GRB.GREATER_EQUAL, 1.0)
d = m.addVars(2, vtype=GRB.BINARY)
# d indicates the number of item in set A that is mapped
for i in range(2):
m.addGenConstrIndicator(d[i], True, x.sum(i, '*'), GRB.GREATER_EQUAL, 1.0)
p = [[1,2,3], [6,0,-4]]
# term1: maximize the sum of product
m.setObjectiveN(-sum(x[i,j]*p[i][j] for i in range(2) for j in range(3)), index=0)
# term2: maximize c
m.setObjectiveN(-c.sum(), index=1, priority=1, name='term2')
# term3: minimize d
m.setObjectiveN(d.sum(), index=2, priority=2, name='term3')
m.optimize()
for i in range(m.NumObj):
m.setParam(gp.GRB.Param.ObjNumber, I)
print(f"Obj {i+1} = {m.ObjNVal}")
Obj 1 = -12.0
Obj 2 = -3.0
Obj 3 = 0.0
print(x)
{(0, 0): <gurobi.Var C0 (value 1.0)>,
(0, 1): <gurobi.Var C1 (value 1.0)>,
(0, 2): <gurobi.Var C2 (value 1.0)>,
(1, 0): <gurobi.Var C3 (value 1.0)>,
(1, 1): <gurobi.Var C4 (value 1.0)>,
(1, 2): <gurobi.Var C5 (value 0.0)>}
print(c)
{0: <gurobi.Var C6 (value 1.0)>,
1: <gurobi.Var C7 (value 1.0)>,
2: <gurobi.Var C8 (value 1.0)>}
print(d)
# incorrect value, should be (1,1)
{0: <gurobi.Var C9 (value 0.0)>, 1: <gurobi.Var C10 (value 0.0)>}
However, the objective function with `d` seems to be ignored. And the value of `d` is not correct and not updated. I tried with higher priority and weight, they all output the same.
Even though the solver failed to optimize the third term (the one with `d`), the value of `d` should at least be correct (which is (1,1)), right?
Is there anything wrong with my programming and modeling? Thank you!
-
正式なコメント
-
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 Danning,
Given the code, the behaviour you see is expected. Gurobi optimizes the objective functions in descending order of their priority values. In your model, the objective term_3 has the highest priority and is optimized first. The objectives term_2 and term_1 are then optimized. The Gurobi log file shows the ordering of the objectives optimized at each stage. You should see the following lines in the log file.
Multi-objectives: optimize objective 1 (term3) ...
Multi-objectives: optimize objective 2 (term2) ...
Multi-objectives: optimize objective 3 () ...And the Gurobi hierarchical approach does not allow later objectives to degrade earlier objectives, subject to the user-defined tolerances. For example, Gurobi will not degrade the objective term_3 in order to obtain a better solution for the objective term_1.
Please note that the constraint below only ensures that if \(d_i=1\), then \(\sum_j x_{ij} \geq 1\). On the other hand, if \(d_i=0\), the linear constraint might be violated or not.
for i in range(2):
m.addGenConstrIndicator(d[i], True, x.sum(i, '*'), GRB.GREATER_EQUAL, 1.0)Your comment "d indicates the number of item in set A that is mapped" is not super clear to me. I guess you would like to ensure \(d_i\) equals 1 if the item \(i\) in set \(A\) is mapped to one or more items in set \(B\) (it seems that your model assumes an item in set \(A\) can be mapped to one or more items in set \(B\)). If this is what you are looking for, the correct way to represent the constraint is shown below where three is the total number of items in set \(B\).
m.addConstrs(x.sum(i, "*") <= 3 * d[i] for i in range(2))
If not, please clarify what you would like to represent as a constraint.
Best regards,
Maliheh
0 -
-
Hi Maliheh,
Thanks for the clarification.
For the variable `d`, the formal definition is:
`d_i = 1 if \sum_{1\leq j \leq m} x_{i,j}\geq 1`, in this case `m=2`
`d_i = 0 otherwise`
For the definition you proposed, I think it doesn't hold when
x.sum(i, "*")=0but `d[i]` can still be 1.
You mentioned that "Gurobi will not degrade the objective term_3 in order to obtain a better solution for the objective term_1. ". What if I give the same priority to all terms? In what hirarchical order would gurobi use?
Also, If I define the objective functions as
m.setObjectiveN(-sum(x[i,j]*p[i][j] for i in range(2) for j in range(3)), index=0, weight=w1)
# term2: maximize c
m.setObjectiveN(-c.sum(), index=1, weight=w2, name='term2')
# term3: minimize d
m.setObjectiveN(d.sum(), index=2, weight=w3, name='term3')Would gurobi give me the minimum value of `m`? `m` is:
m = w1 * term1 + w2* term2 + w3*term3 ...
In another word, would gurobi give me a global optimal solution instead of solving each terms hierarchically?
Thank you.
Best Regards,
Danning
0 -
-
-
Hi Danning,Yes, we modelled the constraint below before:\[\mathrm{if~~} d_i =1 \implies \sum_j x_{ij} \geq 1\]However, you are interested in modelling different constraints:\[\mathrm{if~~} \sum_{1 \leq j \leq 2} x_{ij} \geq 1\ \implies d_i = 1 \]\[\mathrm{if~~} \sum_{1 \leq j \leq 2} x_{ij} = 0 \ \implies d_i = 0 \]Since the indicator variables are not binary, the above does not math the signature of the Gurobi indicator constraints. The above are, however, logically equivalent to:\[\mathrm{if~~} d_i \neq 1 \implies \sum_{1 \leq j \leq 2} x_{ij} \ngeq 1 \mbox{, which is equivalent to:} \mathrm{~~if~~} d_i = 0 \implies \sum_{1 \leq j \leq 2} x_{ij} = 0 \]\[\mathrm{if~~} d_i \neq 0 \implies \sum_{1 \leq j \leq 2} x_{ij} \neq 0 \mbox{, which is equivalent to:} \mathrm{~~if~~} d_i = 1 \implies \sum_{1 \leq j \leq 2} x_{ij} \geq 1 \]Now, you can model both of these two constraints using the Model.addGenConstrIndicator() method.Gurobi supports two approaches for solving a multi-objective optimization problem: blended and hierarchical.To use the blended approach, the user should provide a weight for each objective. Gurobi will then create a single objective being equal to the weighted linear combination of all objectives and will solve a single-objective optimization problem.Let us assume that you assign priorities [2, 2, 1] and weights [5, 3, 1] to your three objectives. Gurobi will first handle the objectives with priority 2 as one blended objective being equal to 5 * obj_1 + 3 * obj_2. And then it will handle the third objective in the next step. You can find more details on how Gurobi solves multi-objective optimization problems in the link shared above.Best regards,Maliheh0 -
-
Hi,
Thank you so much for the explanation.
I found where the problem is. If I define the `d` as this :
d = m.addVars(2, vtype=GRB.BINARY)
for i in range(2):
m.addGenConstrIndicator(d[i], True, x.sum(i, '*'), GRB.GREATER_EQUAL, 1.0)
for i in range(2):
m.addGenConstrIndicator(d[i], False, x.sum(i, '*'), GRB.EQUAL, 0.0)The value of `d` is updated correctly.
I guess it is because I ignored
\[\mathrm{if~~} \sum_{1 \leq j \leq 2} x_{ij} = 0 \ \implies d_i = 0 \]
Thank you for the explanation of the weights and priority. It helps a lot!
Danning
0 -
投稿コメントは受け付けていません。
コメント
5件のコメント