Mixed Integer Programming im Bereich Floorplanning

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

Partner:

Forum

Option

[Erweitert]

• Diese Seite per Mail weiterempfehlen

Gehe zu:

Maughlin

Forum-Newbie


	Beiträge: 5

	Anmeldedatum: 27.06.19

	Wohnort: ---

	Version: ---

Verfasst am: 27.06.2019, 17:43 Titel: Mixed Integer Programming im Bereich Floorplanning

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))

Funktion ohne Link?

(1)

Code:

x(i) - z(j)*h(j) - (1 - z(j)) * w(j) >= x(j) - M(1 - x(ij) + y(ij))

Funktion ohne Link?

(2)

Code:

y(i) + z(i)*w(i) + (1 - z(i)) * h(i) <= y(j) + M(1+x(ij) - y(ij))

Funktion ohne Link?

(3)

Code:

y(i) - z(j)*w(j) - (1 - z(j)) * h(j) <= y(j) - M(2- x(ij) - y(ij))

Funktion ohne Link?

(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:

x(i)>=0

Funktion ohne Link?

Code:

y(i)>=0

Funktion ohne Link?

Code:

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

Funktion ohne Link?

Code:

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

Funktion ohne Link?

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:

354 mal

Harald

Forum-Meister


	Beiträge: 24.495

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 27.06.2019, 17:54 Titel:

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 ;)

Maughlin

Themenstarter

Forum-Newbie


	Beiträge: 5

	Anmeldedatum: 27.06.19

	Wohnort: ---

	Version: ---

Verfasst am: 27.06.2019, 18:26 Titel:

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.

Harald

Forum-Meister


	Beiträge: 24.495

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 27.06.2019, 18:49 Titel:

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 ;)

Maughlin

Themenstarter

Forum-Newbie


	Beiträge: 5

	Anmeldedatum: 27.06.19

	Wohnort: ---

	Version: ---

Verfasst am: 29.06.2019, 14:28 Titel:

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

Funktion ohne Link?

nur so als Bsp., das würde in meinem Fall ja ungefähr so aussehen:

Code:

Y=x1+(1-x2)*h+x2*w

Funktion ohne Link?

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?

Harald

Forum-Meister


	Beiträge: 24.495

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 29.06.2019, 15:41 Titel:

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 ;)

Maughlin

Themenstarter

Forum-Newbie


	Beiträge: 5

	Anmeldedatum: 27.06.19

	Wohnort: ---

	Version: ---

Verfasst am: 03.07.2019, 16:35 Titel:

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);

Funktion ohne Link?

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));

Funktion ohne Link?

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?

Harald

Forum-Meister


	Beiträge: 24.495

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 03.07.2019, 18:37 Titel:

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)

Funktion ohne Link?

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 ;)

Maughlin

Themenstarter

Forum-Newbie


	Beiträge: 5

	Anmeldedatum: 27.06.19

	Wohnort: ---

	Version: ---

Verfasst am: 04.07.2019, 12:00 Titel:

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);

Funktion ohne Link?

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.

Harald

Forum-Meister


	Beiträge: 24.495

	Anmeldedatum: 26.03.09

	Wohnort: Nähe München

	Version: ab 2017b

Verfasst am: 04.07.2019, 19:51 Titel:

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)

Funktion ohne Link?

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 ;)


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 |

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.