如何使用PuLP和Gurobi求解器设置MIP起始值(初始解)?

7

我正在使用Python中的PuLP模块来制定一个混合整数规划。我正试图通过PuLP接口设置一个可行解(即程序起始点的可行解)。

有关如何设置MIP start的详细信息在这里给出。

PuLP软件包的开发人员声称您可以通过PuLP接口访问完整的Gurobi模型这里

下面粘贴了两个完整的模型。我尽可能地缩小了它们的大小,同时防止gurobi求解器使用启发式方法找到最优值。

我已经尝试在两个模型中设置初始解(为最优值),但在PuLP模型中被忽略,在gurobipy模型中按预期工作。

如何通过PuLP接口为Gurobi求解设置初始解?
from pulp import *

prob = LpProblem("min example",LpMinimize)

x1=LpVariable("x1",0,None,LpInteger)
x2=LpVariable("x2",0,None,LpInteger)
x3=LpVariable("x3",0,None,LpInteger)
x4=LpVariable("x4",0,None,LpInteger)

# Objective function
prob += 3*x1 + 5*x2 + 6*x3 + 9*x4

# A constraint
prob += -2*x1 + 6*x2 -3*x3 + 4*x4 >= 2, "Con1"
prob += -5*x1 + 3*x2 + x3 + 3*x4 >= -2, "Con2"
prob += 5*x1 - x2 + 4*x3 - 2*x4 >= 3, "Con3"

# Choose solver, and set it to problem, and build the Gurobi model
solver = pulp.GUROBI()
prob.setSolver(solver)
prob.solver.buildSolverModel(prob)

# Attempt to set an initial feasible solution (in this case to an optimal solution)
prob.solverModel.getVars()[0].start = 1
prob.solverModel.getVars()[1].start = 1
prob.solverModel.getVars()[2].start = 0
prob.solverModel.getVars()[3].start = 0

# Solve model
prob.solve()

# Status of the solution is printed to the screen
print "Status:", LpStatus[prob.status]

# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
    print v.name, "=", v.varValue

# Optimised objective function value is printed to the screen
print "OF = ", value(prob.objective)

返回哪些内容:

Optimize a model with 3 rows, 4 columns and 12 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 6e+00]
  Objective range [3e+00, 9e+00]
  Bounds range    [0e+00, 0e+00]
  RHS range       [2e+00, 3e+00]
Found heuristic solution: objective 12
Presolve removed 0 rows and 1 columns
Presolve time: 0.00s
Presolved: 3 rows, 3 columns, 9 nonzeros
Variable types: 0 continuous, 3 integer (0 binary)

Root relaxation: objective 7.400000e+00, 1 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0    7.40000    0    1   12.00000    7.40000  38.3%     -    0s
H    0     0                       8.0000000    7.40000  7.50%     -    0s

Explored 0 nodes (1 simplex iterations) in 0.00 seconds
Thread count was 8 (of 8 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 8.000000000000e+00, best bound 8.000000000000e+00, gap 0.0%
('Gurobi status=', 2)
Status: Optimal
x1 = 1.0
x2 = 1.0
x3 = -0.0
x4 = -0.0
OF =  8.0

其次,我可以使用gurobipy模块来实现相同的模型,但在这种情况下,实际上会使用MIP起始值:

from gurobipy import *

m = Model("min example")
m.modelSense = GRB.MINIMIZE

objFcnCoeffs = [3, 5, 6, 9]
xVars = []
for i in range(4):
    xVars.append(m.addVar(vtype=GRB.INTEGER, obj=objFcnCoeffs[i], name="Open%d" % i))

# Update model to integrate new variables
m.update()

# Constraints
m.addConstr(-2*xVars[0] + 6*xVars[1] -3*xVars[2] + 4*xVars[3] >= 2, "Con1")
m.addConstr(-5*xVars[0] + 3*xVars[1] + xVars[2] + 3*xVars[3] >= -2, "Con2")
m.addConstr(5*xVars[0] - xVars[1] + 4*xVars[2] - 2*xVars[3] >= 3, "Con3")


# Attempt to set an initial feasible solution (in this case to an optimal solution)
startValues = [1, 1, 0, 0]
for i in range(4):
    xVars[i].start = startValues[i]

# Solve model
m.optimize()

# Print solution
print('\nTOTAL COSTS: %g' % m.objVal)
for i in range(4):
    print('\n xVar[%s] = %g' % i, xVars[i])

这将返回:

Optimize a model with 3 rows, 4 columns and 12 nonzeros
Coefficient statistics:
  Matrix range    [1e+00, 6e+00]
  Objective range [3e+00, 9e+00]
  Bounds range    [0e+00, 0e+00]
  RHS range       [2e+00, 3e+00]
Found heuristic solution: objective 12
Presolve removed 0 rows and 1 columns
Presolve time: 0.00s
Presolved: 3 rows, 3 columns, 9 nonzeros

Loaded MIP start with objective 8

Variable types: 0 continuous, 3 integer (0 binary)

Root relaxation: infeasible, 0 iterations, 0.00 seconds

Explored 0 nodes (0 simplex iterations) in 0.00 seconds
Thread count was 8 (of 8 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 8.000000000000e+00, best bound 8.000000000000e+00, gap 0.0%

TOTAL COSTS: 8

 xVar[0] = 1

 xVar[1] = 1

 xVar[2] = 0

 xVar[3] = 0

你能解释一下这里 "xVars[i].start" 的用途吗?我查阅了文档,但似乎对我来说并没有太多意义。 - Akshay Sapra
它正在尝试为求解器设置一个初始解,以便进行搜索。但请参见下面的答案,了解如何使其正常工作,并评论缺乏文档的情况。 - kabdulla
2个回答

8
您可以这样设置起始值:
prob.solverModel.getVars()[0].start = 1

然后,您可以使用此调用解决该模型。

prob.solve().

如果您调用 prob,原始值不会被更改。

prob.solver.callSolver(prob)

Gurobi将使用起始向量。

这个完美地运行了,谢谢。我认为我对 pulp.pulp.LpProblemgurobipy.Model 类的理解还有些局限。你能指点我一些文档来帮我提高吗? - kabdulla
1
非常感谢您回答这个问题。Pulp和Gurobi之间的交互并没有很好地记录下来,但是如果您查看solvers.py中的代码,您会发现在建立模型之后,gurobi变量和模型会附加到pulp变量和模型上。如果您正在进行这种级别的求解器特定建模,我建议您花30分钟左右将您的pulp模型转换为适当的gurobi模型(语法非常相似),然后从那里继续。Stu - Stuart Mitchell

1

虽然回答有点晚,但希望能对新来的访客有所帮助。从PuLP 2.3版本开始,常用的warmStart接口支持GUROBI api。按照这里的说明here,您应该能够在不需要调整pulp内部或gurobi包的情况下启动gurobi solver。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接