Ich habe ein ganzzahliges lineares Optimierungsproblem und interessiere mich für machbare, gute Lösungen. So weit ich weiß, zum Beispiel das Gnu Linear Programming Kit gibt nur die optimale Lösung (sofern es existiert). Das braucht endlose Zeit und ist nicht genau das, wonach ich suche: Ich wäre mit jeder guten Lösung glücklich, nicht nur mit der optimalen.
Also ein LP-Solver, der z.B. hört nach einiger Zeit auf und gibt die beste Lösung, die er bis jetzt gefunden hat, würde den Job erledigen.
Gibt es eine solche Software? Es wäre großartig, wenn diese Software Open Source wäre oder zumindest frei wie in Bier.
Alternativ: Gibt es sonst noch eine Möglichkeit, die Integer-LP-Probleme zu beschleunigen? Ist das der richtige Ort, um zu fragen?
Wenn Sie schnell eine machbare Integer-Lösung erhalten möchten und Sie nicht die optimale Lösung benötigen, können Sie
ausprobierenErhöhen Sie den relativen oder absoluten Abstand . Normalerweise haben Solver kleine Lücken von zB 0,0001% für den relativen Abstand. Dies bedeutet, dass der Solver weiterhin nach MIP-Lösungen sucht, bis die MIP-Lösung nicht mehr als 0,0001% von der optimalen Lösung entfernt ist. Erhöhen Sie diesen Wert auf z. 1%., So erhalten Sie eine gute Lösung, aber der Solver wird nicht lange auf die Optimierung der Funktionalität.
Probieren Sie verschiedene Werte für Solver-Parameter für MIP-Heuristiken aus.
CPLEX und GUROBI haben Parameter zu steuern, MIP-Schwerpunkt . Dies bedeutet, dass der Solver mehr Wert auf die Suche nach realisierbaren Lösungen oder auf den Nachweis der Optimalität legt. Setzen Sie den Schwerpunkt auf praktikable MIP-Lösungen.
Die meisten Löser wie CPLEX, Gurobi, MOPS oder GLPK haben Einstellungen für Lücken und Heuristiken. MIP-Schwerpunkte können - soweit ich weiß - nur in CPLEX und Gurobi gesetzt werden.
Viele Solver bieten einen Zeitlimit-Parameter; Wenn Sie den Parameter für die Zeitbegrenzung festlegen, werden sie nach Erreichen des Zeitlimits gestoppt. Wenn eine ganzzahlige machbare Lösung gefunden wurde, wird die bestmögliche Lösung, die zu diesem Zeitpunkt gefunden wurde, zurückgegeben.
Wie Sie vielleicht wissen, ist die ganzzahlige Programmierung NP-schwer, und es ist eine echte Kunst, schnell optimale Lösungen und gut durchführbare Lösungen zu finden. Zum Vergleich der verschiedenen Löser siehe Prof. Hans Mittelmanns Benchmarks für Optimierungssoftware . Die MILP-Benchmarks - insbesondere MIPLIB2010 und der Feasibility Benchmark - sollten am relevantesten sein.
Zusätzlich zur Auswahl eines guten Solvers gibt es viele Dinge, die Sie tun können, um die Lösungszeiten zu verbessern, einschließlich der Optimierung der Solver-Parameter und der Modellreformulierung. Viele Menschen in Forschung und Industrie - einschließlich mir selbst - verbringen unsere Karrieren damit, die Lösungszeiten von MIP-Modellen zu verbessern, sowohl im Allgemeinen als auch für spezifische Modelle.
Wenn Sie ein akademischer Benutzer sind, beachten Sie, dass die führenden kommerziellen Systeme wie CPLEX und Gurobi für akademische Zwecke frei sind. Details finden Sie auf den jeweiligen Websites.
Zum Schluss möchten Sie vielleicht OR-Exchange sehen, eine Schwester-Site von Stack Overflow, die sich auf das Gebiet von Operations Research.
(Disclaimer: Ich arbeite derzeit für Gurobi Optimization und arbeitete früher für ILOG, die CPLEX zur Verfügung gestellt hat).
Ein üblicher Ansatz zur Lösung von ILP ist Branch-and-Bound. Dies nutzte die Lösung vieler Sub-LP (ohne-I). Das letztendlich optimale Ergebnis ist das beste aller Sub-LPs. Da mindestens eine Lösung gefunden wurde, könnte man jederzeit anhalten und hätte eine Best-so-weit-Lösung.
Ein Paket, das es könnte, ist die kostenlose lpsolve. Suchen Sie dort nach set_timeout, um ein Zeitlimit zu geben, und wenn es ILP ist, kann die Solve-Funktion in SUPOPTIMAL den Wert von best_so_far zurückgeben.
Soweit ich weiß, kann CPLEX. Es kann den Lösungspool zurückgeben, der die ursprünglich möglichen Lösungen in der Suche enthält, und wenn Sie den Suchfokus auf Durchführbarkeit statt auf Optimalität festlegen, können einfachere Lösungen generiert werden. Am Ende können Sie den Pool einfach exportieren. Sie können den Pool nutzen, um einen heißen Start zu machen, also liegt es ganz bei Ihnen. CPlex ist jetzt zumindest in meinem Land kostenlos, da Sie sich als Forscher anmelden können.
Könnten Sie Microsoft Solver Foundation berücksichtigen? Die einzige Einschränkung ist der Technologie-Stack, den Sie bevorzugen, und hier sollten Sie, wie Sie vermuten, Microsoft-Technologien verwenden: C #, vb.net usw. Hier ist ein Beispiel, wie man es mit Excel verwendet: Ссылка .
In Bezug auf Ihre Frage ist es möglich, keine vollständig optimierten Lösungen zu haben, wenn Sie die Effizienz festlegen (zum Beispiel 85% oder 0,85). Im Ergebnis können Sie alle möglichen Lösungen für eine solche Einschränkung sehen.
Tags und Links linear-programming