较低的 Objective 导致更好的解决方案 MILP

Question

在这个优化问题中，我试图根据一些任意公式最大化表示城市“收入”的输出值。公式依赖于离散值，即所谓的改进，其中大部分是求解器可以自由发挥的变量。

我的问题涉及这样一个事实，即如果我专门划分 objective 函数，使它们的幅度更小，它会产生更好的结果。我可以确认，因为如果我然后通过公式获取改进值 (vars) 和运行它们，我会得到更好的结果。

对于代码，大部分是行话，我认为不相关？我会尽量简洁。

m = gekko.GEKKO(remote=False, name="Optimal Build")
m.options.SOLVER = 1
m.solver_options = ['minlp_gap_tol 1.0e-10',
                    'minlp_integer_tol 1.0e-10']

f = FormulasSolver(m)  # Formulas, external
imps = f.improvements  # Values for each improvement, ie pollution, 
# base cost, prd rate, max number of improvements per imp type...


x = 27 * [0]  # Array of imps

for i in imps.non_constant():
    x[imps.index(i)] = m.Var(value=0, name=i.name, lb=0, ub=i.building_limit, integer=True)

for i in imps.constant():
    x[imps.index(i)] = m.Const(value=constant_buildings[imps.index(i) - 23], name=i.name)


m.Equation("" Sum of all imps, max number of imps is 50 "" <= 50)
m.Equation("" Sum of commerce affecting imps, max commerce is 100% "") <= 100)

commerce = m.Intermediate("" Sum of improvements that affect commerce "")  # Commerce
pollution_index = m.Intermediate("" Sum of improvements that affect pollution "")  # Pollution Index

m.Maximize((
    f.fixed_city_income(2500, 2500, commerce, pollution_index, 365, x[15], x[16])  # Fixed Income
    - sum("" Base cost for every imp "")  # Fixed Cost
    + sum("" Every producing imp "")  # Variable Income
    - sum("" Every manufacturing imp has an associated v cost "")  # Variable Cost
) / 1) <-- Relevant part

m.solve(disp=True)

Iter:     1 I:  0 Tm:      0.00 NLPi:    4 Dpth:    0 Lvs:    3 Obj: -1.05E+06 Gap:       NaN
--Integer Solution:  -1.04E+06 Lowest Leaf:  -1.05E+06 Gap:   9.67E-03
Iter:     2 I:  0 Tm:      0.00 NLPi:    2 Dpth:    1 Lvs:    2 Obj: -1.04E+06 Gap:  9.67E-03
Iter:     3 I:  0 Tm:      0.00 NLPi:    4 Dpth:    1 Lvs:    4 Obj: -1.06E+06 Gap:  9.67E-03
--Integer Solution:  -1.05E+06 Lowest Leaf:  -1.06E+06 Gap:   4.78E-03
Iter:     4 I:  0 Tm:      0.00 NLPi:    2 Dpth:    2 Lvs:    3 Obj: -1.05E+06 Gap:  4.78E-03
.
.
.
Objective      :  -1050396.901745295

运行返回到公式中的 imps 值将确认此优化给出的 imps 确实导致了 1,050,396.90

的“收入”

现在更改 objective 公式：

m.Maximize((
    f.fixed_city_income(2500, 2500, commerce, pollution_index, 365, x[15], x[16])  # Fixed Income
    - sum("" Base cost for every imp "")  # Fixed Cost
    + sum("" Every producing imp "")  # Variable Income
    - sum("" Every manufacturing imp has an associated v cost "")  # Variable Cost
) / 100) <-- Relevant part

Iter:     1 I:  0 Tm:      0.00 NLPi:   12 Dpth:    0 Lvs:    3 Obj: -1.06E+04 Gap:       NaN
--Integer Solution:  -1.06E+04 Lowest Leaf:  -1.06E+04 Gap:   1.25E-03
Iter:     2 I:  0 Tm:      0.00 NLPi:    2 Dpth:    1 Lvs:    2 Obj: -1.06E+04 Gap:  1.25E-03
Iter:     3 I:  0 Tm:     -0.00 NLPi:    1 Dpth:    1 Lvs:    4 Obj: -1.06E+04 Gap:  1.25E-03
Iter:     4 I:  0 Tm:      0.00 NLPi:    1 Dpth:    1 Lvs:    5 Obj: -1.06E+04 Gap:  1.25E-03
.
.
.
Objective      :  -10613.94773200687

通过公式获得新值 -> 1,061,394.77 因此更好的解决方案

Answer 1

当函数和变量被缩放时，优化算法可以更好地执行（参见 Chapter 2 of the Design Optimization 书的第 2.4 节）。这通常解释了为什么求解器可以更快地找到解决方案但不会更改凸优化问题的解决方案（一个局部最小值）。

如果存在多个局部最小值（非凸问题），则缩放或变量初始化会影响解决方案。一个观察结果是，在第一次 MINLP 迭代（不使用整数变量的 NLP 解决方案）中发现了较低的 objective。问题中还有另一个 objective 未缩放，或者问题是非凸的。

未缩放

Iter: 1 I:  0 Tm: 0.00 NLPi:    4 Dpth:    0 Lvs:    3 Obj: -1.05E+06

缩放

Iter: 1 I:  0 Tm: 0.00 NLPi:   12 Dpth:    0 Lvs:    3 Obj: -1.06E+04

如果问题是非凸的，那么尝试不同的初始条件。并行化可以提供帮助：How to do parallel Python Gekko? 但请使用 GEKKO(remote=False) 在本地解决并避免 public 服务器过载。

较低的 Objective 导致更好的解决方案 MILP

Lower Objective leads to better solution MILP

python

gekko