Réduire la variable maximale

Question

J'ai un problème de programmation d'entier mixte. La fonction objectif est une minimisation de la valeur de la variable maximale dans le vecteur a. La variable est a une limite supérieure de 5. Le problème est comme ceci:

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) 

La variable max ne fait pas partie de la syntaxe julia JUMP. Donc, j'ai modifié le problème

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 

Cette solution fait le travail en résolvant le problème itératif pour commencer par une limite supérieure pour la variable à 1 puis augmenter d'un jusqu'à ce que le solutoin est possible. Est-ce vraiment la meilleure façon de le faire?

Answer 1

La question veut minimiser un maximum, ce maximum peut être maintenu dans une variable auxiliaire et ensuite nous allons le minimiser. Pour ce faire, ajoutez des contraintes pour forcer la nouvelle variable à être réellement une borne supérieure sur x. Dans le code est:

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) 

Maintenant, nous pouvons inspectent la solution:

julia> getValue(t) 
4.0 

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

Le problème réel de l'affiche a voulu résoudre est probablement plus complexe que cela, mais il peut être résolu par une variation ce cadre.