python - Python cvxopt glpk ilp 返回第一个可行解

Question

我正在使用 cvxopt.glpk.ilp 来解决一个非常复杂的混合整数程序。我想知道是否有办法让程序在找到第一个解决方案后终止？这需要很长时间，一个可行的解决方案对我的目的来说可以很好地工作。

Answer 1

如果我理解正确，您只对可行的解决方案感兴趣？

那么将目标函数设置为零就足够了。

这是整数线性程序的Wikipedia 示例，以下 Python 代码返回可行的解决方案：

import cvxopt
import cvxopt.glpk

# original program maximizing the second variable
# c=cvxopt.matrix([0,-1],tc='d')  

# modified program returning only a feasible solution
c=cvxopt.matrix([0,0],tc='d') 

G=cvxopt.matrix([[-1,1],[3,2],[2,3],[-1,0],[0,-1]],tc='d')
h=cvxopt.matrix([1,12,12,0,0],tc='d')
(status, x)=cvxopt.glpk.ilp(c,G.T,h,I=set([0,1]))
print('status',status)
print('variables',x[0],x[1]) 
print('objective',sum(c.T*x))

Answer 2

如果您使用PuLP（另一个 python 库，如 cvxopt）来调用 glpk 来解决 MIP，则有一个名为maxtime. 如果您设置maxtime=1，那么求解器将在找到第一个解决方案后立即（几乎）终止搜索。我敢打赌 cvxopt 应该有一些类似的 glpk 参数，因为 PuLP 或 cvxopt 只是这些求解器的包装器。

复制粘贴maxtimeXpress 中的参数描述，这是另一个求解器，但我认为 glpk 应该有类似的东西，你可能需要找到它。

The maximum time in seconds that the Optimizer will run before it terminates, including the problem setup time and solution time. For MIP problems, this is the total time taken to solve all the nodes.

        0 = No time limit.
        n > 0 = If an integer solution has been found, stop MIP search after n seconds, otherwise continue until an integer solution is finally found.
        n < 0 = Stop in LP or MIP search after -n seconds.