WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Mixed Integer Programming im Bereich Floorplanning

 

Maughlin
Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 27.06.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 27.06.2019, 17:43     Titel: Mixed Integer Programming im Bereich Floorplanning
  Antworten mit Zitat      
Hallo zusammen,

ich habe folgende Schwierigkeit. Ich möchte bis zu 10 unterschiedlich große Rechtecke in einem diese umschließenden Rechteck platzieren und diese dort ohne Überlappung möglichst optimal anordnen. Da es sich um ein lineares Problem handelt ist die Breite des umschließenden Rechtecks fest definiert und die Höhe soll minimiert werden. Die einzelnen zu platzierenden Rechtecke haben eine gegebene Höhe (h) und Breite (w), sowie eine untere linke Ecke (x und y). Die Blöcke sollen zusätzlich um 90° rotierbar sein, also aus Höhe wird Breite und umgekehrt. Um die Überlappung zu vermeiden und die Rotation mit einzubeziehen habe ich folgende Randbedingungen aufgestellt:
Code:
x(i) + z(i)*h(i) + (1 - z(i)) * w(i) <=   x(j) + M(x(ij) + y(ij))
(1)
Code:
x(i) - z(j)*h(j) - (1 - z(j)) * w(j) >=   x(j) - M(1 - x(ij) + y(ij))
(2)
Code:
y(i) + z(i)*w(i) + (1 - z(i)) * h(i) <=   y(j) + M(1+x(ij) - y(ij))
(3)
Code:
y(i) - z(j)*w(j) - (1 - z(j)) * h(j) <=   y(j) - M(2- x(ij) - y(ij))
(4)

x(i) und y(i) sowie x(j) und y(j) sind die Eckpunkte von zwei unterschiedlichen Rechtecken. Diese Ungleichungen geben die Position der Rechtecke zueinander an, also:
(1) j ist rechts von i
(2) j ist links von i
(3) j ist über i
(4) j ist unter i

Außerdem ist M=max(W,H), wobei W und H die maximale Breite und Höhe des umschließenden Rechtecks sind. Die Variablen h(i) und w(i) sowie h(j) und w(j) die jeweiligen Höhen und Breiten. z(i) ist binär, also 1 oder 0, und gibt an ob das Rechteck rotiert ist oder nicht. x(ij) und y(ij) sind ebenfalls binär und "aktivieren" eine der ersten vier Ungleichungen, je nachdem welche Werte sie annehmen.

Code:

Code:

Code:
x(i)+(1-z(i))*w(i)+z(i)*h(i)<= W

Code:
y(i)+(1-z(i))*h(i)+z(i)*w(i)<= Y


Diese Ungleichungen dienen dem Einhalten der Begrenzung durch das umschließende Rechteck. Y ist der Wert der minimal sein soll, also in dem Fall die Höhe.

Die Quelle zu diesen Gleichungen/Ungleichungen hänge ich als Datei an. Sie sind dort unter dem Punkt 3.2. zu finden.

Und nun meine Frage, ich habe leider noch keinen Plan wie ich diese Ansätze implementiere. Gibt es dafür eine Funktion in Matlab um alles umzusetzen und wenn ja in welcher Form? Oder sollte ich versuchen alles mit Schleifen und if/else zu implementieren?

Schon einmal Danke im Voraus.

VG
Maughlin

PS Sollte ich was vergessen haben oder etwas nicht eindeutig ist, dann einfach Bescheid geben.

An Analytical Approach to Floorplan Design.pdf
 Beschreibung:

Download
 Dateiname:  An Analytical Approach to Floorplan Design.pdf
 Dateigröße:  944.88 KB
 Heruntergeladen:  298 mal
Private Nachricht senden Benutzer-Profile anzeigen


Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 27.06.2019, 17:54     Titel:
  Antworten mit Zitat      
Hallo,

Wenn das Problem linear und mixed integer ist, dann
intlinprog

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Maughlin
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 27.06.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 27.06.2019, 18:26     Titel:
  Antworten mit Zitat      
Danke für die schnelle Antwort,
mir ist leider nicht klar in welcher Form ich alles an intlinprog übergeben muss. In erster Linie bin ich mir nicht sicher was genau meine Zielfunktion ist und desweiteren sind Beispiel dazu immer nur mit x(1), x(2),..., aber bei meinem Problem gibt es noch y(1), y(2), usw.
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 27.06.2019, 18:49     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
In erster Linie bin ich mir nicht sicher was genau meine Zielfunktion ist

Das musst du entscheiden ;) Du meintest ja: "die Höhe soll minimiert werden". Das würde ich dann etwas wie max( y(i) + h(i) ansehen, wobei Drehungen wohl noch nicht berücksichtigt sind. Womit das Problem abweichend von deiner Angabe leider nicht mehr linear und intlinprog folglich nicht mehr geeignet wäre. Da bliebe nur ga.

Zitat:
desweiteren sind Beispiel dazu immer nur mit x(1), x(2),..., aber bei meinem Problem gibt es noch y(1), y(2), usw.

Das ist das geringste Problem... du erstellst einen langen Vektor, in dem du die x und y und auch noch die x(ij) aneinanderhängst.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Maughlin
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 27.06.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 29.06.2019, 14:28     Titel:
  Antworten mit Zitat      
Ich habe mich jetzt noch eine ganze Weile mit beiden Funktionen beschäftigt. Dabei stoße ich immer wieder auf das selbe Probleme. Eine mögliche Lösungsfunktion im linearen Fall sollte ja den Aufbau haben:
Code:
y=x1+x2+x3
nur so als Bsp., das würde in meinem Fall ja ungefähr so aussehen:
Code:
Y=x1+(1-x2)*h+x2*w
Wobei x1 für y(i) und x2 für z(i) steht. Die Werte für h und w stehen dann natürlich fest.
Nun stellt sich mir die Frage, wenn ich in meiner Zielfunktion zwei Variablen habe und in meinen Constraints aber fünf, wie soll ich das denn mit den genannten Funktionen umsetzen?
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 29.06.2019, 15:41     Titel:
  Antworten mit Zitat      
Hallo,

dann bekommen die Variablen, die nicht in der Zielfunktion vorkommen sollen, den Beitrag 0.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Maughlin
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 27.06.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 03.07.2019, 16:35     Titel:
  Antworten mit Zitat      
Ok, danke. Ich habe es so versucht wie du gesagt hast und ich bekomme ein zumindest ein Ergebnis, leider außerhalb der Begrenzungen.
Code:
p = optimproblem;
x = optimvar('x',4,'Type','integer','LowerBound',0,'UpperBound',23);
y = optimvar('y',4,'Type','integer','LowerBound',0,'UpperBound',23);
z = optimvar('z',16,'Type','integer','LowerBound',0,'UpperBound',1);

p.ObjectiveSense = 'minimize';
p.Objective= x(1)*0 + 1*y(1) + 4*z(1)+ (1-z(1))*5+x(2)*0 + 1*y(2) + 3*z(2)+ (1-z(2))*7+x(3)*0 + 1*y(3) + 6*z(3)+ (1-z(3))*4+x(4)*0 + 1*y(4) + 7*z(4)+ (1-z(4))*7+z(5)*0+z(6)*0+z(7)*0+z(8)*0+z(9)*0+z(10)*0+z(11)*0+z(12)*0+z(13)*0+z(14)*0+z(15)*0+z(16)*0;

p.Constraints.c1 = x(1)+z(1)*5+(1-z(1))*4-x(2)-23*z(5)+23*z(6)<=0;
p.Constraints.c2 = x(1)-z(2)*7-(1-z(2))*3-x(2)+23-23*z(5)+23*z(6)>=0;
p.Constraints.c3 = y(1)+z(1)*4+(1-z(1))*5-y(2)-23-23*z(5)+23*z(6)<=0;
p.Constraints.c4 = y(1)-z(2)*3-(1-z(2))*7-y(2)+46-23*z(5)-23*z(6)>=0;

p.Constraints.c5 = x(1)+z(1)*5+(1-z(1))*4-x(3)-23*z(7)+23*z(8)<=0;
p.Constraints.c6 = x(1)-z(3)*7-(1-z(3))*3-x(3)+23-23*z(7)+23*z(8)>=0;
p.Constraints.c7 = y(1)+z(1)*4+(1-z(1))*5-y(3)-23-23*z(7)+23*z(8)<=0;
p.Constraints.c8 = y(1)-z(3)*3-(1-z(3))*7-y(3)+46-23*z(7)-23*z(8)>=0;

p.Constraints.c9 = x(1)+z(1)*5+(1-z(1))*4-x(4)-23*z(9)+23*z(10)<=0;
p.Constraints.c10 = x(1)-z(4)*4-(1-z(4))*6-x(4)+23-23*z(9)+23*z(10)>=0;
p.Constraints.c11 = y(1)+z(1)*4+(1-z(1))*5-y(4)-23-23*z(9)+23*z(10)<=0;
p.Constraints.c12 = y(1)-z(4)*6-(1-z(4))*4-y(4)+46-23*z(9)-23*z(10)>=0;

p.Constraints.c13 = x(2)+z(2)*7+(1-z(2))*3-x(3)-23*z(11)+23*z(12)<=0;
p.Constraints.c14 = x(2)-z(3)*4-(1-z(3))*6-x(3)+23-23*z(11)+23*z(12)>=0;
p.Constraints.c15 = y(2)+z(2)*3+(1-z(2))*7-y(3)-23-23*z(11)+23*z(12)<=0;
p.Constraints.c16 = y(2)-z(3)*6-(1-z(3))*4-y(3)+46-23*z(11)-23*z(12)>=0;

p.Constraints.c13 = x(2)+z(2)*7+(1-z(2))*3-x(4)-23*z(13)+23*z(14)<=0;
p.Constraints.c14 = x(2)-z(4)*7-(1-z(4))*7-x(4)+23-23*z(13)+23*z(14)>=0;
p.Constraints.c15 = y(2)+z(2)*3+(1-z(2))*7-y(4)-23-23*z(13)+23*z(14)<=0;
p.Constraints.c16 = y(2)-z(4)*7-(1-z(4))*7-y(4)+46-23*z(13)-23*z(14)>=0;

p.Constraints.c21 = x(3)+z(3)*4+(1-z(3))*6-x(4)-23*z(15)+23*z(16)<=0;
p.Constraints.c22 = x(3)-z(4)*7-(1-z(4))*7-x(4)+23-23*z(15)+23*z(16)>=0;
p.Constraints.c23 = y(3)+z(3)*6+(1-z(3))*4-y(4)-23-23*z(15)+23*z(16)<=0;
p.Constraints.c24 = y(3)-z(4)*7-(1-z(4))*7-y(4)+46-23*z(15)-23*z(16)>=0;
values=solve(p);

Das ist meine Programmierung. Ich habe die Constraints für 4 Blöcke eingebaut. Die Blöcke haben die Maße b1 (4,5), b2 (3,7), b3 (6,4), b4 (7,7). Ich kann leider gerade nicht sagen was ich falsch gemacht habe oder anders machen müsste damit ich ein brauchbares Ergebnis bekommen. Außer vielleicht das umstellen der Ungleichungen. Ich habe sie, wie in der Beschreibung zur linearen Optimierung gesagt wird, in die Form Ax=b gebracht.
Code:

x(1)+z(1)*5+(1-z(1))*4<=x(2)+23*(z(5)+z(6));
x(1)-z(2)*7-(1-z(2))*3>=x(2)-23*(1-z(5)+z(6));
y(1)+z(1)*4+(1-z(1))*5<=y(2)+23*(1+z(5)-z(6));;
y(1)-z(2)*3-(1-z(2))*7>=y(2)-23*(2-z(5)-z(6));

Das ist die ursprüngliche Ungleichung zu den ersten vier Constraints.
Außerdem wäre es sehr gut, wenn es eine Möglichkeit gäbe mir die Werte von x(1)-x(4) bzw. y(1)-y(4) nach der Optimierung anzeigen zu lassen?
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 03.07.2019, 18:37     Titel:
  Antworten mit Zitat      
Hallo,

in der ersten Bedingung sehe ich auf Anhieb einen Vorzeichenfehler beim letzten Term 23*z(6).

Meines Erachtens spricht nichts gegen die ursprüngliche Form der Nebenbedingungen.

Anzeige der Werte:
Code:
values.x(1:4)


Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Maughlin
Themenstarter

Forum-Newbie

Forum-Newbie


Beiträge: 5
Anmeldedatum: 27.06.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 04.07.2019, 12:00     Titel:
  Antworten mit Zitat      
Ich habe die Constraints jetzt in der ursprünglichen Form belassen und denke, sie sollten soweit korrekt sein. Dazu habe ich noch die Breiten und Höhen der Blöcke in zwei Vektor zusammen gefasst und diese in den Constraints dementsprechend ersetzt. Außerdem habe ich jetzt nur 4 z-Variablen für die Rotation der Blöcke und zusätzlich 12 xy-Variablen für die Position der Blöcke zueinander. Zusätzlich habe ich noch 8 Constraints hinzugefügt, die die Positionen der Blöcke auf innerhalb des umschließenden Rechtecks beschränken
Code:
clear
clc
close all
format long

w = [4; 3; 6; 7];
h = [5; 7; 4; 7];

p = optimproblem;
x = optimvar('x',4,'Type','integer','LowerBound',0);
y = optimvar('y',4,'Type','integer','LowerBound',0);
z = optimvar('z',4,'Type','integer','LowerBound',0,'UpperBound',1);
xy = optimvar('xy',12,'Type','integer','LowerBound',0,'UpperBound',1);

p.ObjectiveSense = 'minimize';
p.Objective.o1= sum(y + ((w.*z).'+ ((1-z).*h).').');

p.Constraints.c1 = x(1)+z(1)*h(1)+(1-z(1))*w(1)<=x(2)+23*(xy(1)+xy(2));
p.Constraints.c2 = x(1)-z(2)*h(2)-(1-z(2))*w(2)>=x(2)-23*(1-xy(1)+xy(2));
p.Constraints.c3 = y(1)+z(1)*w(1)+(1-z(1))*h(1)<=y(2)+23*(1+xy(1)-xy(2));
p.Constraints.c4 = y(1)-z(2)*w(2)-(1-z(2))*h(2)>=y(2)-23*(2-xy(1)-xy(2));

p.Constraints.c5 = x(1)+z(1)*h(1)+(1-z(1))*w(1)<=x(3)+23*(xy(3)+xy(4));
p.Constraints.c6 = x(1)-z(3)*h(3)-(1-z(3))*w(3)>=x(3)-23*(1-xy(3)+xy(4));
p.Constraints.c7 = y(1)+z(1)*w(1)+(1-z(1))*h(1)<=y(3)+23*(1+xy(3)-xy(4));
p.Constraints.c8 = y(1)-z(3)*w(3)-(1-z(3))*h(3)>=y(3)-23*(2-xy(3)-xy(4));

p.Constraints.c9 = x(1)+z(1)*h(1)+(1-z(1))*w(1)<=x(4)+23*(xy(5)+xy(6));
p.Constraints.c10 = x(1)-z(4)*h(4)-(1-z(4))*w(4)>=x(4)-23*(1-xy(5)+xy(6));
p.Constraints.c11 = y(1)+z(1)*w(1)+(1-z(1))*h(1)<=y(4)+23*(1+xy(5)-xy(6));
p.Constraints.c12 = y(1)-z(4)*w(4)-(1-z(4))*h(4)>=y(4)-23*(2-xy(5)-xy(6));

p.Constraints.c13 = x(2)+z(2)*h(2)+(1-z(2))*w(2)<=x(3)+23*(xy(7)+xy(8));
p.Constraints.c14 = x(2)-z(3)*h(3)-(1-z(3))*w(3)>=x(3)-23*(1-xy(7)+xy(8));
p.Constraints.c15 = y(2)+z(2)*w(2)+(1-z(2))*h(2)<=y(3)+23*(1+xy(7)-xy(8));
p.Constraints.c16 = y(2)-z(3)*w(3)-(1-z(3))*h(3)>=y(3)-23*(2-xy(7)-xy(8));

p.Constraints.c17 = x(2)+z(2)*h(2)+(1-z(2))*w(2)<=x(4)+23*(xy(9)+xy(10));
p.Constraints.c18 = x(2)-z(4)*h(4)-(1-z(4))*w(4)>=x(4)-23*(1-xy(9)+xy(10));
p.Constraints.c19 = y(2)+z(2)*w(2)+(1-z(2))*h(2)<=y(4)+23*(1+xy(9)-xy(10));
p.Constraints.c20 = y(2)-z(4)*w(4)-(1-z(4))*h(4)>=y(4)-23*(2-xy(9)-xy(10));

p.Constraints.c21 = x(3)+z(3)*h(3)+(1-z(3))*w(3)<=x(4)+23*(xy(11)+xy(12));
p.Constraints.c22 = x(3)-z(4)*h(4)-(1-z(4))*w(4)>=x(4)-23*(1-xy(11)+xy(12));
p.Constraints.c23 = y(3)+z(3)*w(3)+(1-z(3))*h(3)<=y(4)+23*(1+xy(11)-xy(12));
p.Constraints.c24 = y(3)-z(4)*w(4)-(1-z(4))*h(4)>=y(4)-23*(2-xy(11)-xy(12));

p.Constraints.c25 = x(1)+z(1)*h(1)+(1-z(1))*w(1)<=23;
p.Constraints.c26 = x(2)+z(2)*h(2)+(1-z(2))*w(2)<=23;
p.Constraints.c27 = x(3)+z(3)*h(3)+(1-z(3))*w(3)<=23;
p.Constraints.c28 = x(4)+z(4)*h(4)+(1-z(4))*w(4)<=23;

p.Constraints.c29 = y(1)+z(1)*w(1)+(1-z(1))*h(1)<=23;
p.Constraints.c30 = y(2)+z(2)*w(2)+(1-z(2))*h(2)<=23;
p.Constraints.c31 = y(3)+z(3)*w(3)+(1-z(3))*h(3)<=23;
p.Constraints.c32 = y(4)+z(4)*w(4)+(1-z(4))*h(4)<=23;

showproblem(p);

values=solve(p);


Ich habe wirklich viel mit der Zielfunktion rumprobiert und glaube, dass sie das Hauptproblem ist. Ich weiß allerdings nicht wie ich es behebe. So wie sie jetzt ist erhalte ich als Ergebnis -5.
Mir ist nicht ganz klar wie ich die Zielfunktion so gestallte, dass auf die Position der Blöcke Rücksicht genommen wird, also wenn Block 2 rechts von Block 1 ist soll für die Optimierung nur die Höhe des höheren Blocks verwendet werden. Wenn Block 3 allerdings oberhalb von Block 1 liegt, so soll ja die Höhe von Block 3 plus die Höhe von Block 1 die momentane Höhe sein.
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 04.07.2019, 19:51     Titel:
  Antworten mit Zitat      
Hallo,

Zitat:
So wie sie jetzt ist erhalte ich als Ergebnis -5.

Von welchem Ergebnis sprichst du? Der optimale Zielfunktionswert ist jedenfalls 20.
Code:
[values, fval] =solve(p)


Zitat:
Mir ist nicht ganz klar wie ich die Zielfunktion so gestallte, dass auf die Position der Blöcke Rücksicht genommen wird, also wenn Block 2 rechts von Block 1 ist soll für die Optimierung nur die Höhe des höheren Blocks verwendet werden. Wenn Block 3 allerdings oberhalb von Block 1 liegt, so soll ja die Höhe von Block 3 plus die Höhe von Block 1 die momentane Höhe sein.

Siehe mein Beitrag von 27.06.2019, 19:49.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.