langsamer Modellaufbau

mit matplotlib, NumPy, pandas, SciPy, SymPy und weiteren mathematischen Programmbibliotheken.
Antworten
schuesra
User
Beiträge: 26
Registriert: Donnerstag 4. Oktober 2018, 17:40

Hallo,

mein Gurobi Modell wird einige Male erneut aufgerufen und dabei habe
ich festgestellt, dass der Modellaufbau bei einer Nebenbedingung sehr lange dauert.
Um folgende Nebenbedingung handelt es sich:

Code: Alles auswählen

    c = m.addConstrs(quicksum(a[i,j]*(S_tj_RLP[l, t, j]*accept[t,j] - denie[l,t,j])
            for t in perioden for j in produkte) <= flugkapazität[i] for i in flüge for l in n_showup_samples)
            

Dabei ist das "l" das Problem. Je höher ich das "l" einstelle, desto länger dauert der Modellaufbau. An sich klar, aber
gibt es Möglichkeiten wie ich die Nebenbedingung anders schreiben kann, damit die Nebenbedingung schneller aufgebaut wird?

Viele Grüße
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

@schuesra: das l (ein sehr schlechter Variablenname) stellst Du gar nicht höher oder tiefer ein, sondern ist eine Laufvariable, n_showup_samples dagegen wird wohl von der Größe von denie oder S_tj_RLP abhängen. Da hier wahrscheinlich niemand genau weiß, was Du eigentlich erreichen willst, kann man da schlecht helfen. Allgemein: Du hast eine vierfach verschachtelte Schleife, dass die langsam ist, braucht nicht zu wundern, ob man die schneller bekommt, hängt vom Problem ab. Die Summe sieht wie ein Matrixprodukt aus, da müßte man schauen, ob Dein Framework mit Matrizen rechnen kann. Der eigentliche Vergleich ist sind dann zwei Vektoren, die Elementweise verglichen werden, da müßte man schauen, ob Dein Framework das schon kompakter kann.
Das hilft aber nur, eine umständliche Formulierung kompakter zu schreiben und zu hoffen, das das dann schneller bearbeitet wird. Generell die Frage, was für eine Optimierung Du durchführen willst und wie man diese prinzipiell effizient löst, dazu müßtest Du Dich mit dem Problem, einer möglichen Umformulierung oder möglicherweise anderer Lösungsverfahren auseinandersetzen.
schuesra
User
Beiträge: 26
Registriert: Donnerstag 4. Oktober 2018, 17:40

Ich versuche mein Problem nochmal besser zu beschreiben. Im Grunde wird das Gurobi Modell immer wieder aufgerufen, wobei sich immer nur eine Nebenbedingung je nach gegenwärtiger Periode verändert. Die Nebenbedingungen (8) hängen von der "x" Matrix ab, weswegen eben das Modell immer neu berechnet wird. Die Frage ist eben ob ich das geschickter machen kann als alles immer neu zu berechnen, da sich ja nur (8) ändert und der Rest des Modells gleich bleiben. Ich hänge mal den ganzen Code an, dann ist es vielleicht leichter zu verstehen.
Zunächst werden Parameter festgelegt und ganz am Ende eine Funktion aufgerufen. Hier noch nichts spannendes...

Code: Alles auswählen

#Flüge
flüge = np.arange(2)
#perioden, in welchen DLP berechnet wird um neue bid-preise zu errechnen
reoptperiods = np.array([0])
#Produkte
produkte = np.arange(3)
#Perioden
perioden = np.arange(3)
#Kapazität der einzelnen Flüge
flugkapazität = np.array([1, 1])
#Erlöse der einzelnen Produkte
f = np.array([100, 110, 170])
#teta
teta = np.array([400, 440, 680])
#Anzahl an Show up samples
n_showup_samples = np.arange(25)        
#Anzahl an demand samples    
n_demand_samples = np.arange(100)
#Wahrscheinlichkeit für ein bestimmtes Produkt in einer bestimten Periode
p = np.array( [[0.38, 0.26, 0.36]] * 3)

p_sum = np.zeros(perioden.size)
p = uniform.rvs(size = (perioden.size, produkte.size), random_state = 3) 
for t in perioden:
    p_sum[t] = sum(p[t, :])
    for j in produkte:
        p[t, j] = p[t, j]/p_sum[t] 
        
#Wahrscheinlichkeitsmatrix, dass eine Person mit Reservierung für Produkt j zum Zeitpunkt t tatsächlich fliegt
q = np.array([[.7, .9, .9]] * 3)

#1 wenn Produkt j Ressource i nutzt, ansonsten 0
a = np.array([ [1.0, 0.0, 1.0], 
               [0.0, 1.0, 1.0] ])
             
#erwartete Nachfrage für Flug 1
alpha = np.sum(a[0,j]*q[0,j]*p[t,j] for t in perioden for j in produkte)
#erwartete Nachfrage über beide Flüge
alpha = np.sum(a[i,j]*q[0,j]*p[t,j] for t in perioden for j in produkte for i in flüge)
          
modell = ("small")
           
nRuns = 1

averageyieldallruns_DLP = erstelle_Simulation_DLP(nRuns, flüge, reoptperiods, produkte, perioden, flugkapazität, f, teta, p, q, a, modell)
Nun der Teil, in der das Gurobi Modell in der Schleife t-mal aufgerufen wird immer mit modifiziertem "x":

Code: Alles auswählen

def erstelle_Simulation_DLP(nRuns, flüge, reoptperiods, produkte, perioden, flugkapazität, f, teta, p, q, a, modell):

    
    rs = 3
    s = berechne_showups(q, perioden, produkte, nRuns, rs)
    yieldallruns = np.zeros(nRuns,dtype=np.int32)   
    Ba = np.zeros((len(perioden),nRuns), dtype=np.int32)

    for c in range(nRuns):
#wie bei perioden, nie mit range in schleifen arbeiten???
        I = np.zeros((len(perioden),len(produkte)))    #wird später mit kumulierten W'keiten befüllt
        x = np.zeros((len(perioden),len(produkte)),dtype=np.int32)
        gesamterlös = 0    #wie hoch ist der  gesamterlös pro run, zunächst 0 als Startwert
    
        for t in perioden:
            I[t,:] = p[t,:].cumsum()
            Ba[t, c] = find_ba1(I, t, produkte, nRuns, perioden, c, rs )
            j = Ba[t, c]
            if t in reoptperiods:
                myy = berechne_bidpreise(f, teta, flugkapazität, a, p, q, t, x, flüge, perioden, produkte, modell)
            opportunitycost_j = np.sum([a[i,j]*myy[i] for i in flüge]) * q[t,j]
            if f[j] >= opportunitycost_j:
                x[t,j] = 1
                gesamterlös += f[j]         
        
        dbkosten = berechne_dbkosten(teta, a, s[c], x, perioden, produkte, flugkapazität, flüge) #Aufruf des db-Optimierungsmodells 
        enderlös_eines_runs = gesamterlös-dbkosten #enderlös eines runs
        yieldallruns[c] = enderlös_eines_runs      #Matrix mit erlöse aller runs
    averageyieldallruns = np.mean(yieldallruns)   #gebe durchschnittlichen Erlös über alle runs aus 
    print("durchschnittlicher Erlös über alle runs: ",averageyieldallruns)
    
    return averageyieldallruns
Schlussendlich das immer wieder aufgerufene Gurobi Modell:

Code: Alles auswählen

def berechne_bidpreise(f, teta, flugkapazität, a, p, q, t, x, flüge, perioden, produkte, modell):
# Model
    print("Start Aufbau")
    m = Model("DLP")
    
#Erstelle Entscheidungsvariablen für die akzeptierten BA der jeweiligen Produkte
#legt constraint(10), also >=  0 automatisch fest
#decision varibales
    accept = m.addVars(perioden, produkte, name="accept")
    denie = m.addVars(perioden, produkte, name="denie")
    m.update()
#Objective
    obj = sum(f[j]*accept[t, j] - teta[j]*denie[t, j]
          for t,j in accept)

    m.setObjective(obj, GRB.MAXIMIZE)

#constraint (7)
    print("Hallo 1")
    c7= m.addConstrs(sum(a[i,j]*(q[t,j]*accept[t,j] - denie[t,j])
                     for t in perioden for j in produkte) <= flugkapazität[i] for i in flüge)
    print("Hallo 2")
#constraint (8)
    if t == 0:
        c8 = m.addConstrs(accept[t, j] <= p[t, j] for t,j in accept)

    if t!= 0:
        m.addConstrs(accept[t, j] == x[t, j] for t in perioden[0:t] for j in produkte)
        m.addConstrs(accept[t, j] <= p[t, j] for t in perioden[t:] for j in produkte)

#constraint (9)
    m.addConstrs(denie[t,j] <= q[t, j]*accept[t,j]
                for t,j in accept)
    print("Ende Aufbau")
#optimiert das Modell
    m.optimize()
    
    if modell == ("small"):
        return c7[0].Pi, c7[1].Pi

Könnt ihr jetzt besser nachvollziehen was ich meine? Der Teil von "Hallo1" bis "Hallo2" dauert enorm lange bei einem größerem Modell weswegen das anders gelöst werden muss...Am besten wäre es wenn das Gurobi Modell gespeichert werden würde und dann nur Nebenbedingungen (8) jeweils für jede Periode hinzugefügt werden.
Antworten