julia - 最小化最大变量

Question

我有一个混合整数规划问题。目标函数是向量中最大变量值的最小化。变量 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，直到解决方案可行。这真的是最好的方法吗？

Answer 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

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