programmation linéaire entier: par exemple et de bons outils?

StackOverflow https://stackoverflow.com/questions/1970686

Question

Trouver un vecteur x qui minimise c. x sous réserve de la contrainte m. x> = b, x entier.

Voici un ensemble d'entrée exemple: 

c : {1,2,3}
m : {{1,0,0},
     {0,1,0},
     {1,0,1}}
b : {1,1,1}

Avec la sortie: 

x = {1,1,0}

Quels sont les bons outils pour résoudre ce genre de problème, et des exemples de la façon de les utiliser?

Était-ce utile?

La solution

Mathematica

Mathematica a cette construction. (NB: Mathematica est pas un logiciel libre.) 

LinearProgramming[c, m, b, Automatic, Integers]

sorties: 

{1, 1, 0}

Autres conseils

GLPK

Je propose une réponse en utilisant glpsol de GLPK, mais j'espère qu'il y aura beaucoup de meilleures façons de le faire (il semble que GLPK est trop puissant / général pour ce genre de cas particulier simple d'un problème de programmation linéaire):

Pour générer le fichier .mps donné ci-dessous vous devez diviser par rangée vos matrices dans un système d'équations, de sorte que la description du problème devient: 

minimize

cost = 1 x_1 + 2 x_2 + 3 x_3

s.t. constraints:

S1 = 1 x_1 + 0 x_2 + 0 x_3
S2 = 0 x_1 + 1 x_2 + 0 x_3
S3 = 1 x_1 + 0 x_2 + 1 x_3

S1 >= 1
S2 >= 1
S3 >= 1

0 <= x1 <= 1
0 <= x2 <= 1
0 <= x3 <= 1

GLPK documentation a des informations détaillées sur le format .mps , mais vous spécifiez les lignes, les colonnes et les limites rhs. Dans les lignes section du « N » et « G » spécifient le type de contrainte (nombre et supérieur, respectivement). Dans la section délimitant la 'UI' indique que les bornes sont nombre entier supérieur Type, forçant la solution à nombre entier.

Pour exécuter le solveur sur la spécification du problème: 

> glpsol --freemps example.mps -o example.out

example.mps fichier: 

NAME          VM
ROWS
 N cost
 G S1
 G S2
 G S3
COLUMNS
 x_1    cost    1.0
 x_1    S1      1.0
 x_1    S3      1.0
 x_2    cost    2.0
 x_2    S2      1.0
 x_3    cost    3.0
 x_3    S3      1.0
RHS 
 RHS1 cost   0.0
 RHS1 S1     1.0
 RHS1 S2     1.0
 RHS1 S3     1.0
BOUNDS
 UI BND1 x_1 1.0
 UI BND1 x_2 1.0
 UI BND1 x_3 1.0
ENDATA

sorties: 

Problem:    VM
Rows:       4
Columns:    3 (3 integer, 3 binary)
Non-zeros:  7
Status:     INTEGER OPTIMAL
Objective:  cost = 3 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 cost                        3
     2 S1                          1             1
     3 S2                          1             1
     4 S3                          1             1

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x_1          *              1             0             1
     2 x_2          *              1             0             1
     3 x_3          *              0             0             1

Integer feasibility conditions:

INT.PE: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

INT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output

En outre, je ne suis pas clair sur la façon d'obtenir directement le vecteur x qui résout le problème, mais il est codé dans la sortie ci-dessus dans cette section: 

  No. Column name       Activity     
------ ------------    ------------- 
     1 x_1          *              1 
     2 x_2          *              1 
     3 x_3          *              0

Vous avez spécifié un pur problème de programmation entier. La plupart des applications pratiques impliquent généralement ce qu'on appelle la programmation mixte en nombres entiers où seulement certaines des variables sont des nombres entiers. Vous trouverez sur le sujet Un tutoriel assez concis et essai ici:

http://mat.gsia.cmu.edu/orclass/integer /integer.html

techniques de solution pour les problèmes typiques IP sont la programmation dynamique ou branche et liée. La recherche sur ces termes devrait vous aider à trouver un certain freeware, shareware, ou un code académique.

Bonne chance

Python:

Ces types de problèmes simples peuvent également être résolus en utilisant une technique appelée la programmation par contraintes. Vous pouvez trouver plus de détails sur la technique et solveurs libres et disponibles dans le commerce pour résoudre ces problèmes de entrée de wikipedia correspondant . Si les problèmes faisant intervenir des variables entières sont plus complexes que ce que vous dites, il est préférable d'envisager objectif général linéaire Programmation / Programmation entière solveurs (comme GLPK). Il y a un tas d'entre eux, certains noms sont:. Lpsolve (gratuit), IBM ILOG CPLEX (Commercial)

J'utilise Python & Pyomo. Il y a un bon aperçu des avantages sur le site du projet: http://www.pyomo.org

Il est une question similaire sur scicomp.stackexchange .com et une réponse qui énumère quelques bibliothèques.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top