Minimize the maximum variable

Question

I have a Mixed Integer Programming problem. The objective function is a minimization of the maximum variable value in the a vector. The variable is has an upper bound of 5. The problem is like this:

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)

The max variable is not part of the julia JuMP syntax. So I modified the problem to

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

This solution does the job by solving the problem iterative for starting with a upper bound for the variable at 1 and then increase by one until the solutoin is feasible. Is this really the best way to do this?

Answer 1

The question wants to minimize a maximum, this maximum can be held in an auxiliary variable and then we will minimize it. To do so, add constraints to force the new variable to actually be an upper bound on x. In code it is:

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)

Now we can inspect the solution:

julia> getValue(t)
4.0

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

The actual problem the poster wanted to solve is probably more complex that this, but it can be solved by a variation on this framework.