Python cvxopt glpk ilp Rückkehr erste mögliche Lösung

Question

Ich benutze cvxopt.glpk.ilp, um ein sehr kompliziertes Mixed Integer-Programm zu lösen. Ich habe mich gefragt, ob es eine Möglichkeit gibt, das Programm zu beenden, nachdem die erste Lösung gefunden wurde. Es dauert zu lange und eine praktikable Lösung würde für meine Zwecke gut funktionieren.

Answer 1

Wenn Sie PuLP (eine andere Python-Bibliothek wie cvxopt) verwenden, um glpk aufzurufen, um MIP zu lösen, gibt es einen Parameter namens . Wenn Sie maxtime=1 einstellen, dann wird der Löser die Suche fast sofort beenden, nachdem er die erste Lösung gefunden hat. Ich wette, cvxopt sollte einen ähnlichen Parameter für glpk haben, da entweder PuLP oder cvxopt nur ein Wrapper dieser Löser ist.

Kopieren Sie die Beschreibung von maxtime Parameter in Xpress, die ein anderer Löser ist, aber ich denke, Glpk sollte etwas ähnliches haben, die Sie möglicherweise herausfinden müssen.

Answer 2

Wenn ich Sie richtig verstehe, sind Sie nur an einer realisierbaren Lösung interessiert?

Dann sollte es ausreichen, die Zielfunktion auf Null zu setzen. Hier

ist ein Wikipedia example für eine ganze Zahl lineares Programm und die folgende Python Code gibt eine realisierbare Lösung:

import cvxopt 
import cvxopt.glpk 

# original program maximizing the second variable 
# c=cvxopt.matrix([0,-1],tc='d') 

# modified program returning only a feasible solution 
c=cvxopt.matrix([0,0],tc='d') 

G=cvxopt.matrix([[-1,1],[3,2],[2,3],[-1,0],[0,-1]],tc='d') 
h=cvxopt.matrix([1,12,12,0,0],tc='d') 
(status, x)=cvxopt.glpk.ilp(c,G.T,h,I=set([0,1])) 
print('status',status) 
print('variables',x[0],x[1]) 
print('objective',sum(c.T*x))