Quadratische Optimierung mit CPLEX

Neue Frage »

Herr-Vorragend Auf diesen Beitrag antworten »
Quadratische Optimierung mit CPLEX
Hi,

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ß
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?).
tigerbine Auf diesen Beitrag antworten »

Willkommen

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. Wink
Herr-Vorragend Auf diesen Beitrag antworten »

Danke für die nette Begrüßung smile

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.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
param NL >= 0;					# Anzahl an Veranstaltungen
param NP >= 0;					# Anzahl an Personen
param NR >= 0;					# Anzahl an Räumen
param NS >= 0;					# Anzahl an Zeit-Slots

set L := 1..NL;					# Menge von Veranstaltungen
set P := 1..NP;					# Menge von Personen
set R := 1..NR;					# Menge von Räumen
set S := 1..NS;					# Menge von Zeit-Slots

param C{R} >= 0;				# Raumkapazitäten
param W{P,L};					# "Affinität" einer Person zu einer Veranstaltung

var B{L,S,R} >= 0, <= 1;			# = 1 gdw. Vorlesung in Slot und Raum stattfinden soll
var A{P,L} >= 0, <= 1;				# = 1 gdw. Person Veranstaltung zugeteilt ist


maximize Zufriedenheit:
		sum {l in L, p in P} A[p,l]*W[p,l];

subject to Raumkapazitaeten {l in L, r in R, s in S}:
		B[l,s,r] * sum{p in P} A[p,l] <= C[r];

subject to MaxEinVeranstaltungProSlotUndRaum{r in R, s in S}:
		sum {l in L} B[l,s,r] <= 1;

subject to VeranstaltungGenauEinSlotUndRaum{l in L}:
		sum {s in S, r in R} B[l,s,r] = 1;

subject to PersonInMaxEinerVeranstaltungProSlot{p in P, s in S}:
		sum {l in L, r in R} B[l,s,r]*A[p,l] <= 1;


Danke und Gruß
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »