Discussion :

[convexe]

Bonjour à tous,

j'ai un petit problème avec la fonction bintprog sous matlab 7.1.
J'appelle la fonction sur le problème classique :

minimiser f
SC A*x<b
Aeq*x=beq

avec A de taille 600x600 sans préciser de solution initial x0 :
x = bintprog(f,A,b,Aeq,beq);

J'obtiens alors la réponse "The problem is infeasible.".
Pourtant ce problème admet au moins une solution réalisable.
D'ailleurs lorsque je précise le point initial x0, la fonction bintprog répond :

"Optimization terminated." et me renvoie x0.

Y-a-t'il un bug connu avec cette fonction ???

Merci de votre aide.

[Jerome Briot]

Tu pourrais donner un exemple de problème réel ?

[convexe]

C'est pour résoudre un problème de partitionnement :

En gros :
j'ai n objets qui ont tous un coût et je cherche un partitionnement de taille p (p<n) avec comme contrainte que que le partitionnement doit être assez "homogène" par rapport au coût.

Un exemple :
n=5
p=2
cout = [ 50 75 25 25 25 ]

une solution est : [ 1 3 4 ] et [ 2 5 ], c'est bien une partition en 2 sous ensembles de coût 100.

Le problème est modélisé par un problème d'optimisation linéaire binaire,de la forme :

min f
sous contraintes :
A*x<b
Aeq*x=beq
avec x vecteur binaire

avec en gros A et Aeq de taille n² x n²

J'ai programmé la résolution du problème sous matlab.
J'ai une instance (n=25,p=2) , pour laquelle je connais un vecteur x binaire solution du problème qui vérifie bien les contraintes.
Cependant quand je lance la résolution sous matlab sur cette instance avec la fonction bintprog il me dit que le problème est infaisable.
De plus lorsque que je relance la résolution,toujours sur cette même instance, en précisant comme point de départ la solution x que je connais, il ne fait pas d'erreur et me renvoie comme solution optimale x.