Antworte auf:  Linearisierung einer Nebenbedingung von Kingtom2
Forum:  Numerik & Optimierung, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Beitrag No.7, eingetragen 2020-06-04 16:25    [Diesen Beitrag zitieren]

Alles klar. Danke dir auf jeden Fall.


Goswin
Senior
Dabei seit: 18.09.2008
Mitteilungen: 1502
Herkunft: Chile, Ulm
 Beitrag No.6, eingetragen 2020-06-04 01:39    [Diesen Beitrag zitieren]

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: 82
Herkunft:
 Beitrag No.5, eingetragen 2020-06-03 18:51    [Diesen Beitrag zitieren]

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: 1502
Herkunft: Chile, Ulm
 Beitrag No.4, eingetragen 2020-06-03 13:55    [Diesen Beitrag zitieren]

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: 82
Herkunft:
 Beitrag No.3, eingetragen 2020-06-02 19:19    [Diesen Beitrag zitieren]

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: 1502
Herkunft: Chile, Ulm
 Beitrag No.2, eingetragen 2020-06-01 22:50    [Diesen Beitrag zitieren]

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: 82
Herkunft:
 Beitrag No.1, eingetragen 2020-05-29 16:58    [Diesen Beitrag zitieren]

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



Kingtom2
Aktiv
Dabei seit: 03.05.2019
Mitteilungen: 82
Herkunft:
 Themenstart: 2020-05-29 16:38    [Diesen Beitrag zitieren]

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


 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 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]