Mixte-Entier Solution optimale la plus proche dans Matlab

Question

Est-il possible de trouver la solution la plus proche optimale pour un problème d'entier mixte? Par exemple, je voudrais que le problème simplifié ci-dessous:

f = [1;1;1]; 
intcon = 1:3; 

Aeq = [0.99,0.97,0.15]; 
beq = 0.16; 
lb = zeros(3,1); 
ub = [1;1;1]; 

x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub) 

pour revenir x=[0;0;1] comme cela est le plus proche solution entière à la valeur objective de 0.16. Au lieu actuellement, il retourne

Intlinprog arrêté car aucun point satisfait aux contraintes.

Ne doit pas nécessairement exécuter intlinprog. Idéalement, il devrait également fonctionner si beq est faible, par exemple 0.14.

Answer 1

Vous pouvez introduire des variables de jeu pour permettre une violation de contrainte en cas de besoin comme suit:

largeValue = 100; % choose some large value to penalise the constraint violation 
f_ = [f; largeValue; largeValue]; % penalise both slack variables 
Aeq_ = [Aeq, 1, -1]; % add a positive and negative slack variable to the constraint 
beq_ = beq; 
lb_ = [lb; 0; 0]; % limit the constraint to a positive number 
ub_ = [ub; inf; inf]; 

x_ = intlinprog(f_,intcon,[],[],Aeq_,beq_,lb_,ub_); % solve the adapted problem 
x = x_(1:3) % extract the solution of the original problem 

Remarques

• J'ai ajouté deux (positifs) variables d'écart, l'un pour un positif violation de contrainte et une autre pour une violation de contrainte négative.

• Vous devriez pénaliser les variables lâches avec une grande valeur, sinon il est utile de violer vos contraintes plus que strictement nécessaire. serait une approche plus générale pour déterminer une bonne valeur sur la base des dépénalisation des valeurs dans f et Aeq, par exemple

  largeValue = 2*max(abs(f))/min(abs(Aeq(Aeq ~= 0)))