为什么针对同一个优化问题的这两个版本的 Julia 代码几乎相同却产生不同的结果？

Question

出于教育目的，我正在尝试学习 Julia。特别是，我尝试使用 Julia 和 JuMP 包来解决运筹学问题。

我在 YouTube 上观看了这部精彩的 video。一个名叫 Philip Thomas 的人展示了一个教学示例。不过这个视频是2014年制作的，从那时起，Julia就进化了。

他使用了这个代码：

#=
We are going to the thrift store and need 99 cents. What is the least amount of
weight we need to carry?

i.e. a knapsack problem

We specify that you need at least 99 cents - does the answer change if you need exact change?
=#

using JuMP
using Cbc # Open source solver. Must support integer programming.

m = Model(solver=CbcSolver())

# Variables represent how many of each coin we want to carry
@defVar(m, pennies >= 0, Int)
@defVar(m, nickels >= 0, Int)
@defVar(m, dimes >= 0, Int)
@defVar(m, quarters >= 0, Int)

# We need at least 99 cents
@addConstraint(m, 1 * pennies + 5 * nickels + 10 * dimes + 25 * quarters >= 99)

# Minimize mass (Grams)
# (source: US Mint)
@setObjective(m, Min, 2.5 * pennies + 5 * nickels + 2.268 * dimes + 5.670 * quarters)

# Solve
status = solve(m)

println("Minimum weight: ", getObjectiveValue(m), " grams")
println("using:")
println(round(getValue(pennies)), " pennies") # "round" to cast as integer
println(round(getValue(nickels)), " nickels")
println(round(getValue(dimes)), " dimes")
println(round(getValue(quarters)), " quarters")

他的代码 return 这个结果：

Minimum weight: 22.68 grams
using:
0.0 pennies
0.0 nickels
0.0 dimes
4.0 quarters

我使用的是当前版本的 Julia (1.0)。此外，我使用的是当前版本的 JUMP。当前版本的 Julia 和上面的代码之间存在语法差异。经过反复试验，我能够正确翻译代码，使其在 Julia 1.0 中成为运行:

#=
We are going to the thrift store and need 99 cents. What is the least amount of
weight we need to carry?
i.e. a knapsack problem
We specify that you need at least 99 cents - does the answer change if you need exact change?
=#

using JuMP
using GLPK
using Cbc # Open source solver. Must support integer programming.

model = Model(with_optimizer(GLPK.Optimizer))

# Variables represent how many of each coin we want to carry
@variable(model, pennies >= 0, Int)
@variable(model, nickels >= 0, Int)
@variable(model, dimes >= 0, Int)
@variable(model, quarters >= 0, Int)

# We need at least 99 cents
@constraint(model, 1 * pennies + 5 * nickels + 10 * dimes + 25 * quarters >= 99)

# Minimize mass (Grams)
# (source: US Mint)
@objective(model, Min, 2.5 * pennies + 5 * nickels + 2.268 * dimes + 5.670 * quarters)

# Solve
optimize!(model)

println("Minimum weight: ", objective_value(model), " grams")
println("using:")
println(round(value(pennies)), " pennies") # "round" to cast as integer
println(round(value(nickels)), " nickels")
println(round(value(dimes)), " dimes")
println(round(value(quarters)), " quarters")

有趣的是终端的结果 returned:

Minimum weight: 22.68 grams
using:
0.0 pennies
0.0 nickels
0.0 dimes
4.0 quarters

如您所见，关于最小重量的最终结果保持不变。然而，关于获得什么硬币的决定从 10 角硬币变为 4 25 硬币。

除了句法上的变化，我还修改了求解器，因为最初我无法运行 Cbc。

之后，我又改成了 Cbc，做了这么简单的修改：

model = Model(with_optimizer(Cbc.Optimizer))

经过上面的修改后 "code translation" 更接近原来的选择 Cbc 作为求解器。奇怪的是，程序 return 的预期结果是：

Minimum weight: 22.68 grams
using:
0.0 pennies
0.0 nickels
10.0 dimes
0.0 quarters

但是，我还是一头雾水。根据 documentation 两个求解器都可以求解 MILP（混合整数线性问题）。

为什么会这样？为什么不同的求解器 return 具有相似的配置文件却会产生不同的结果？我在代码翻译过程中是否遗漏了一些细节？

提前致谢。

Answer 1

正如您已经发现的，两种解决方案的目标函数值相同。到达哪个解决方案取决于求解器到达它所经过的路径。

用于解决单个 LP 子问题的 Simplex 优化器可能会出现路径差异。切换变量或行的顺序可能足以在解决方案集中的另一点结束。一些求解器甚至使用随机数生成器来确定哪个变量首先进入 Simplex 算法中的基数（但不是 GLPK）。

得出不同解决方案的另一个原因可能是搜索整数变量的搜索树的顺序。这受到搜索策略的影响（例如深度优先与广度优先）。

为什么针对同一个优化问题的这两个版本的 Julia 代码几乎相同却产生不同的结果？

Why these two versions of Julia code for the same optimization problem are almost identical and produce different results?

optimization

solver

julia

glpk

julia-jump