3

我有一个混合整数编程问题。目标函数是 a 向量中最大变量值的最小化。变量 is 的上限为 5。问题是这样的：

m = Model(solver = GLPKSolverMIP())
@objective(m, Min, max(x[i] for i=1:12))
@variable(m, 0 <= x[i] <= 5, Int)
@constraint(m, sum(x[i] for i=1:12) == 12)
status = solve(m)

max 变量不是 julia JuMP 语法的一部分。所以我将问题修改为 

t=1
while t<=5 && (status == :NotSolved || status == :Infeasible)
    m = Model(solver = GLPKSolverMIP())
    i = 1:12

    @objective(m, Min, max(x[i] for i=1:12))
    @variable(m, 0 <= x[i] <= t, Int)
    @constraint(m, sum(x[i] for i=1:12) == 12)

    status = solve(m)
    t += 1
end

该解决方案通过迭代解决问题来完成这项工作，该问题从 1 处的变量上限开始，然后增加 1 直到解决方案可行。这真的是最好的方法吗？

4

1 回答 1

1

这个问题想要最小化一个最大值，这个最大值可以保存在一个辅助变量中，然后我们将它最小化。为此，请添加约束以强制新变量实际上是x. 在代码中是：

using GLPKMathProgInterface
using JuMP

m = Model(solver = GLPKSolverMIP())

@variable(m, 0 <= x[i=1:3] <= 5, Int)  # define variables
@variable(m, 0 <= t <= 12)             # define auxiliary variable
@constraint(m, t .>= x)                # constrain t to be the max

@constraint(m, sum(x[i] for i=1:3) == 12)   # the meat of the constraints

@objective(m, Min, t)                  # we wish to minimize the max

status = solve(m)

现在我们可以检查解决方案：

julia> getValue(t)
4.0

julia> getValue(x)
3-element Array{Float64,1}:
 4.0
 4.0
 4.0

发帖人想要解决的实际问题可能比这个更复杂，但可以通过这个框架的变体来解决。

于 2017-10-04T22:53:39.063 回答