Quadratische Optimierung mit CPLEX |
26.11.2009, 15:56 | Herr-Vorragend | Auf diesen Beitrag antworten » | |||||
Quadratische Optimierung mit CPLEX im Rahmen meiner Bachelor-Arbeit musste ich ein Programm aufstellen, welches ein spezielles Problem löst. Dabei war mein erster Ansatz ein quadratisches Programm, nach weiterem Knobeln kam ich auch auf eine lineare Variante desselben Sachverhalts, was jedoch auch weitaus mehr Variablen und Nebenbedingungen mit sich zieht. Da Geschwindigkeit bei diesem Problem die größte Rolle spielt (mit Originaldaten wird das ganze wohl einige Tage rechnen müssen) habe ich mir an der Uni eine CPLEX-Lizenz ausgeliehen (Version 10.2.0), um die Laufzeit beider Programmvarianten mit verschiedenen Testdaten zu messen und zu vergleichen. Das klappt bei dem linearen Problem auch wunderbar, beim quadratischen jedoch meckert CPLEX "CPLEX 10.2.0: QP Hessian is not positive semi-definite.; no basis." und startet nicht mit der Berechnung. Ich habe auf dem englischen Wikipedia gelesen, dass nur effiziente Algorithmen für quadratische Probleme existieren, wenn sie positiv definit sind, hat das damit etwas zu tun? Falls ja, kann ich mein Programm irgendwie umschreiben, damit es lösbar ist, oder liegt es an der "Natur" des Problems und ich kann (oder sollte) die quadratische Variante direkt vergessen? Danke und Gruß |
|||||||
26.11.2009, 15:59 | Herr-Vorragend | Auf diesen Beitrag antworten » | |||||
Was ich vergessen habe: Die Zielfunktion des quadratischen Problems ist linear, ich habe lediglich ein paar quadratische Nebenbedingungen (d.h. Summen von Produkten zweier Variablen, ich nehme einfach mal an, dass das quadratisch ist?). |
|||||||
26.11.2009, 16:02 | tigerbine | Auf diesen Beitrag antworten » | |||||
Ich werde dir nicht helfen können. Damit es jemand anderes kann, zeige doch am besten mal das Problem, das gelöst werden soll. Benutze dazu latex. Danke und viel Erfolg. |
|||||||
26.11.2009, 16:10 | Herr-Vorragend | Auf diesen Beitrag antworten » | |||||
Danke für die nette Begrüßung Ich poste das ganze mal hier als AMPL-Code, das sollte denke ich gut lesbar sein, falls nicht bitte melden, dann texe ich das. Es geht darum, NL Veranstaltungen auf NR Räume und NS Zeitslots zu verteilen und NP Personen so auf die Veranstaltungen zu verteilen, dass es keine Kolissionen gibt, die Raumkapazitäten nicht überschritten werden und jeder in den Veranstaltungen sitzt, an denen er am liebsten teilnehmen würde (das ist in W gespeichert). Eigentlich müsste ich hier mit binären Variablen arbeiten, aber da das NP-hart ist kann ich es das aufgrund der Datenmenge vergessen und muss irgendwie auf rationale Variablen und randomisiertes Runden ausweichen.
Danke und Gruß |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|