Python混合整数非线性规划

Question

我正在为一个对设备有多个离散选项的制造设施解决一个设计优化问题(例如，选择一个0.5,1,2,5)。成本M是固定的，但零件的数量β是另一个离散变量，需要构造n总单元。下面是一个演示这个问题的简化的、最小的例子：

import numpy as np
from gekko import GEKKO
m = GEKKO()
n = 100
# select one of the Special Ordered Set
α = m.sos1([0.5, 1, 2, 5])
# integer variables
β = m.Array(m.Var,n,integer=True,lb=1,ub=5)
# log transform
δ = [m.log(b) for b in β] 
# matrix
M = np.random.rand(n,n)
# constraints
Mδ = M.dot(δ)
m.Equations([α*x>50 for x in Mδ])
# objective
m.Minimize(α)
# solve
m.solve()
print('α: ', α.value[0])
print('β: ', β)

对所有可行解进行详尽的搜索对于5^100 x 4 = 3e70可能的可行解来说是不实际的。这个简化的问题在30秒内用大约100个整数变量求解。

 Number of state variables:            205
 Number of total equations: -          102
 Number of slack variables: -          100

 ---------------------------------------------------
 Solver         :  APOPT (v1.0)
 Solution time  :    33.4135999999999      sec
 Objective      :    1.00000000000000     
 Successful solution
 ---------------------------------------------------
 
α:  1.0
β:  [[3.0] [4.0] [4.0] [5.0] [4.0] [3.0] [3.0] [3.0] [3.0] [5.0] [4.0] [4.0]
 [4.0] [4.0] [3.0] [3.0] [4.0] [4.0] [3.0] [3.0] [4.0] [3.0] [3.0] [4.0]
 [4.0] [4.0] [5.0] [3.0] [1.0] [4.0] [4.0] [4.0] [3.0] [4.0] [4.0] [3.0]
 [3.0] [3.0] [4.0] [4.0] [3.0] [4.0] [1.0] [3.0] [4.0] [3.0] [3.0] [4.0]
 [3.0] [3.0] [4.0] [4.0] [3.0] [1.0] [3.0] [3.0] [3.0] [3.0] [3.0] [3.0]
 [4.0] [3.0] [3.0] [4.0] [4.0] [4.0] [2.0] [3.0] [1.0] [4.0] [4.0] [3.0]
 [3.0] [3.0] [4.0] [4.0] [3.0] [3.0] [4.0] [3.0] [3.0] [4.0] [3.0] [3.0]
 [3.0] [2.0] [4.0] [5.0] [4.0] [2.0] [3.0] [4.0] [3.0] [4.0] [1.0] [3.0]
 [5.0] [3.0] [4.0] [5.0]]

一个潜在的解决方案是在第一个可行的整数解可用时终止求解器，而不是迭代直到满足间隙容限。然而，这可能会返回一个次优解。提高解决速度的策略是什么？

Answer 1

求解者迭代总结可以给出如何提高求解速度的建议。以下是一些建议：

Initialization

如果分支和界的第一个NLP (非整数解决方案)需要一段时间才能解决，那么尝试使用IPOPT NLP解决程序进行初始化：

# solve
for i in [3,1]:
    m.options.SOLVER=i
    m.solve()

初始化将APOPT的第一次迭代时间从1.57秒缩短到0.1秒，以便在迭代1上获得一个解决方案：

 ----------------------------------------------
 Steady State Optimization with APOPT Solver
 ----------------------------------------------
Iter: 1 I:  0 Tm: 0.10 NLPi: 2 Dpth: 0 Lvs: 3 Obj: 7.60E-01 Gap: NaN
Iter: 2 I: -1 Tm: 0.05 NLPi: 0 Dpth: 1 Lvs: 2 Obj: 7.60E-01 Gap: NaN
Iter: 3 I: -1 Tm: 0.09 NLPi: 1 Dpth: 1 Lvs: 1 Obj: 7.60E-01 Gap: NaN

但是IPOPT需要3.09秒才能找到最初的解决方案，因此没有节省时间。

APOPT求解器选项

有一些APOPT求解器选项可以帮助提高解决方案的速度。如果不可行的NLP问题占用不成比例的解决时间，请将nlp_maximum_iterations设置为较低的数目，以终止不能快速收敛的试用解决方案。minlp_branch_method=1对这个问题的解决时间有积极的影响，如深度优先搜索，以快速识别初始整数解。这有助于消除候选解决方案，并修剪树枝和绑定树。另一个要尝试的解决方案是minlp_gap_tol对成功的解决方案具有更大的容忍度。

m.solver_options = [# nlp sub-problem max iterations
                    'nlp_maximum_iterations 50', \
                    # 1 = depth first, 2 = breadth first
                    'minlp_branch_method 1', \
                    # covergence tolerance
                    'minlp_gap_tol 0.01']

将随机种子设置为运行直接比较矩阵M的相同随机数。

# same random numbers
np.random.seed(0)

使用相同的随机数，这些选项将解决方案时间从7.86秒提高到4.87秒。

import numpy as np
from gekko import GEKKO
m = GEKKO()

# same random numbers
np.random.seed(0)

m.solver_options = [# nlp sub-problem max iterations
                    'nlp_maximum_iterations 50', \
                    # 1 = depth first, 2 = breadth first
                    'minlp_branch_method 1', \
                    # covergence tolerance
                    'minlp_gap_tol 0.01']

n = 100
# select one of the Special Ordered Set
α = m.sos1([0.5, 1, 2, 5])
# binary variables
β = m.Array(m.Var,n,integer=True,lb=1,ub=5)
# log transform
δ = [m.log(b) for b in β]
# matrix
M = np.random.rand(n,n)
# constraints
Mδ = M.dot(δ)
m.Equations([α*x>50 for x in Mδ])
# objective
m.Minimize(α)
# solve
m.solve()
print('α: ', α.value[0])
print('β: ', β)

 ----------------------------------------------
 Steady State Optimization with APOPT Solver
 ----------------------------------------------
Iter:  1 I:  0 Tm: 1.57 NLPi: 24 Dpth:  0 Lvs:  3 Obj: 7.60E-01 Gap: NaN
Iter:  2 I: -1 Tm: 0.05 NLPi:  0 Dpth:  1 Lvs:  2 Obj: 7.60E-01 Gap: NaN
Iter:  3 I:  0 Tm: 0.10 NLPi:  2 Dpth:  1 Lvs:  3 Obj: 7.60E-01 Gap: NaN
Iter:  4 I:  0 Tm: 0.30 NLPi:  5 Dpth:  2 Lvs:  5 Obj: 1.00E+00 Gap: NaN
Iter:  5 I:  0 Tm: 0.22 NLPi:  4 Dpth:  3 Lvs:  7 Obj: 1.00E+00 Gap: NaN
Iter:  6 I:  0 Tm: 0.16 NLPi:  3 Dpth:  4 Lvs:  9 Obj: 1.00E+00 Gap: NaN
Iter:  7 I:  0 Tm: 0.16 NLPi:  3 Dpth:  5 Lvs: 11 Obj: 1.00E+00 Gap: NaN
Iter:  8 I:  0 Tm: 0.17 NLPi:  3 Dpth:  6 Lvs: 13 Obj: 1.00E+00 Gap: NaN
Iter:  9 I:  0 Tm: 0.16 NLPi:  3 Dpth:  7 Lvs: 15 Obj: 1.00E+00 Gap: NaN
Iter: 10 I:  0 Tm: 0.17 NLPi:  3 Dpth:  8 Lvs: 17 Obj: 1.00E+00 Gap: NaN
Iter: 11 I:  0 Tm: 0.15 NLPi:  3 Dpth:  9 Lvs: 18 Obj: 1.00E+00 Gap: NaN
Iter: 12 I:  0 Tm: 0.16 NLPi:  3 Dpth: 10 Lvs: 20 Obj: 1.00E+00 Gap: NaN
Iter: 13 I:  0 Tm: 0.20 NLPi:  4 Dpth: 11 Lvs: 22 Obj: 1.00E+00 Gap: NaN
Iter: 14 I:  0 Tm: 0.25 NLPi:  5 Dpth: 12 Lvs: 24 Obj: 1.00E+00 Gap: NaN
Iter: 15 I:  0 Tm: 0.10 NLPi:  2 Dpth: 13 Lvs: 26 Obj: 1.00E+00 Gap: NaN
Iter: 16 I:  0 Tm: 0.10 NLPi:  2 Dpth: 14 Lvs: 28 Obj: 1.00E+00 Gap: NaN
Iter: 17 I:  0 Tm: 0.10 NLPi:  2 Dpth: 15 Lvs: 30 Obj: 1.00E+00 Gap: NaN
--Integer Solution:   1.00E+00 Lowest Leaf:   7.60E-01 Gap:   2.40E-01
Iter: 18 I:  0 Tm: 0.10 NLPi:  2 Dpth: 16 Lvs: 29 Obj: 1.00E+00 Gap: 2.40E-01
Iter: 19 I: -1 Tm: 0.09 NLPi:  1 Dpth:  2 Lvs:  1 Obj: 7.60E-01 Gap: 2.40E-01
Iter: 20 I:  0 Tm: 0.55 NLPi:  5 Dpth:  1 Lvs:  0 Obj: 5.00E+00 Gap: 2.40E-01
 No additional trial points, returning the best integer solution
 Successful solution
 
 ---------------------------------------------------
 Solver         :  APOPT (v1.0)
 Solution time  :    4.86900000000605      sec
 Objective      :    1.00000000000000     
 Successful solution
 ---------------------------------------------------