Gurobi Multiple Objective 函数层级降级
Gurobi Multiple Objective Function Hierarchical Degradation
我正在尝试实现一个具有多个 objective 函数（特别是 2 个）的 Gurobi 模型，该模型按字典顺序（在层次结构中）求解，但我 运行 遇到了一个问题，在优化第二个 objective 函数将解决方案降级为第一个，这不应该发生在分层优化中。它将第一个解决方案降低 1，将第二个解决方案降低 5，这可能是我如何分层设置模型的错误吗？这是我设置模型的代码：
m = Model('lexMin Model')
m.ModelSense = GRB.MINIMIZE
variable = m.addVars(k.numVars, vtype=GRB.BINARY, name='variable')
m.setObjectiveN(LinExpr(quicksum([variable[j]*k.obj[0][j] for j in range(k.numVars)])),0)
m.setObjectiveN(LinExpr(quicksum([variable[j]*k.obj[1][j] for j in range(k.numVars)])),1)
for i in range(0,k.numConst):
m.addConstr(quicksum([k.const[i,j]*variable[j] for j in range(k.numVars)] <= k.constRHS[i]))
m.addConstr(quicksum([variable[j]*k.obj[0][j] for j in range(k.numVars)]) >= r2[0][0])
m.addConstr(quicksum([variable[j]*k.obj[0][j] for j in range(k.numVars)]) <= r2[1][0])
m.addConstr(quicksum([variable[j]*k.obj[1][j] for j in range(k.numVars)]) >= r2[1][1])
m.addConstr(quicksum([variable[j]*k.obj[1][j] for j in range(k.numVars)]) <= r2[0][1])
m.Params.ObjNumber = 0
m.ObjNPriority = 1
m.update()
m.optimize()
我仔细检查过，第二个函数的优先级是 0，objective 函数的值与我将错误的函数设置优先级的值相去甚远。当优化第一个函数时，它甚至找到了正确的值，但是当它移动到第二个值时，它选择的值会降低第一个值。
Gurobi 输出如下所示：
Optimize a model with 6 rows, 375 columns and 2250 nonzeros
Model fingerprint: 0xac5de9aa
Variable types: 0 continuous, 375 integer (375 binary)
Coefficient statistics:
Matrix range [1e+01, 1e+02]
Objective range [1e+01, 1e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+04, 1e+04]
---------------------------------------------------------------------------
Multi-objectives: starting optimization with 2 objectives ...
---------------------------------------------------------------------------
Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------
Presolve time: 0.00s
Presolved: 6 rows and 375 columns
---------------------------------------------------------------------------
Multi-objectives: optimize objective 1 () ...
---------------------------------------------------------------------------
Presolve time: 0.00s
Presolved: 6 rows, 375 columns, 2250 nonzeros
Variable types: 0 continuous, 375 integer (375 binary)
Root relaxation: objective -1.461947e+04, 10 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -14619.473 0 3 - -14619.473 - - 0s
H 0 0 -14569.00000 -14619.473 0.35% - 0s
H 0 0 -14603.00000 -14619.473 0.11% - 0s
H 0 0 -14608.00000 -14619.473 0.08% - 0s
H 0 0 -14611.00000 -14618.032 0.05% - 0s
0 0 -14617.995 0 5 -14611.000 -14617.995 0.05% - 0s
0 0 -14617.995 0 3 -14611.000 -14617.995 0.05% - 0s
H 0 0 -14613.00000 -14617.995 0.03% - 0s
0 0 -14617.995 0 5 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 5 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 7 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 3 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 4 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 6 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 6 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 6 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.720 0 7 -14613.000 -14617.720 0.03% - 0s
0 0 -14617.716 0 8 -14613.000 -14617.716 0.03% - 0s
0 0 -14617.697 0 8 -14613.000 -14617.697 0.03% - 0s
0 0 -14617.661 0 9 -14613.000 -14617.661 0.03% - 0s
0 2 -14617.661 0 9 -14613.000 -14617.661 0.03% - 0s
* 823 0 16 -14614.00000 -14616.351 0.02% 2.8 0s
Cutting planes:
Gomory: 6
Cover: 12
MIR: 4
StrongCG: 2
Inf proof: 6
Zero half: 1
Explored 1242 nodes (3924 simplex iterations) in 0.29 seconds
Thread count was 8 (of 8 available processors)
Solution count 6: -14614 -14613 -14611 ... -14569
No other solutions better than -14614
Optimal solution found (tolerance 1.00e-04)
Best objective -1.461400000000e+04, best bound -1.461400000000e+04, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 2 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective -12798
Presolve removed 1 rows and 0 columns
Presolve time: 0.01s
Presolved: 6 rows, 375 columns, 2250 nonzeros
Variable types: 0 continuous, 375 integer (375 binary)
Root relaxation: objective -1.282967e+04, 28 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -12829.673 0 3 -12798.000 -12829.673 0.25% - 0s
0 0 -12829.378 0 4 -12798.000 -12829.378 0.25% - 0s
0 0 -12829.378 0 3 -12798.000 -12829.378 0.25% - 0s
0 0 -12828.688 0 4 -12798.000 -12828.688 0.24% - 0s
H 0 0 -12803.00000 -12828.688 0.20% - 0s
0 0 -12825.806 0 5 -12803.000 -12825.806 0.18% - 0s
0 0 -12825.193 0 5 -12803.000 -12825.193 0.17% - 0s
0 0 -12823.156 0 6 -12803.000 -12823.156 0.16% - 0s
0 0 -12822.694 0 7 -12803.000 -12822.694 0.15% - 0s
0 0 -12822.679 0 7 -12803.000 -12822.679 0.15% - 0s
0 2 -12822.679 0 7 -12803.000 -12822.679 0.15% - 0s
Cutting planes:
Cover: 16
MIR: 6
StrongCG: 3
Inf proof: 4
RLT: 1
Explored 725 nodes (1629 simplex iterations) in 0.47 seconds
Thread count was 8 (of 8 available processors)
Solution count 2: -12803 -12798
No other solutions better than -12803
Optimal solution found (tolerance 1.00e-04)
Best objective -1.280300000000e+04, best bound -1.280300000000e+04, gap 0.0000%
因此它找到值 (-14613,-12803) 而不是 (-14614,-12798)
默认MIPGap是1e-4。第一个 objective 的降级幅度小于此。 (1/14614 =~ 0.7 e-4)。如果您降低 MIPGap，您的问题应该会消失。在您的代码中添加
m.setObjective('MipGap', 1e-6)
优化前。
解释此行为的一种方法是，由于您的 MIPGap 为 1e-4，您会接受值为 -14113 的解，即使您没有第二个 objective .
我正在尝试实现一个具有多个 objective 函数（特别是 2 个）的 Gurobi 模型，该模型按字典顺序（在层次结构中）求解，但我 运行 遇到了一个问题，在优化第二个 objective 函数将解决方案降级为第一个，这不应该发生在分层优化中。它将第一个解决方案降低 1，将第二个解决方案降低 5，这可能是我如何分层设置模型的错误吗？这是我设置模型的代码：
m = Model('lexMin Model')
m.ModelSense = GRB.MINIMIZE
variable = m.addVars(k.numVars, vtype=GRB.BINARY, name='variable')
m.setObjectiveN(LinExpr(quicksum([variable[j]*k.obj[0][j] for j in range(k.numVars)])),0)
m.setObjectiveN(LinExpr(quicksum([variable[j]*k.obj[1][j] for j in range(k.numVars)])),1)
for i in range(0,k.numConst):
m.addConstr(quicksum([k.const[i,j]*variable[j] for j in range(k.numVars)] <= k.constRHS[i]))
m.addConstr(quicksum([variable[j]*k.obj[0][j] for j in range(k.numVars)]) >= r2[0][0])
m.addConstr(quicksum([variable[j]*k.obj[0][j] for j in range(k.numVars)]) <= r2[1][0])
m.addConstr(quicksum([variable[j]*k.obj[1][j] for j in range(k.numVars)]) >= r2[1][1])
m.addConstr(quicksum([variable[j]*k.obj[1][j] for j in range(k.numVars)]) <= r2[0][1])
m.Params.ObjNumber = 0
m.ObjNPriority = 1
m.update()
m.optimize()
我仔细检查过，第二个函数的优先级是 0，objective 函数的值与我将错误的函数设置优先级的值相去甚远。当优化第一个函数时，它甚至找到了正确的值，但是当它移动到第二个值时，它选择的值会降低第一个值。
Gurobi 输出如下所示：
Optimize a model with 6 rows, 375 columns and 2250 nonzeros
Model fingerprint: 0xac5de9aa
Variable types: 0 continuous, 375 integer (375 binary)
Coefficient statistics:
Matrix range [1e+01, 1e+02]
Objective range [1e+01, 1e+02]
Bounds range [1e+00, 1e+00]
RHS range [1e+04, 1e+04]
---------------------------------------------------------------------------
Multi-objectives: starting optimization with 2 objectives ...
---------------------------------------------------------------------------
Multi-objectives: applying initial presolve ...
---------------------------------------------------------------------------
Presolve time: 0.00s
Presolved: 6 rows and 375 columns
---------------------------------------------------------------------------
Multi-objectives: optimize objective 1 () ...
---------------------------------------------------------------------------
Presolve time: 0.00s
Presolved: 6 rows, 375 columns, 2250 nonzeros
Variable types: 0 continuous, 375 integer (375 binary)
Root relaxation: objective -1.461947e+04, 10 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -14619.473 0 3 - -14619.473 - - 0s
H 0 0 -14569.00000 -14619.473 0.35% - 0s
H 0 0 -14603.00000 -14619.473 0.11% - 0s
H 0 0 -14608.00000 -14619.473 0.08% - 0s
H 0 0 -14611.00000 -14618.032 0.05% - 0s
0 0 -14617.995 0 5 -14611.000 -14617.995 0.05% - 0s
0 0 -14617.995 0 3 -14611.000 -14617.995 0.05% - 0s
H 0 0 -14613.00000 -14617.995 0.03% - 0s
0 0 -14617.995 0 5 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 5 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 7 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 3 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 4 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 6 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 6 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.995 0 6 -14613.000 -14617.995 0.03% - 0s
0 0 -14617.720 0 7 -14613.000 -14617.720 0.03% - 0s
0 0 -14617.716 0 8 -14613.000 -14617.716 0.03% - 0s
0 0 -14617.697 0 8 -14613.000 -14617.697 0.03% - 0s
0 0 -14617.661 0 9 -14613.000 -14617.661 0.03% - 0s
0 2 -14617.661 0 9 -14613.000 -14617.661 0.03% - 0s
* 823 0 16 -14614.00000 -14616.351 0.02% 2.8 0s
Cutting planes:
Gomory: 6
Cover: 12
MIR: 4
StrongCG: 2
Inf proof: 6
Zero half: 1
Explored 1242 nodes (3924 simplex iterations) in 0.29 seconds
Thread count was 8 (of 8 available processors)
Solution count 6: -14614 -14613 -14611 ... -14569
No other solutions better than -14614
Optimal solution found (tolerance 1.00e-04)
Best objective -1.461400000000e+04, best bound -1.461400000000e+04, gap 0.0000%
---------------------------------------------------------------------------
Multi-objectives: optimize objective 2 () ...
---------------------------------------------------------------------------
Loaded user MIP start with objective -12798
Presolve removed 1 rows and 0 columns
Presolve time: 0.01s
Presolved: 6 rows, 375 columns, 2250 nonzeros
Variable types: 0 continuous, 375 integer (375 binary)
Root relaxation: objective -1.282967e+04, 28 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -12829.673 0 3 -12798.000 -12829.673 0.25% - 0s
0 0 -12829.378 0 4 -12798.000 -12829.378 0.25% - 0s
0 0 -12829.378 0 3 -12798.000 -12829.378 0.25% - 0s
0 0 -12828.688 0 4 -12798.000 -12828.688 0.24% - 0s
H 0 0 -12803.00000 -12828.688 0.20% - 0s
0 0 -12825.806 0 5 -12803.000 -12825.806 0.18% - 0s
0 0 -12825.193 0 5 -12803.000 -12825.193 0.17% - 0s
0 0 -12823.156 0 6 -12803.000 -12823.156 0.16% - 0s
0 0 -12822.694 0 7 -12803.000 -12822.694 0.15% - 0s
0 0 -12822.679 0 7 -12803.000 -12822.679 0.15% - 0s
0 2 -12822.679 0 7 -12803.000 -12822.679 0.15% - 0s
Cutting planes:
Cover: 16
MIR: 6
StrongCG: 3
Inf proof: 4
RLT: 1
Explored 725 nodes (1629 simplex iterations) in 0.47 seconds
Thread count was 8 (of 8 available processors)
Solution count 2: -12803 -12798
No other solutions better than -12803
Optimal solution found (tolerance 1.00e-04)
Best objective -1.280300000000e+04, best bound -1.280300000000e+04, gap 0.0000%
因此它找到值 (-14613,-12803) 而不是 (-14614,-12798)
默认MIPGap是1e-4。第一个 objective 的降级幅度小于此。 (1/14614 =~ 0.7 e-4)。如果您降低 MIPGap，您的问题应该会消失。在您的代码中添加
m.setObjective('MipGap', 1e-6)
优化前。
解释此行为的一种方法是，由于您的 MIPGap 为 1e-4，您会接受值为 -14113 的解，即使您没有第二个 objective .