Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Binäre Variablenbelegung eines großen Gleichungssystems
Druckversion
Druckversion
Antworten
Antworten
Autor
Beruf Binäre Variablenbelegung eines großen Gleichungssystems
Brausebonbon
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2021
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-02-22 10:56


Hallo Zusammen,

im Moment brüte ich über eine Aufgabe und komme nicht so richtig voran. Ich bin auf der Suche nach einem (schnellen) Verfahren, dass mir folgendes Problem löst:

Im Kern geht es um ein gewöhnliches Gleichungssystem. Jedoch mit sehr vielen Werten (20.000 Zeilen und ca. 25. Mio. Spalten)

Die eigentliche Herausforderung besteht darin, dass die Variablen nur ganze Zahlen annehmen dürfen (idealerweise 0 oder 1).

Die vollständige Lösung braucht nicht gefunden zu werden. Es genügt eine möglichst Gute. Das gilt im übrigen auch, wenn keine Lösung existiert - nah dran ist gut genug.

Beipiel:
fed-Code einblenden
ist bspw. mit
fed-Code einblenden
oder
fed-Code einblenden
exakt gelöst.

M.E. handelt es sich um ein klassisches Optimierungsproblem. (Falls ich mich irre und es doch eine normal berechenbare Lösung gibt - immer her damit :-) ) Die Frage ist jetzt, mit welchem Verfahren bekomme ich das möglichst schnell berechnet? Gibt es evtl. schon Implementierungen z.B. in R oder Python auf die ich zurück greifen kann?

Ich bin für jede Anregung dankbar!

Es grüßt,
Brausebonbon



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1342
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-02-22 18:33


Hallo Brausebonbon,

gut, dass Du ein Beispiel mitgeliefert hast, denn da gibt es ja unendlich viele Lösungen:

y -> w - 2 x, 
z -> 1 - w + x
also
{
 {"w","x","y","z"},
...
 {-1, -1,  1,  1},
 {0 , -1,  2,  0},
 {1 , -1,  3, -1},
 {-1,  0, -1,  2},
 {0 ,  0,  0,  1},
 {1 ,  0,  1,  0},
 {-1,  1, -3,  3},
 {0 ,  1, -2,  2},
 {1 ,  1, -1,  1}
...
}

Jedoch ist das "Gesuchte" etwas schwammig formuliert:
- Variablen "nur ganzzahlig...idealerweise 0 oder 1"
- es reicht eine "eine möglichst Gute"

Wie definierst Du "Gut"?
- exakt, jedoch dürfen die Lösungs-Werte auch von 0 und 1 abweichen
- oder mehr ein "Minimierungsproblem" (also möglichst dicht an den gewünschten Zahlen auf der rechten Seite)
- oder möglichst dicht an einer "ganzen Zahl"

-> es fehlt also die Priorisierung der Randbedingungen

Du hast hier 4 Spalten -> also 4 Ergebnisvariablen im Beispiel und willst bis zu 25 Mio. Spalten erweitern???

Das kann ja dann nur über Datei- In- & Output funktionieren. Wer soll diese enorme Menge an Daten auswerten? Oder geht es hier um Simulationen wie beim Wetter, wo man dann Farbbilder als Ergebnis hat?

Zunächst würde man bestimmt die "Unabhängigkeiten" herauskürzen, um die enorme Datenmenge handeln zu können.

So kürzt sich in bei

die Variable z in Gleichung 3:


Das wird bei 25 Mio. Variablen & 20000 Gleichungen aber eine enorme Optimierungsaufgabe...
... bei der 20000 Variablen über bleiben (Rest sollte sich kürzen).

Schau Dir mal www.arndt-bruenner.de/mathe/scripts/gleichungssysteme.htm
an. Da gibt es Beispiele & verschiedene Algorithmen.

Beachte auch den RAM-Verbrauch:
(20000*25*10^6+2*25*10^6)*8 etwa 4000 GB -> Großrechner
nur für den Input der Daten! Da wird noch nichts gerechnet!!

Grüße Gerd



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1342
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-02-22 19:02


Beispiel mit 10 Variablen:

  -5o + 9r + 2v      = -3
  -3r - 2v           = -10
   9r + 4v           = -4
  -4b - 6c           = -4
   10a + 4b + 3c     = -6
  -5a + c            = 10
  -15m + 9n - 2p     = 4
   5m - 4n - q       = 8
  -5m + 3n           = -10
   5m - 2n + 2p + 2q = -10
 
 Stelle die Koeffizientenmatrix auf. Reihenfolge der Variablen: a, b, c, m, n, o, p, q, r, v, Konstante
      0     0     0      0     0   - 5     0     0     9     2    - 3 
      0     0     0      0     0     0     0     0   - 3   - 2   - 10 
      0     0     0      0     0     0     0     0     9     4    - 4 
      0   - 4   - 6      0     0     0     0     0     0     0    - 4 
     10     4     3      0     0     0     0     0     0     0    - 6 
    - 5     0     1      0     0     0     0     0     0     0     10 
      0     0     0   - 15     9     0   - 2     0     0     0      4 
      0     0     0      5   - 4     0     0   - 1     0     0      8 
      0     0     0    - 5     3     0     0     0     0     0   - 10 
      0     0     0      5   - 2     0     2     2     0     0   - 10 
 Da das Diagonalenfeld in der 1. Zeile 0 ist, tausche die 1. und die 5. Zeile:
     10     4     3      0     0     0     0     0     0     0    - 6 
      0     0     0      0     0     0     0     0   - 3   - 2   - 10 
      0     0     0      0     0     0     0     0     9     4    - 4 
      0   - 4   - 6      0     0     0     0     0     0     0    - 4 
      0     0     0      0     0   - 5     0     0     9     2    - 3 
    - 5     0     1      0     0     0     0     0     0     0     10 
      0     0     0   - 15     9     0   - 2     0     0     0      4 
      0     0     0      5   - 4     0     0   - 1     0     0      8 
      0     0     0    - 5     3     0     0     0     0     0   - 10 
      0     0     0      5   - 2     0     2     2     0     0   - 10 
 Durch Division der 1. Zeile durch 10 wird das Diagonalelement zu 1 gemacht:
           2      3                                                 3 
     1     —     ——      0     0     0     0     0     0     0    - — 
           5     10                                                 5 
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0     0     0     0     9     4    - 4 
     0   - 4    - 6      0     0     0     0     0     0     0    - 4 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
   - 5     0      1      0     0     0     0     0     0     0     10 
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Mit der 1. Zeile werden alle anderen Zeilen in der 1. Spalte auf 0 gebracht.
 Zur 6. Zeile wird das 5fache der 1. Zeile addiert:
           2      3                                                 3 
     1     —     ——      0     0     0     0     0     0     0    - — 
           5     10                                                 5 
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0     0     0     0     9     4    - 4 
     0   - 4    - 6      0     0     0     0     0     0     0    - 4 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
                  5                                                   
     0     2      —      0     0     0     0     0     0     0      7 
                  2                                                   
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Da das Diagonalenfeld in der 2. Zeile 0 ist, tausche die 2. und die 4. Zeile:
           2      3                                                 3 
     1     —     ——      0     0     0     0     0     0     0    - — 
           5     10                                                 5 
     0   - 4    - 6      0     0     0     0     0     0     0    - 4 
     0     0      0      0     0     0     0     0     9     4    - 4 
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
                  5                                                   
     0     2      —      0     0     0     0     0     0     0      7 
                  2                                                   
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Durch Division der 2. Zeile durch -4 wird das Diagonalelement zu 1 gemacht:
           2      3                                                 3 
     1     —     ——      0     0     0     0     0     0     0    - — 
           5     10                                                 5 
                  3                                                   
     0     1      —      0     0     0     0     0     0     0      1 
                  2                                                   
     0     0      0      0     0     0     0     0     9     4    - 4 
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
                  5                                                   
     0     2      —      0     0     0     0     0     0     0      7 
                  2                                                   
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Mit der 2. Zeile werden alle anderen Zeilen in der 2. Spalte auf 0 gebracht.
 Zur 1. Zeile wird das -2/5fache der 2. Zeile addiert:
                  3                                                   
     1     0   - ——      0     0     0     0     0     0     0    - 1 
                 10                                                   
                  3                                                   
     0     1      —      0     0     0     0     0     0     0      1 
                  2                                                   
     0     0      0      0     0     0     0     0     9     4    - 4 
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
                  5                                                   
     0     2      —      0     0     0     0     0     0     0      7 
                  2                                                   
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Zur 6. Zeile wird das -2fache der 2. Zeile addiert:
                  3                                                   
     1     0   - ——      0     0     0     0     0     0     0    - 1 
                 10                                                   
                  3                                                   
     0     1      —      0     0     0     0     0     0     0      1 
                  2                                                   
     0     0      0      0     0     0     0     0     9     4    - 4 
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
                  1                                                   
     0     0    - —      0     0     0     0     0     0     0      5 
                  2                                                   
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Da das Diagonalenfeld in der 3. Zeile 0 ist, tausche die 3. und die 6. Zeile:
                  3                                                   
     1     0   - ——      0     0     0     0     0     0     0    - 1 
                 10                                                   
                  3                                                   
     0     1      —      0     0     0     0     0     0     0      1 
                  2                                                   
                  1                                                   
     0     0    - —      0     0     0     0     0     0     0      5 
                  2                                                   
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
     0     0      0      0     0     0     0     0     9     4    - 4 
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Durch Multiplikation der 3. Zeile mit -2 wird das Diagonalelement zu 1 gemacht:
                  3                                                   
     1     0   - ——      0     0     0     0     0     0     0    - 1 
                 10                                                   
                  3                                                   
     0     1      —      0     0     0     0     0     0     0      1 
                  2                                                   
     0     0      1      0     0     0     0     0     0     0   - 10 
     0     0      0      0     0     0     0     0   - 3   - 2   - 10 
     0     0      0      0     0   - 5     0     0     9     2    - 3 
     0     0      0      0     0     0     0     0     9     4    - 4 
     0     0      0   - 15     9     0   - 2     0     0     0      4 
     0     0      0      5   - 4     0     0   - 1     0     0      8 
     0     0      0    - 5     3     0     0     0     0     0   - 10 
     0     0      0      5   - 2     0     2     2     0     0   - 10 
 Mit der 3. Zeile werden alle anderen Zeilen in der 3. Spalte auf 0 gebracht.
 Zur 1. Zeile wird das 3/10fache der 3. Zeile addiert:
     1     0     0      0     0     0     0     0     0     0    - 4 
                 3                                                   
     0     1     —      0     0     0     0     0     0     0      1 
                 2                                                   
     0     0     1      0     0     0     0     0     0     0   - 10 
     0     0     0      0     0     0     0     0   - 3   - 2   - 10 
     0     0     0      0     0   - 5     0     0     9     2    - 3 
     0     0     0      0     0     0     0     0     9     4    - 4 
     0     0     0   - 15     9     0   - 2     0     0     0      4 
     0     0     0      5   - 4     0     0   - 1     0     0      8 
     0     0     0    - 5     3     0     0     0     0     0   - 10 
     0     0     0      5   - 2     0     2     2     0     0   - 10 
 Zur 2. Zeile wird das -3/2fache der 3. Zeile addiert:
     1     0     0      0     0     0     0     0     0     0    - 4 
     0     1     0      0     0     0     0     0     0     0     16 
     0     0     1      0     0     0     0     0     0     0   - 10 
     0     0     0      0     0     0     0     0   - 3   - 2   - 10 
     0     0     0      0     0   - 5     0     0     9     2    - 3 
     0     0     0      0     0     0     0     0     9     4    - 4 
     0     0     0   - 15     9     0   - 2     0     0     0      4 
     0     0     0      5   - 4     0     0   - 1     0     0      8 
     0     0     0    - 5     3     0     0     0     0     0   - 10 
     0     0     0      5   - 2     0     2     2     0     0   - 10 
 Da das Diagonalenfeld in der 4. Zeile 0 ist, tausche die 4. und die 7. Zeile:
     1     0     0      0     0     0     0     0     0     0    - 4 
     0     1     0      0     0     0     0     0     0     0     16 
     0     0     1      0     0     0     0     0     0     0   - 10 
     0     0     0   - 15     9     0   - 2     0     0     0      4 
     0     0     0      0     0   - 5     0     0     9     2    - 3 
     0     0     0      0     0     0     0     0     9     4    - 4 
     0     0     0      0     0     0     0     0   - 3   - 2   - 10 
     0     0     0      5   - 4     0     0   - 1     0     0      8 
     0     0     0    - 5     3     0     0     0     0     0   - 10 
     0     0     0      5   - 2     0     2     2     0     0   - 10 
 Durch Division der 4. Zeile durch -15 wird das Diagonalelement zu 1 gemacht:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                             3            2                        4 
     0     0     0     1   - —     0     ——     0     0     0   - —— 
                             5           15                       15 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
     0     0     0     5   - 4     0      0   - 1     0     0      8 
     0     0     0   - 5     3     0      0     0     0     0   - 10 
     0     0     0     5   - 2     0      2     2     0     0   - 10 
 Mit der 4. Zeile werden alle anderen Zeilen in der 4. Spalte auf 0 gebracht.
 Zur 8. Zeile wird das -5fache der 4. Zeile addiert:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                             3            2                        4 
     0     0     0     1   - —     0     ——     0     0     0   - —— 
                             5           15                       15 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
                                          2                       28 
     0     0     0     0   - 1     0    - —   - 1     0     0     —— 
                                          3                        3 
     0     0     0   - 5     3     0      0     0     0     0   - 10 
     0     0     0     5   - 2     0      2     2     0     0   - 10 
 Zur 9. Zeile wird das 5fache der 4. Zeile addiert:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                             3            2                        4 
     0     0     0     1   - —     0     ——     0     0     0   - —— 
                             5           15                       15 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
                                          2                       28 
     0     0     0     0   - 1     0    - —   - 1     0     0     —— 
                                          3                        3 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
     0     0     0     5   - 2     0      2     2     0     0   - 10 
 Zur 10. Zeile wird das -5fache der 4. Zeile addiert:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                             3            2                        4 
     0     0     0     1   - —     0     ——     0     0     0   - —— 
                             5           15                       15 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
                                          2                       28 
     0     0     0     0   - 1     0    - —   - 1     0     0     —— 
                                          3                        3 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
                                          4                       26 
     0     0     0     0     1     0      —     2     0     0   - —— 
                                          3                        3 
 Da das Diagonalenfeld in der 5. Zeile 0 ist, tausche die 5. und die 8. Zeile:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                             3            2                        4 
     0     0     0     1   - —     0     ——     0     0     0   - —— 
                             5           15                       15 
                                          2                       28 
     0     0     0     0   - 1     0    - —   - 1     0     0     —— 
                                          3                        3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
                                          4                       26 
     0     0     0     0     1     0      —     2     0     0   - —— 
                                          3                        3 
 Durch Multiplikation der 5. Zeile mit -1 wird das Diagonalelement zu 1 gemacht:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                             3            2                        4 
     0     0     0     1   - —     0     ——     0     0     0   - —— 
                             5           15                       15 
                                          2                       28 
     0     0     0     0     1     0      —     1     0     0   - —— 
                                          3                        3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
                                          4                       26 
     0     0     0     0     1     0      —     2     0     0   - —— 
                                          3                        3 
 Mit der 5. Zeile werden alle anderen Zeilen in der 5. Spalte auf 0 gebracht.
 Zur 4. Zeile wird das 3/5fache der 5. Zeile addiert:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                                          8     3                 88 
     0     0     0     1     0     0     ——     —     0     0   - —— 
                                         15     5                 15 
                                          2                       28 
     0     0     0     0     1     0      —     1     0     0   - —— 
                                          3                        3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
                                          4                       26 
     0     0     0     0     1     0      —     2     0     0   - —— 
                                          3                        3 
 Zur 10. Zeile wird das -1fache der 5. Zeile addiert:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                                          8     3                 88 
     0     0     0     1     0     0     ——     —     0     0   - —— 
                                         15     5                 15 
                                          2                       28 
     0     0     0     0     1     0      —     1     0     0   - —— 
                                          3                        3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
                                          2                        2 
     0     0     0     0     0     0      —     1     0     0      — 
                                          3                        3 
 Da das Diagonalenfeld in der 6. Zeile 0 ist, tausche die 6. und die 8. Zeile:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                                          8     3                 88 
     0     0     0     1     0     0     ——     —     0     0   - —— 
                                         15     5                 15 
                                          2                       28 
     0     0     0     0     1     0      —     1     0     0   - —— 
                                          3                        3 
     0     0     0     0     0   - 5      0     0     9     2    - 3 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
     0     0     0     0     0     0      0     0     9     4    - 4 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
                                          2                        2 
     0     0     0     0     0     0      —     1     0     0      — 
                                          3                        3 
 Durch Division der 6. Zeile durch -5 wird das Diagonalelement zu 1 gemacht:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                                          8     3                 88 
     0     0     0     1     0     0     ——     —     0     0   - —— 
                                         15     5                 15 
                                          2                       28 
     0     0     0     0     1     0      —     1     0     0   - —— 
                                          3                        3 
                                                      9     2      3 
     0     0     0     0     0     1      0     0   - —   - —      — 
                                                      5     5      5 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
     0     0     0     0     0     0      0     0     9     4    - 4 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
                                          2                        2 
     0     0     0     0     0     0      —     1     0     0      — 
                                          3                        3 
 Alle übrigen Zeilen haben in der 6. Spalte bereits eine 0.
 Da das Diagonalenfeld in der 7. Zeile 0 ist, tausche die 7. und die 9. Zeile:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                                          8     3                 88 
     0     0     0     1     0     0     ——     —     0     0   - —— 
                                         15     5                 15 
                                          2                       28 
     0     0     0     0     1     0      —     1     0     0   - —— 
                                          3                        3 
                                                      9     2      3 
     0     0     0     0     0     1      0     0   - —   - —      — 
                                                      5     5      5 
                                          2                       34 
     0     0     0     0     0     0      —     0     0     0   - —— 
                                          3                        3 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
                                          2                        2 
     0     0     0     0     0     0      —     1     0     0      — 
                                          3                        3 
 Durch Multiplikation der 7. Zeile mit 3/2 wird das Diagonalelement zu 1 gemacht:
     1     0     0     0     0     0      0     0     0     0    - 4 
     0     1     0     0     0     0      0     0     0     0     16 
     0     0     1     0     0     0      0     0     0     0   - 10 
                                          8     3                 88 
     0     0     0     1     0     0     ——     —     0     0   - —— 
                                         15     5                 15 
                                          2                       28 
     0     0     0     0     1     0      —     1     0     0   - —— 
                                          3                        3 
                                                      9     2      3 
     0     0     0     0     0     1      0     0   - —   - —      — 
                                                      5     5      5 
     0     0     0     0     0     0      1     0     0     0   - 17 
     0     0     0     0     0     0      0     0     9     4    - 4 
     0     0     0     0     0     0      0     0   - 3   - 2   - 10 
                                          2                        2 
     0     0     0     0     0     0      —     1     0     0      — 
                                          3                        3 
 
...
 
 Mit der 10. Zeile werden alle anderen Zeilen in der 10. Spalte auf 0 gebracht.
 Zur 6. Zeile wird das -4/5fache der 10. Zeile addiert:
     1     0     0     0     0     0     0     0     0     0    - 4 
     0     1     0     0     0     0     0     0     0     0     16 
     0     0     1     0     0     0     0     0     0     0   - 10 
     0     0     0     1     0     0     0     0     0     0    - 4 
     0     0     0     0     1     0     0     0     0     0   - 10 
     0     0     0     0     0     1     0     0     0     0    - 7 
     0     0     0     0     0     0     1     0     0     0   - 17 
     0     0     0     0     0     0     0     1     0     0     12 
                                                           2     10 
     0     0     0     0     0     0     0     0     1     —     —— 
                                                           3      3 
     0     0     0     0     0     0     0     0     0     1     17 
 Zur 9. Zeile wird das -2/3fache der 10. Zeile addiert:
     1     0     0     0     0     0     0     0     0     0    - 4 
     0     1     0     0     0     0     0     0     0     0     16 
     0     0     1     0     0     0     0     0     0     0   - 10 
     0     0     0     1     0     0     0     0     0     0    - 4 
     0     0     0     0     1     0     0     0     0     0   - 10 
     0     0     0     0     0     1     0     0     0     0    - 7 
     0     0     0     0     0     0     1     0     0     0   - 17 
     0     0     0     0     0     0     0     1     0     0     12 
     0     0     0     0     0     0     0     0     1     0    - 8 
     0     0     0     0     0     0     0     0     0     1     17
 
 In der letzten Spalte stehen die Lösungen!!

...schon 64 k Text...
& Du möchtest 25 Mio. Variablen...???
Selbst nach Kürzung bleiben 20000 Variablen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Brausebonbon
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2021
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2021-02-22 19:26


Hallo Gerd,

danke für die Rückmeldung.

Die Ergebnisvektoren sollen binär sein (zur Not gingen auch ganzzahlige positive Werte - negative Werte oder gebrochene Zahlen sind keine brauchbaren Lösungen und müssen daher verworfen werden). Es sind also schlicht nicht alle Variablenbelegungen erlaubt.

Mit möglichst Gut meinte ich ein "Minimierungsproblem" (also möglichst dicht an den gewünschten Zahlen auf der rechten Seite). Für die Gewichtung würde ich jetzt einfach eine Gleichverteilung verwenden. (Ich wollte es für den ersten Aufschlag nicht zu kompliziert machen)

 
> Du hast hier 4 Spalten -> also 4 Ergebnisvariablen im Beispiel und
  willst bis zu 25 Mio. Spalten erweitern???

Ja, wobei die Daten selbst und auch das Ergebnis dünn besetzt ist (ganz viele 0-en in der Matrix und dem Vektor). Die Daten lassen sich also recht effizient speichern. Das Ergebnis ist dann der Vektor aus 0en und 1en (Als spärlich besetzte Struktur bleibt eine Liste von Positionen der 1en übrig)

Das geht schon recht effizient und ist auch in vernünftiger Zeit auswertbar. Ich bin aktuell bei 120GB für die Matrix und benötige 2h zum Aufbau der Matrix und die näherungsweise Lösung als normales Gleichungssystem (also mit neg. Werten im Ergebnisvektor). Mit der Laufzeit und dem Speicherverbrauch bin ich zufrieden. (Wenn es am Ende eine Woche dauert ist es mir auch egal - muss ja nicht dabei zugucken ;-) )

Das Ergebnis passt nur leider nicht so richtig zu dem was ich brauche. Als Fingerübung also ganz nett aber ich muss vermutlich einfach nochmal auf Anfang und das Problem von vorn durchdenken.

In den Basisdaten sind weder die Spalten noch die Zeilen linear abhängig. (Kreuzprodukt gebildet und die Determinate berechnet - diese ist ungleich 0 - also keine Singularitäten) Rauskürzen kann ich da also vermutlich nichts oder ich hänge in der Linearen Algebra. (Sorry, bin kein Mathematiker und puzzle mich nur so durch)

> Das wird bei 25 Mio. Variablen & 20000 Gleichungen aber eine enorme Optimierungsaufgabe...

Ja, deswegen kaue ich vermutlich auch schon eine Weile auf der Aufgabe rum. :-) Vielleicht muss ich mich auch davon verabschieden eine gute Lösung zu finden aber ich mag im Moment noch nicht aufgeben. Als normale Lösung eines Gleichungssystems wird das vermutlich nicht vernünftig berechenbar sein (es sei den ein Numeriker zaubert noch ein tolles Verfahren aus dem Hut) Es bleibt das weite Feld der Optimierungsverfahren. Welches ist für die Fragestellung geeignet?

Man könnte das Problem auch Umformulieren: Ich habe eine Population und möchte daraus eine Unterpopulation auswählen, sodass bestimmte Merkmale als Randverteilung passen.

Im Beispiel: Ich habe 25 Mio. Fahrzeuge mit jeweils 20.000 Merkmalen (Rot, Blau, Anzahl Räder, PS usw.) Ich weiß von jedem Merkmal wie oft es in der Unterpopulation vorkommt (Ergebnisvektor) und möchte nun wissen, ob ich das Fahrzeug in die Unterpopulation aufnehme oder nicht. Jedes Fahrzeug darf nur maximal einmal in der Unterpopulation aufgenommen werden. Die Frage ist also welche Fahrzeuge werden ausgewählt?

Danke auch für den Link! Guck ich mir an.

Gruß Brausebonbon

[Die Antwort wurde nach Beitrag No.1 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-02-23 14:18


2021-02-22 10:56 - Brausebonbon im Themenstart schreibt:
Die eigentliche Herausforderung besteht darin, dass die Variablen nur ganze Zahlen annehmen dürfen (idealerweise 0 oder 1).

2021-02-22 19:26 - Brausebonbon in Beitrag No. 3 schreibt:
Die Ergebnisvektoren sollen binär sein (zur Not gingen auch ganzzahlige positive Werte - negative Werte oder gebrochene Zahlen sind keine brauchbaren Lösungen und müssen daher verworfen werden)

Damit hast du die Aufgabestellung vom Startbeitrag *wesentlich* verändert. Falls die Lösung nur ganzzahlig sein soll (Stichwort: diophantisches Gleichungssystem) oder nur nichtnegativ (Lineare Optimierung), dann lässt sich eine Lösung in polynombeschränkter Zeit finden. Aber wenn beides zusammenkommt, dann ist die Aufgabestellung nur NP-vollständig (Lösung einer beliebigen Aufgabe kann in polynombeschränkter Zeit nur *nachgewiesen* werden).

Das ist zwar bloß ein worst-case-Szenario, aber es gibt auch kleinere Aufgaben die extrem schwer zu lösen sind. Letztendlich wird es bei dir auf Herumprobieren herauslaufen, und auf Glück hoffen. Solche Aufgaben lassen sich meist auf verschiedene Art formulieren (es gibt verschiedene Gleichungssysteme die dasselbe aussagen), und die Effizienz hängt *sehr* von der Formulierung ab. Die beste Software für derlei Probleme ist leider immer proprietär und meist teuer; kostenloses gibt es meiner Info nach nur für kleine Aufgaben.

Es ist interessant und neuartig, dass dir auch nichtbinäre kleine Zahlen genügen. Ich würde mir überlegen, ob man eine teilweise gebrochene Lösung vielleicht so aufrunden kann, dass das Gleichungssystem weiterhin erfüllt ist und die Zahlen nicht allzusehr anwachsen.


-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen. (Kol.2:9)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Brausebonbon
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2021
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-02-23 17:38


Super vielen Dank!

Da sind viele Anregungen dabei, die ich mir ansehen werde. Ich versuche es erstmal mit der linearen Optimierung.

Hast du evtl. noch einen Lösungsansatz für die NP-vollständige Problemvariante?

Gruß,
Brausebonbon



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1580
Herkunft: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2021-02-23 18:30


2021-02-23 17:38 - Brausebonbon in Beitrag No. 5 schreibt:
Hast du evtl. noch einen Lösungsansatz für die NP-vollständige Problemvariante?

Der übliche Ansatz ist "Branch and Bound", mit zahlreichen Umformulierungen, Abwandlungen und sonstigen Tricks, die die Suche schneller machen sollen (und welche natürlich von den komerziellen Softwareherstellern geheimgehalten werden). Was Einzelheiten anbetrifft, bin ich da nicht auf dem Laufenden. In der Regel kommt man nicht zu einer optimalen Lösung, sondern bricht die Suche nach einer angemessenen Zeit ab; die Software liefert in der Regel die besten soweit gefundenen Zwischenlösungen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6701
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2021-02-23 20:35


Vielleicht kann man folgendes probieren:

Alternative 1
a) Wir betrachten das Problem als lineares Optimierungsproblem mit der Nebenbedingung, dass alle Variablen zwischen 0 und 1 liegen müssen.
b) Da 25 Millionen Variablen uns wahrscheinlich Probleme mit dem Speicherplatz bescheren, setzen wir erstmal einen Großteil davon willkürlich auf 0 oder 1 und arbeiten mit sagen wir mal 200.000 echten Variablen. [Die Zahl hängt davon ab, was wir mit unseren Solver für lineare Programme noch hinbekommen].
c) Jetzt werden wir wahrscheinlich Probleme habe, dass sich die Nebenbedingung Ax=b nicht exakt erfüllen lässt. Wir untersuchen stattdessen das Problem (A,1)*(x;d)$\geq$ b und (A,-1)*(x,d)$\leq$b und wählen als Zielfunktion min d. Der Wert d ist dann die maximale Abweichung, den die linke Seite von der rechten Seite haben darf.
d) Wir erhalten eine Lösung, bei der die meisten Variablen den Wert 0 oder 1 annehmen und nur einige einen Wert ungleich 1 oder 0.
Die Variablen, die in der Lösung ganzzahlig sind, werden fixiert, die anderen bleiben variabel. Zusätzlich heben wir bei einigen anderen Variablen die Fixierung auf, um wieder auf 200.000 freie Variablen zu kommen. Wir starten die lineare Optimierung neu. Da die vorherige optimale Lösung auch im neuen Problem zulässig ist, können wir uns in der Zielfunktion nicht verschlechtern. Die Hoffnung ist, dass wir die zulässige Abweichung d damit in einen erträglichen Bereich bekommen, wenn wir in mehreren Runden nach und nach alle Variablen mal als freie Variablen zulassen.

Damit haben wir das eigentliche Problem noch nicht gelöst, da wir am Ende eine Lösung erhalten, bei der zwar die meisten Variablen ganzzahlig sind, aber einige eben nicht. Die Hoffnung ist aber damit zumindest schon mal nicht ganz schlecht zu sein, wenn man die erhaltene Lösung auf ganze Werte rundet.(*)

(*) Man kann auch "iterativ Runden". D.h., man rundet einige Werte, fixiert diese Variablen und optimiert dann nochmal. Rundet wieder einige Werte usw.


Alternative 2
Eine Alternative wäre eine lokale Suche. Zulässig sind nur Belegungen aller Variablen mit 0 und 1. Zwei Lösungen heißen benachbart, wenn sie sich nur in einer Variablen unterscheiden.
Man wählt zufällig eine Startlösung. Nun schaut man, ob irgendeine Nachbarlösung einen besseren Zielfunktionswert aufweist.(*) Wenn ja, wechselt man zu dieser Lösung und setzt von da die Suche fort.
Gibt es keine bessere Lösung, dann hat man ein lokales Optimum erreicht. Hat man noch Rechenzeit übrig, startet man von einer anderen zufälligen Startlösung und schaut, ob man von da eine bessere Lösung erreicht.
(*) Es bietet sich an, zuerst die Änderung von Variablen zu auszuprobieren, die an der Zeile mit der größten Abweichung zur rechten Seite mit einem von 0 verschiedenen Koeffizienten beteiligt sind.

Vorteile: Algorithmisch ist das sehr einfach. Die notwendigen Rechnungen sind nicht übermäßig komplex.
Nachteil: Man erreicht nur lokal optimale Lösungen. Dabei kann man dann vom globalen Optimum weit entfernt sein.


Ich würde Alternative 2 zuerst probieren, vorallem, weil mir bei 1 die Erfahrung fehlt, wie groß ein lineares Optimierungsproblem sein darf, um noch in erträglicher Zeit gelöst zu werden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6701
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2021-02-23 21:06


Alternative 2 als Matlab-Code:
Matlab
format long g
 
% Zufällige Instanz erzeugen
N=2000; M=20000;
tic % Start der Zeitmessung
A=rand(N,M);b=rand(N,1)*M/20;
 
% Einmaliger Durchlauf der lokalen Suche
tic
x=round(rand(M,1));
% Es erweist sich als günstig, direkt das Residuum r zu betrachten
r=A*x-b;
best=norm(r);
 
weiter=1;
while weiter
    weiter=0;
    for p=1:M
% Hier wird direkt die Änderung des Residuums bestimmt, wenn man x an der
% p-ten Stelle ändert. Das erspart die aufwändige Berechnung von A*x.
        rn=r+(1-2*x(p))*A(:,p);
        if norm(rn)<best
            r=rn;
            best=norm(rn);
            x(p)=1-x(p);
            weiter=1;
        end
    end
% Damit man etwas "sieht", wird nach jeder Runde der beste Wert angezeigt
    best 
end
toc
% Am Ende enthält "x" die beste gefundene Lösung 
% und "best" ihren Funktionswert.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Brausebonbon
Neu Letzter Besuch: in der letzten Woche
Dabei seit: 22.02.2021
Mitteilungen: 4
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2021-02-24 07:26


Prima,

vielen Dank jetzt habe ich erstmal wieder ein wenig Material zum Lesen und Basteln.

@Kitaktus:
Variante 1 klingt interessant. Da muss ich nochmal in Ruhe drüber nachdenken. Variante 2 hatte ich bereits umgesetzt (4 Wochen Laufzeit bei lokaler Suche für halbwegs brauchbare Ergebnisse). Ich habe das Verfahren dann zu einer globalen Suche erweitert in dem ich die Schrittweite in Abhängigkeit zur Zielfunktion variiere. Es wird dann immer die nächste Population gewählt, die die größte Verbesserung bringt (Laufzeit ca. 2 Wochen für halbwegs brauchbare Ergebnisse). Ich hatte vorher aber die Zeilen der Matrix deutlich reduziert. Statt 20.000 eher 2000 um mich erstmal rann zu tasten. Da ich mit der Laufzeit und dem Ergebnis nicht zufrieden war, habe ich mit einem anderen Ansatz weiter gemacht. In der Diskussion ist mir jetzt bewusst geworden, dass das Ergebnis vielleicht doch nicht so schlecht war. Vielleicht ist mein Anspruch eher das Problem.

Vielen Dank für die vielen Vorschläge und Lösungsansätze! Das hilft mir schon sehr weiter! Vielleicht probiere ich es auch nochmal mit einer Kombination der Lösungsansätze. Die Matrix lässt sich schlicht so schön effektiv speichern und berechnen. Simplex-Berechnung als Vorstufe mit anschließender stochastischer Optimierung o.s.ä.

Gruß,
Brausebonbon



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6701
Herkunft: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2021-02-24 09:56


2021-02-24 07:26 - Brausebonbon in Beitrag No. 9 schreibt:
Es wird dann immer die nächste Population gewählt, die die größte Verbesserung bringt ..
Wenn man alle Nachbarn betrachtet und dann zum besten wechselt, nennt man das "volle lokale Suche". Das würde ich hier nicht machen und stattdessen "schnelle lokale Suche" probieren. Dabei wechselt man immer sofort, wenn man einen besseren Nachbarn gefunden hat.
Außerdem bietet sich eine "zyklische Suche" an. Das heißt, wenn man durch Änderung der j-ten Variable eine Verbesserung gefunden hat, fängt man nicht wieder bei der ersten Variable an, nach weiteren Verbesserungen zu suchen, sondern macht bei der j+1-ten Variable weiter.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Brausebonbon wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]