J'utilise CPLEX en C++ pour résoudre un problème de localisation de hub, un MIP, et j'ai récemment trouvé un ensemble très précis d'entrées que CPLEX considère comme infaisable (c'est-à-dire CPXMIP_INFEASIBLE) alors que le problème est certainement faisable. Le problème semble diverger dans CPLEX pendant le MIP Presolve ; normalement, à ce stade, le problème est réduit à un problème nul, mais pas dans l'ensemble d'entrées infaisable.
J'ai constaté qu'un léger ajustement des données d'entrée peut faire basculer la capacité de CPLEX à trouver une solution. Par exemple, en remplaçant 250,242566 par 250,242567, ou même en arrondissant chaque valeur d'entrée à l'entier le plus proche, j'obtiens une solution parfaitement valide.
L'assouplissement des deux contraintes de relâchement que je possède permettra également de trouver une solution, mais ces contraintes ne devraient pas être brisées compte tenu des données d'entrée. La valeur de ces variables de contrainte après une solution est approximativement 0 mais légèrement négative, par exemple -0.7e-10. (Ceci est suspect puisque les valeurs devraient être supérieures à 0).
Qu'est-ce qui se passe ? Je ne sais pas quoi faire. J'ai essayé d'ajuster certaines des variables CPLEX relatives à la précision (c'est-à-dire CPX_PARAM_NUMERICALEMPHASIS, CPX_PARAM_EPOPT, CPX_PARAM_EPMRK, CPX_PARAM_EPRHS) mais rien n'a aidé. Les données d'entrée elles-mêmes ne nécessitent pas trop de précision : la plus petite valeur des entrées est 1,412 et la plus grande est 1520,984907.
J'apprécierais tout conseil ou suggestion !
UPDATE :
J'ai remarqué que le problème infaisable diverge du problème faisable pendant la résolution du MIP.
En vérifiant CPXgetprestat pour les deux problèmes, une différence notable que je peux voir entre les deux problèmes est que dans le vecteur pcstat une variable ne peut pas être agrégée dans l'ensemble infaisable (c'est-à-dire que la valeur est 0 dans le problème infaisable contre -4 dans le problème faisable).
De plus, les vecteurs ocstat et orstat de CPXgetprestat ont chacun une valeur non nulle dans le problème infaisable (le problème faisable n'en a aucune car il a été réduit à un problème nul), mais je ne sais pas quoi faire de ces deux valeurs. Si orstat[0] == 7 et ocstat[0] == 1, cela signifie-t-il que quelque chose est notable dans la 7ème ligne et la 1ère variable du problème avant Presolve ? Comment pourrais-je vérifier cela ?
J'ai comparé la sortie de CPXwriteprob dans les deux problèmes et rien n'est différent, à part la valeur d'entrée que j'ai modifiée de 0,0001 pour rendre le problème infaisable.
