Comment écrire un fichier MPS simple à soumettre à des serveurs NEOS

J'essaie de trouver un solveur open source qui soit assez rapide pour mon problème. J'essaye de construire un dossier de MPS ainsi je peux le soumettre aux serveurs de NEOS et comparer les performances des différents solveurs. Mon problème implique, dans ses cas les plus difficiles, quelque chose autour de 150 variables entières, mais je commence par un cas simple pour m'aider à comprendre comment fonctionne le format de fichier MPS.Comment écrire un fichier MPS simple à soumettre à des serveurs NEOS

C'est le problème:

minimize : 330.3 * M1 + 1132.88 * M2 + 955.86 * M3 
subject to: 
     20 <= 60 * M2 <= 20.9 
     20 <= 34 * M3 <= 20.9 
     M1 + M2 + M3 = 1

et moi avons écrit le fichier MPS suivant:

NAME problema1 
ROWS 
L K 
L N 
E ONE 
N CUSTO 
COLUMNS 
    M1  ONE  1    CUSTO  330.3 
    M2  K   60 
    M2  ONE  1    CUSTO  1132.88 
    M3  N   34 
    M3  ONE  1    CUSTO  955.86 
RHS 
    KLESS  K   20.9 
    NLESS  N   20.9 
    ONEREST ONE  1 
RANGES 
    RANGE1 K   0.9 
    RANGE2 N   0.9 
ENDATA

En utilisant les solveurs linéaires disponibles à NEOS (https://neos-server.org/neos/solvers/index.html), juste Gurobi peut le résoudre. Les autres trouvent que le problème est infaisable (ce qui n'est pas le cas). Je suis assez confiant que c'est un problème avec mon fichier MPS, mais je ne peux pas comprendre ce que c'est. Qu'est-ce que je fais mal?

Source

2017-01-29 Fausto Richetti Blanco

Peut-être ajouter un peu plus d'arrière-plan. Si vous cherchez seulement un solveur open-source pour les problèmes MIP, il n'y a pas beaucoup de candidats: Coin CBC, GLPK et lpsolve (dans cet ordre pour moi) comme logiciel libre et SCIP (open-source mais non-free; même battu CBC). Remarque: il existe un large fossé entre les solveurs open-source et commerciaux (comme Gurobi, CPLEX et Mosek). Consultez également [ces benchmarks] (http://plato.asu.edu/ftp/milpc.html). Si vous voulez vraiment faire tous ces benchmarks, pourquoi ne pas en utiliser un pour générer ces fichiers MPS standardisés (GLPK ayant peut-être les meilleurs docs)? – sascha

NEOS pour certains solveurs accepte également le format .lp, qui est plus lisible par l'homme que .mps. –

Merci pour votre contribution @sascha Je connais l'écart entre les solveurs open-source et commerciaux. Cependant, les solveurs commerciaux sont très chers lorsque vous devez adapter la solution à un grand nombre d'utilisateurs, ce qui est mon cas. Je pense que, pour la taille de mon problème, un solveur open-source comme ceux que vous avez cités peut faire l'affaire. –

En effet votre fichier MPS a un problème. Les lignes de la section RHS doivent avoir un nom, par ex.

RHS 
    RHS1  K   20.9 
    RHS1  N   20.9 
    RHS1  ONE  1

Fondamentalement, le solveur choisit un jeu RHS. Similaire pour la section RANGES. Je ne suis pas sûr de ce que vous vouliez utiliser les lignes dans la section RANGES.

Source

2017-01-30 04:43:31

Merci Erwin! Cela a résolu mon problème =) La section RANGES est de signaler la contrainte> = aux lignes indiquées. Ainsi, la ligne K sera comprise entre 20,9 et 20 (20,9 spécifiée dans la section RHS - 0,9 spécifiée dans la section RANGES). Idem pour la ligne N –

Oui, j'ai manqué que <= partie (c'était en retard) –

Comment ajouteriez-vous les contraintes entières sur les variables M1, M2 et M3? –

Comment écrire un fichier MPS simple à soumettre à des serveurs NEOS

Répondre

Questions connexes