résolveur de programmation linéaire binaire en Python

j'ai un script Python dans lequel j'ai besoin pour résoudre un problème de programmation linéaire. Le hic, c'est que la solution doit être binaire. En d'autres termes, J'ai besoin d'un équivalent de la fonction bintprog de MATLAB. NumPy et SciPy ne semblent pas avoir une telle procédure. Est-ce que quelqu'un a des suggestions sur la façon dont je pourrais faire une de ces trois choses:

  • trouvez une bibliothèque Python qui inclut une telle fonction.

  • limite le problème de manière à ce qu'il puisse être résolu par un solveur de programmation linéaire plus général.

  • Interface Python avec MATLAB afin d'utiliser directement bintprog .

13
demandé sur tlayton 2010-07-24 21:22:02

2 réponses

Juste pour être rigoureux, si le problème est un binaire problème de programmation, alors il n'est pas un programme linéaire.

vous pouvez essayer CVXOPT . Il a une fonction de programmation entière (voir ce ). Pour faire de votre problème un programme binaire, vous devez ajouter la contrainte 0 <= x <= 1.

Edit : vous pouvez effectivement déclarer votre variable comme binaire, donc vous n'avez pas besoin d'ajouter la contrainte 0 <= x < = 1. 

cvxopt.glpk.ilp = ilp(...)
Solves a mixed integer linear program using GLPK.

(status, x) = ilp(c, G, h, A, b, I, B)

PURPOSE
Solves the mixed integer linear programming problem

    minimize    c'*x
    subject to  G*x <= h
                A*x = b
                x[I] are all integer
                x[B] are all binary
6
répondu Alejandro 2015-06-15 11:23:42

c'est une demi-réponse, mais vous pouvez utiliser Python pour l'interface avec GLPK (via python-glpk). GLPK supporte les programmes linéaires entiers. (les programmes binaires sont juste un sous-ensemble de programmes entiers).

http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit

ou vous pouvez simplement écrire votre problème en Python et générer un fichier MPS (que la plupart des solveurs standards LP/MILP (CPLEX, Gurobi, GLPK) accepteront). Cela peut être un bon chemin à prendre, parce que pour autant que je sache, il n'y a pas de solveurs MILP de haute qualité qui sont natifs de Python (et il n'y en aura peut-être jamais). Cela vous permettra également d'essayer différents solveurs.

http://code.google.com/p/pulp-or /

quant à l'interfaçage de Python avec MATLAB, je voudrais juste lancer ma propre solution. Vous pourriez générer un .m le fichier et puis l'exécuter à partir de la ligne de commande 

% matlab -nojava myopt.m

Notes :

  1. si vous êtes un utilisateur universitaire, vous pouvez obtenir une licence gratuite pour Gurobi, un solveur haute performance LP/MILP. Il a une interface Python. http://www.gurobi.com/
  2. OpenOpt est une suite d'optimisation Python qui s'interface avec différents solveurs. http://en.wikipedia.org/wiki/OpenOpt
4
répondu Gilead 2010-07-24 17:53:10