Lösungen

Moderator: Algorithmische Modellierung

joh
Gast

Lösungen

Beitrag von joh » 24. Jul 2007 16:53

Hallo,

Die Zeit zum Zähne ausbeißen wird ja nun langsam knapp,
leider gibt es ja keine abgesegneten Musterlösungen,
wäre jemand bereit jetzt seine Lösungen zu veröffentlichen?
Das wäre denke ich eine große Hilfe beim Verständnis einzelner Modellierungen.

Schonmal Danke und Gruß

Pinky
Erstie
Erstie
Beiträge: 18
Registriert: 15. Dez 2005 01:37

Beitrag von Pinky » 24. Jul 2007 19:37

Im alten Forum gibt es einige Lösungen, Link: http://www.fachschaft.informatik.tu-dar ... .php?f=229

Ansonsten hier mal meine Lösungen, bei denen ungefähr das geforderte Modell rausgekommen ist ...

Ich wäre insbesondere an einem Lösungsansatz für die 4.2 interessiert ... da habe ich nichts gefunden, was auch nur vom Prinzip her funktionieren würde ...

1.2) Das kann man sicher auch schöner machen ...

Code: Alles auswählen

int+ MengeWasserstoff = 170;
int+ MengeKohlenstoff = 1000;

//Runterrechnen auf die Verhältnisse also 16 Tonnen Methan bzw. 30 Tonnen Ethan
//int+ GewinnMethan = 80;
//int+ GewinnEthan = 100;
int+ GewinnMethan = 1280;
int+ GewinnEthan = 3000;

//MengeMethan * 16 ist die produzierte Menge Methan
var int+ MengeMethan in 0..MengeWasserstoff;
//MengeEthan * 30 ist die produzierte Menge Ehtan
var int+ MengeEthan in 0..MengeWasserstoff;

maximize(MengeMethan * GewinnMethan + MengeEthan * GewinnEthan) subject to {
   MengeMethan * 4 + MengeEthan * 6 <= MengeWasserstoff;
   MengeMethan * 12 + MengeEthan * 24 <= MengeKohlenstoff;
};
3.2) Da habe ich aber die Verkehrstage, Verbindungen die über 0:00 Uhr gehen und mehrere Abfragen (statt einer) noch nicht berücksichtigt.
Datafile:

Code: Alles auswählen

anzBhf = 4;
umsteigeZeiten = [5,10,2,5];
anzZugabschnitte = 6;

alleZA = [<1, 100, 3, 150, 4, 1, 1>,
         <3, 155, 4, 185, 5, 0, 1>,
         <1, 50,  2,  80, 5, 0, 2>,
         <2, 85,  3, 115, 10, 0, 2>,
         <3, 165, 4, 195, 3, 1, 2>,
         <1, 105, 4, 155, 4, 0, 3>];

anzahlZuege = 3;

//outdated
zuegeSet = {
   <{1,2}, 0>,
   <{3,4,5}, 0>,
   <{6}, 1>
};

zuege = [
   <{1,2}, 0>,
   <{3,4,5}, 0>,
   <{6}, 1>
   ];

icZuschlag = 2.0;

abfragen = <1, 4, 1, 0>; 

Model:

Code: Alles auswählen

/*** Datentypen ***/
/*** Eingabe ***/
range boolean 0..1;
//Minuten pro Tag
range RZeit 0..1440;
//range verkehrstag 1..7;

int+ anzBhf = ...;
range RBhf 1..anzBhf;
int+ anzZugabschnitte = ...;
range RZA 1..anzZugabschnitte;
int+ anzahlZuege = ...;
range RZuege 1 .. anzahlZuege;

int+ umsteigeZeiten[RBhf] = ...;

float+ icZuschlag = ...;

struct Zugabschnitt {
   RBhf abfahrtBhf;
   RZeit abfahrtZeit;
   RBhf ankunftBhf;
   RZeit ankunftZeit;
   float+ preis;
   boolean keinFahrad;
   RZuege zugID;
};

Zugabschnitt alleZA[RZA] = ...;

struct Zug {
   {RZA} zugZA;
   //{verkehrstag} verkehrstage;
   boolean ic;
};

struct Abfrage {
   RBhf start;
   RBhf ziel;
   boolean keinIC;
   boolean fahrad;
};

{Zug} zuegeSet = ...;
//Array damit eindeutige Zugkennung und Zugriff darauf möglich ist
Zug zuege[RZuege] = ...;

Abfrage abfragen = ...;

/*** ausgabe ***/
var boolean benutzteZA[RZA];
var float+ preis;

var boolean benIC;

/*** Model ***/
minimize preis subject to {
   //**Definiert die Kostenberechnung
   //Wird IC benutzt?
   sum (i in RZA) benutzteZA[i] * zuege[alleZA[i].zugID].ic > 0 => benIC = 1;
   //Bestimmen des Fahrpreises
   preis = sum (i in RZA) benutzteZA[i] * alleZA[i].preis 
           + benIC * icZuschlag 
           //teuerster preisaufschlag für ic-benutzung, wenn kein ic gewünscht.
           + benIC * abfragen.keinIC * maxint
           //analog mit fahrad, wenn fahrad gewünscht kosten strecken ohne fahrad sauviel
           + sum (i in RZA) benutzteZA[i] * alleZA[i].keinFahrad * abfragen.fahrad * maxint;
   
   //**Definieren der Verbindung
   
   //*Zugabschnitte/Stationen müssen eine Strecke bilden
   
   //keine Kreise um Knoten - nötig? Kosten sollten eigentlich > 0 sein ...
   forall(i in RBhf) 
      sum (j in RZA) (benutzteZA[j] * alleZA[j].ankunftBhf = i) <= 1;
   
   //Start und Zielpunkte müssen passen, also genau einmal in benutzte sein
   (sum (i in RZA) (alleZA[i].abfahrtBhf * benutzteZA[i] = abfragen.start)) = 1;
   (sum (i in RZA) (alleZA[i].ankunftBhf * benutzteZA[i] = abfragen.ziel)) = 1;

   //Jeder benutzte Bahnhof muss gleichviele eingehende und ausgehende Kanten haben
   forall ( i in RBhf ) 
       i <> abfragen.start & i <> abfragen.ziel
       => sum (j in RZA) (benutzteZA[j] * alleZA[j].abfahrtBhf = i) 
          = sum (j in RZA) (benutzteZA[j] * alleZA[j].ankunftBhf = i);

   //*Zugabschnitte müssen zeitlich passen
   forall(i in RZA, j in RZA) 
      benutzteZA[i] * alleZA[i].ankunftBhf = benutzteZA[j] * alleZA[j].abfahrtBhf <> 0
      => alleZA[i].ankunftZeit
         //Bei Zugwechsel müssen die Umsteigezeiten beachtet werden
         + ((alleZA[i].zugID <> alleZA[j].zugID) * umsteigeZeiten[alleZA[i].ankunftBhf]) 
         <= alleZA[j].abfahrtZeit;
  
   
};
4.1) Da habe ich erstmal mit unterbrechbaren Jobs gearbeitet und das hinterher auf nicht unterbrechbar umgebastelt (wer lesen kann ist klar im Vorteil ...), das geht auch einfacher ... ich glaube im alten Forum ist dazu ne Lsg.
Datafile:

Code: Alles auswählen

planungshorizont = 19;

anzRessourcen = 3;

verfRessourcen = [
   5, //Arbeitskräfte
   1, //Betonmischer
   1  //Kran
];

anzJobs = 4;

jobs = [
   <1, planungshorizont, 4, [0,0,0,0], [1,1,0]>, //Fundament
   <1, 5, 3, [0,0,0,0], [1,1,0]>, //Irgendwas mit Deadline
   <1, planungshorizont, 6, [1,0,0,0], [1,1,0]>, //Wände
   <8, planungshorizont, 5, [0,0,1,0], [1,0,1]> //Dach
];
Model:

Code: Alles auswählen

range boolean 0..1;
int invert = -1;

//Eingabe
int+ planungshorizont = ...;
range RPlanungsH 1..planungshorizont;

int+ anzRessourcen = ...;
range RRes 1..anzRessourcen;
int+ verfRessourcen[RRes] = ...;

int+ anzJobs = ...;
range RJobs 1..anzJobs;

struct Job {
   RPlanungsH start;
   RPlanungsH ende;
   RPlanungsH dauer;
   boolean benJobs[RJobs];
   boolean benRes[RRes];
};

Job jobs[RJobs] = ...;

//Ausgabe
var RPlanungsH dauer;
var boolean planung[RJobs, RPlanungsH];
var RPlanungsH out[RJobs];

/*** Model ***/
minimize dauer subject to {
   //Dauer ist der letzte Tag an dem noch ein Job läuft
   dauer = max (i in RPlanungsH) (sum (j in RJobs) planung[j,i] > 0) * i;

   //Jeder Job muß seine Dauer dauern ;)
   forall (i in RJobs) sum (j in RPlanungsH) planung[i,j] = jobs[i].dauer;

   //Jobs sind nicht unterbrechbar - auskommentieren wenn unterbrechbar ...
   forall (i in RJobs) ((max (k in RPlanungsH) planung[i, k] * k) 
      - (planungshorizont - (max (k in RPlanungsH) (planungshorizont * planung[i, k] - k))))
      = (jobs[i].dauer - 1);
   
   //Jeder Job muß nach seinem start beginnen und vor seinem Ende beendt sein
   // -- jobs[i].start > 1 => damit auch erster zeitslot belegt wird, bei start = 1
   forall (i in RJobs) jobs[i].start > 1 => sum (j in [1..jobs[i].start]) planung[i,j] = 0;
   forall (i in RJobs) sum (j in [jobs[i].ende..planungshorizont]) planung[i,j] = 0;
   

   //Keine Ressource darf überansprucht werden
   forall (i in RRes) forall (j in RPlanungsH) 
      sum (k in RJobs) planung[k,j] * jobs[k].benRes[i] <= verfRessourcen[i];

   //Vorbedingungen müssen erfüllt sein, bevor ein Job starten darf
   // -- basicly: der letzte slot des vorbedingungsjobs muß kleiner sein, als der erste des
   //    nachfolgenden jobs. das (k-1) damit nicht die letzten slots überschneiden.
   forall (i in RJobs, j in RJobs) ((max (k in RPlanungsH) planung[i, k] * k * jobs[j].benJobs[i])
      <= (planungshorizont - (max (k in RPlanungsH) (planungshorizont * planung[j, k] - (k - 1)))));
    
};
4.5) Ein schönes Beispiel dafür, das ein Model einfacher sein kann, als eine Freitext Aufgabenstellung ;)
Datafile:

Code: Alles auswählen

n = 3;
m = 5;

A = [[0,1,0,1,0],
     [1,0,0,1,0],
     [0,1,0,1,1]];
Model:

Code: Alles auswählen

range boolean 0..1;

int n = ...;
int m = ...;

int maxWert = n * m;
range RMaxW 0..maxWert;

range Rn 1..n; //Zeilen
range Rm 1..m; //Spalten

boolean A[Rn, Rm] = ...;

var Rm sigma[Rm];
var RMaxW x[Rm]; //Die x_j 
var boolean y[Rn, Rm];

minimize sum (i in Rm) (x[i]) subject to {
   //Die y[i,j] sind 1, wenn die 1. 1 in Zeile i links von spalte j und 
   //die letzte 1 in zeile i rechts von spalte j ist.
   forall (i in Rn, j in Rm) (( m - max (k in [1..j-1]) (m * A[i, sigma[k]] - k ) = j-1) 
      & max (k in [j..m]) (k * A[i, sigma[k]]) = j+1)
      = y[i, sigma[j]];

   //Die x[j] sind die summe der kennzahlen der y_i,j, eigentlich brauchts hier
   //die zuordnung zu den permutationen nicht, aber so wird das ergebnis lesbarer
   forall (i in Rm) x[sigma[i]] = sum (j in Rn) y[j, sigma[i]];

   //Eine Permutation muß jedes Element auf genau ein element abbilden
   forall (i in Rm) ((sum (j in Rm) (sigma[j] = i)) = 1);  
   //Zum Debuggen, Permutation die jedes Element auf sich selber abbildet
   //forall (i in Rm) (sigma[i] = i);  

};
5.2) Die ist noch nicht fertig! Momentan nur ein normales Steinerbaumproblem, aber alle Vorbereitungen für das Steinerpacken Problem sind da ... Da habe ich mal mit den OPL-sets und if ... then ... endif; rumexperimentiert ... Da mich das einiges an Nerven gekostet hat, hilft es vielleicht jemandem das gleiche Schicksal zu ersparen ...
Datafile:

Code: Alles auswählen

anzKnoten = 5;
anzTerminals = 3;

terminals = {2, 4, 5};
Model:

Code: Alles auswählen

range boolean 0..1;

int+ anzKnoten = ...;
range RKnoten 1..anzKnoten;

int+ anzTerminals = ...; // aka. "k"
range RTerminals 0..anzTerminals;
range RTerminals2 2..anzTerminals;

{RKnoten} terminals = ...;

//Muß leider hier initialisiert werden, im datafile knallts wg. maxint ...
int+ kanten[RKnoten, RKnoten] 
       = [[maxint, 1, maxint, 1, maxint],
          [1, maxint, 1, maxint, maxint],
          [maxint, 1, maxint, 1, 1],
          [1, maxint, 1, maxint, maxint],
          [maxint, maxint, 1, maxint, maxint]];
          
var boolean y[RKnoten, RKnoten];
var boolean x[RTerminals2, RKnoten, RKnoten];
var RTerminals gehoertZuTerminalSet[RKnoten];  

minimize sum(i in RKnoten, j in RKnoten) ((i>j) * y[i,j] * kanten[i,j]) 
   subject to {

   //die beiden constraints von 259, also beziehung von x und y modellieren
   forall (k in RTerminals2) forall (i in RKnoten, j in RKnoten) 
      x[k, i, j] <= y[i, j] & x[k, j, i] <= y[i, j]; 
   
   //ausgehend vom ersten terminal, pfade zu allen anderen terminals definieren
   //start- und zielterminal haben genau eine ausgehende bzw. eingehende kante
   forall (i in terminals)
      if (ord(terminals, i) <> 0) then 
         (sum (j in RKnoten) (terminals.first() <> j & terminals.ord(i) <> 0
            & x[terminals.ord(i) + 1, terminals.first(), j] > 0)) = 1
      endif;
   forall (i in terminals) 
      if (ord(terminals, i) <> 0) then 
         (sum (j in RKnoten) (i <> j & x[terminals.ord(i) + 1,j,i] > 0)) = 1
      endif;
   
   //Speichern das die Terminalknoten zu dem entsprechenden Terminalset gehören
   forall (i in terminals) gehoertZuTerminalSet[i] = 1;
   
   //alle anderen knoten haben gleichviele ein- bzw. ausgehende kanten
   forall (i in RTerminals2, j in RKnoten) {
      sum (k in RKnoten) x[i,j,k] = sum (k in RKnoten) x[i,k,j];

      //Speichern, dass die Knoten auf dem Weg auch zu den entsprechenden 
      //Terminalsets gehören, damit erreicht man allerdings das 
      //constraints-limit der opl trial...
//      forall (k in RKnoten) 
//            x[i,j,k] = 1 => gehoertZuTerminalSet[j] = gehoertZuTerminalSet[k] = 1;
   };
   
};

Benutzeravatar
Ultr1
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 13. Okt 2004 17:53
Wohnort: Dreieich
Kontaktdaten:

Re: Lösungen

Beitrag von Ultr1 » 24. Aug 2008 12:21

So,
ich hätte auch noch die ein oder andere Frage offen, und will dazu auch nochmal den ein oder anderen Codeschnipsel posten:

Aufgabe 1.3.b: alldifferent

Den Fall alldiffrent für das eindimensionale Array habe icb erfolgreich modelliert, für den zweidimensionalen gibt der Solver aber falsche Lösungen aus, obwohl ich es meiner Meinung nach korrekt modelliert habe:

Code: Alles auswählen

 using CP;
 int m_size = ...;
 int n_size = ...;
 int number_of_values = ...;
 range m = 1..m_size;
 range n = 1..n_size;
 range values = 1..number_of_values;
 dvar int ausgabe[m,n] in values;
 
 subject to {
 	forall (i in m, j in n, k in m, l in  n)
 		i != k && j == l => ausgabe[i,j] != ausgabe[k,l];
 };
dat.file:

Code: Alles auswählen

 m_size = 10;
 n_size = 10;
 number_of_values = 100;
In der Ausgabe gibt es nur keinen Schnitt in den Zeilen und Spalten, aber eigentlich sollte ein Wert doch nur einmal im anzen Konstrukt auftauchen?

EDIT: Habe es nun einfach so gelöst:

Code: Alles auswählen

forall (i in values)
     sum(j in m, k in n) (ausgabe[j,j] == i)  == 1;

Aufgabe 4.2: Graph drawing
Ist die Idee soweit richtig? Ich kann das getippte leider nicht nachprüfen, da es immer zu cannot replay solution Fehlern kommt. Das passiert immer sobald ich die euklidischen Distanzen bilden möchte:

Code: Alles auswählen

using CP;

 int number_of_nodes = ...;
 range nodes = 1..number_of_nodes;
 
 int edge[nodes,nodes] = ...;
 
 dvar int x[nodes];
 dvar int y[nodes];
 dvar int quality;
 dvar int two_node_repell;
 dvar int two_node_attract;
 dvar int node_edge_repell;
 dvar int two_edge_repell;
  
 maximize quality;
 subject to {
 	quality == two_node_repell + two_node_attract + node_edge_repell + two_edge_repell;
 	
 	// zwei knoten stoßen sich in ihrer distanz quadratisch ab, wenn es keine kante gibt
 	two_node_repell == sum(i in nodes, j in nodes) (   (edge[i,j] == 0 && i != j) * ( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) ) );
 	
 	// zwei knoten ziehen sich quadratisch an wenn sie über eine kante verbunden sind
 	two_node_attract == sum (i in nodes, j in nodes) ( (edge[i,j] == 1 && i != j) * (-1) * ((x[i]-x[j])*(x[i]-x[j]))+((y[i]-y[j])*(y[i]-y[j])));
 	
 	// ein knoten stößt eine Kante ab, bzgl der distanz zu ihren beiden endpunkten
 	node_edge_repell == sum(i in nodes, j in nodes, k in nodes) 
 	( 
 		(edge[i,j] == 1 && i != j)  *
 		( 	(x[i]-x[k])*(x[i]-x[k])  +  (y[i]-y[k])*(y[i]-y[k]) + 
 			(x[j]-x[k])*(x[j]-x[k])  +  (y[j]-y[k])*(y[j]-y[k])
 		)
 		// eigentlich halbieren für durschnitt, aber der summant müsste sowieso noch gewichtet werden
 	);
 	
 	// zwei kanten stoßen sich durch ihre endpunkte zueinander ab (achtung dauert zu lange)
 	two_edge_repell == sum (i in nodes, j in nodes, k in nodes, l in nodes)
 		((edge[i,j] == 1 && edge[k,l] == 1 && i != j && k != l && i != k && i != l && j != k && j != l)
 			*   (((x[i]-x[k])*(x[i]-x[k]))+((y[i]-y[k])*(y[i]-y[k]))) +
 				(((x[i]-x[l])*(x[i]-x[l]))+((y[i]-y[l])*(y[i]-y[l]))) +
 				(((x[j]-x[k])*(x[j]-x[k]))+((y[j]-y[k])*(y[j]-y[k]))) +
 				(((x[j]-x[l])*(x[j]-x[l]))+((y[j]-y[l])*(y[j]-y[l])))
 		);
 };
.dat-file:

Code: Alles auswählen

 number_of_nodes = 6;
 
 edge = [
 	[0,1,1,0,0,0],
 	[1,0,1,1,0,0],
 	[1,1,0,0,1,0],
 	[0,1,0,0,1,1],
 	[0,1,0,1,0,1],
 	[0,0,0,1,1,0]
 ];
Ich habe die euklidische Distanz relativ ausführlich ausgeschrieben, hätte auch pow und sqrt benutzen können. Insbesondere sqrt sollte relativ an der Lösung nichts ändern.

EDIT: Das Problem scheint die Komplexität zu sein. Wenn ich einen keliener Faktor vor die komplexen Forces setze erhalte ich keine Error. Das Programm terminiert aber einfach nicht mehr. Ich nehme an das liegt daran: Der Solver testet ja mit einer guten Strategie Belegung für Belegung durch. Für jede Belegung muss von jedem Knoten zu jedem die euklidische Distanz berechnet werden. Und schon haben wir den Salat. Es kann auch nicht im Script Block berechnet werden, da die Lösung ja direkt davon abhängt. Es diese Aufgab denn überhaupt praktisch lösbar?



Aufgabe 4.2: Zugüberdeckung, Data Reduction

Zunächst ist mir nicht ganz klar, was in der Aufgabe gefordert ist. Soll ich einfach einen Beispiel-Graphen wählen, dann die Reduktion darauf anwenden und für dieses Beispiel damit zeigen, dass mind. ein isolierter Knoten und mind. eine Zusammenhangskomponente übrig bleibt?

Auch in der Modellierung tue ich mich schwer:

Code: Alles auswählen

using CP;
 int number_of_trains = ...;
 int number_of_stations = ...;
 range trains = 1..number_of_trains;
 range stations = 1..number_of_stations;
 range bool = 0..1;
 {int} drives[trains] = ...;  // zugketten
 
 // was nach der reduktion noch übrig is
 dvar int train_out[trains] in bool;
 dvar int stations_out[stations] in bool;
  
  // ich nehme an, dass es in der eingabe keine in ihrer fahrt identischen züge gibt
  // außerdem darf ein zug in seiner fahrt nicht einen bf zweimal besuchen
  
 subject to {
 	// besucht ein zug I alle stationen wie Zug J, so fliegt I raus 	
 	forall (i in trains)
 		( max(j in trains)
 			( (i != j) * (card(drives[i] inter drives[j]) == card(drives[i])) )  // inter ist die schnittmenge, card ist vergleichbar zu size
 		) == 0 => train_out[i] == 1;
 		
 	// Wenn jeder Zug, der Bf. I besucht, auch Bf X besucht, so lösche den Bahnhof I
 	// ????????????? 	 		
 };
.dat-file:

Code: Alles auswählen

 number_of_trains = 3;
 number_of_stations = 4;
 
 // jeder der züge, der Bf 2 oder auch 3 besucht, besucht auch Bf 1=> Bf 2 und 3 fliegt raus
 // train 2 und 3 sind teilmenge von train 1 => train 2 und 3 fliegen raus
 drives = [
 	{1,2,3,4},
 	{1,2,3},
 	{4,1},
 ];
Mir fehlen hier etwas die Ideen, wie ich besonders "Wenn jeder Zug, der Bf. I besucht, auch Bf X besucht, so lösche den Bahnhof I " modellieren kann.


Aufgabe 5.1: TSP als ILP
Scheitert bei mir genau wie bei der Graph-drawing Aufgabe an einem Error bei den euklidischen Distanzen. Deshalb kam ich leider nicht einmal dazu u, x[i,k] {2,...,k} etc. zu modellieren. Hat hier jemand ein funktionierende Lösung?


Aufgabe 5.2: Steiner-Tree als ILP
Ich habe das y[{v,w}] modelliert , weiß aber nicht wie ich das x[i,{v,w}] modellieren soll ( siehe Folie 255 ff.) Genauer habe ich bereits hier mal nachgefragt


Vielen Dank schomla im Vorraus für alle Tipps.
Gruß
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

Antworten

Zurück zu „Algorithmische Modellierung“