Forum:  Numerik & Optimierung
Thema: Linearisierung einer Nebenbedingung
Themen-Übersicht
Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 73
Aus:
Themenstart: 2020-05-29 16:38

Hallo ich habe hier eine Nebenbedingung, die ich gerne linearisieren möchte.

\( \sum_{i=1}^{n-1} \sum_{j=1}^{n} \sum_{c\in C} c*(w_{ci}*x_{ij}^{pq}+w_{cj}*x_{ij}^{pq}) \geq 2*(1+2+...+( \sum_{i=1}^{n-1} \sum_{j=1}^{n} x_{ij}^{pq} -1)) \)

Dabei sind w und x binär und die Entscheidungsvariablen.

Ich kenne die Standardlinearisierung bei Binärvariablen in der einfachsten Form. Hier bin ich aber mit den Indizes etwas verwirrt.

Mein Vorschlag:
Setze \( z_{1} = w_{ci}*x_{ij}^{pq} \) und \( z_{2} = w_{cj}*x_{ij}^{pq} \)
Mit
\( z_{1} \leq w_{ci} \\
z_{1} \leq x_{ij}^{pq} \\
w_{ci}+x_{ij}^{pq} \leq 1 + z_{1} \\
und z_{1} \geq 0 \)
Analog für \( z_{2}\)

Ich habe aber leider das Gefühl dass das so nicht reicht.
Kann mir da jemand weiterhelfen? Es wäre mir wirklich wichtig. Danke


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 73
Aus:
Beitrag No.1, vom Themenstarter, eingetragen 2020-05-29 16:58

Da das mit LATEX nicht so funktioniert wie geplant, hier die Bedingung als Bilddatei:



Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1484
Aus: Chile, Ulm
Beitrag No.2, eingetragen 2020-06-01 22:50

2020-05-29 16:38 - Kingtom2 im Themenstart schreibt:
Mein Vorschlag:

Setze \( w_{ci}\cdot x_{ij}^{pq} = z_{1} \) mit
\( z_{1} \leq w_{ci} \\
z_{1} \leq x_{ij}^{pq} \\
w_{ci}+x_{ij}^{pq} \leq 1 + z_{1} \\
z_{1} \geq 0 \)

Ich habe aber leider das Gefühl, dass das so nicht reicht.

Ich habe das Gefühl, dass das so reicht: 😃

Setze \( w_{ci}\cdot x_{ij}^{pq} = z_{cij}^{1pq} \) mit
\( z_{cij}^{1pq} \leq w_{ci} \\
z_{cij}^{1pq} \leq x_{ij}^{pq} \\
w_{ci}+x_{ij}^{pq} \leq 1 + z_{cij}^{1pq} \\
z_{cij}^{1pq} \geq 0 \)


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 73
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2020-06-02 19:19

Hey danke für deine Antwort Goswin. 🤗

Dann war mein Ansatz ja schon mal richtig. Ich muss lediglich alle Indizes betrachten um auch wirklich alle möglichen Paarungen zu linearisieren, korrekt?

Die rechte Seite der Ungleichung kann so bleiben, da sie bereits linear ist?


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1484
Aus: Chile, Ulm
Beitrag No.4, eingetragen 2020-06-03 13:55

2020-06-02 19:19 - Kingtom2 in Beitrag No. 3 schreibt:
ich habe hier eine Nebenbedingung, die ich gerne linearisieren möchte.

\[
\sum_{i=1}^{n-1} \sum_{j=1}^{n} \sum_{c\in C}
  c\, (w_{ci}\cdot x_{ij}^{pq}+w_{cj}\cdot x_{ij}^{pq})
~\geq~
2\, (1+2+...+( \sum_{i=1}^{n-1} \sum_{j=1}^{n} x_{ij}^{pq} -1))
\]
Dabei sind w und x binär und die Entscheidungsvariablen.
Die rechte Seite der Ungleichung kann so bleiben, da sie bereits linear ist?

Was lässt dich daran zweifeln?

Und wenn du die Bedingungen wie folgt hinschreibst, kommst du mit weniger zusätzlichen Variablen aus:
\[
\sum_{c\in C} c\, \Big(
  \sum_{i=1}^{n-1} w_{ci}\cdot \big(\sum_{j=1}^{n} x_{ij}^{pq}\big)
  + \sum_{j=1}^{n} w_{cj}\cdot \big(\sum_{i=1}^{n-1} x_{ij}^{pq}\big)
\Big)
~\geq~
2\cdot(1+2+...+( \sum_{i=1}^{n-1} \sum_{j=1}^{n} x_{ij}^{pq} -1))
\]


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 73
Aus:
Beitrag No.5, vom Themenstarter, eingetragen 2020-06-03 18:51

Wie kommst du darauf, dass es weniger sind?
Es macht doch gar keinen Sinn die Summen auseinander zuziehen oder habe ich da einen Denkfehler?


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1484
Aus: Chile, Ulm
Beitrag No.6, eingetragen 2020-06-04 01:39

2020-06-03 18:51 - Kingtom2 in Beitrag No. 5 schreibt:
Es macht doch gar keinen Sinn die Summen auseinander zuziehen oder habe ich da einen Denkfehler?

Du hast vollkommen recht, der Denkfehler geht auf meine Kosten:
Auch wenn die \(x^{pq}_{ij}\) binär sind, dann ist ihre Summe \(\sum_{j=1}^n x^{pq}_{ij}\) längst nicht binär. Und wenn diese Summe nicht binär ist, funktioniert mein Vorschlag nicht.


Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 73
Aus:
Beitrag No.7, vom Themenstarter, eingetragen 2020-06-04 16:25

Alles klar. Danke dir auf jeden Fall.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=247733=110
Druckdatum: 2020-08-06 15:32