Übung 2 Lecture-Plan

Moderator: Algorithmische Modellierung

tastatur
Erstie
Erstie
Beiträge: 14
Registriert: 30. Mai 2006 15:10

Übung 2 Lecture-Plan

Beitrag von tastatur » 26. Jul 2011 17:31

Hallo,
ich wollte mich nicht nur mti dem Programmieren auf Papier begnügen und hatte mal versucht das Programm der Folien 63 und 64 in die aktuelle OPL Syntax zu übersetzen die auch unter dem aktuellen "IBM Ilog CPLEX Optimization Studio" läuft.
Dabei bin ich auf die folgende Syntax gekommen:

Code: Alles auswählen

using CP;

 int+ number_of_lectures= ...;
 int+ number_of_halls= ...;
 int+ number_of_slots= ...;
 
 range lectures = 1..number_of_lectures;
 range halls = 1..number_of_halls;
 range slots = 1..number_of_slots;
 
 int number_of_seats [halls]= ...;
 int number_of_students [lectures]= ...;
 
// range boolean = 0..1;
 
 boolean in_conflict[lectures][lectures]= ...;
 
var halls hall [lectures];
var slots slot [lectures];


subject to{
   forall (i in lectures, j in lectures)
     i!= j=> hall[i] != hall[j] || slot[i] != slot[j];
     forall ( i in lectures, j in lectures)
       in_conflict[i,j] => slot[i] != slot[j];
       forall (i in lectures)
         number_of_students[i] <= number_of_seats[hall[i]];
   };
Lecture.mod

Code: Alles auswählen

number_of_lectures= 4;
number_of_halls= 6;
number_of_slots= 8;

in_conflict= [[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
];
Lecture.dat

Ich bekomme bei der Definition von "var" jeweils das gleiche Problem angezeigt --> "syntax error unexpected (identifier), expecting ';'

Ist jemand damit weiter gekommen und hat ein lauffähiges Programm als Beispiel?
Zuletzt geändert von tastatur am 27. Jul 2011 14:07, insgesamt 1-mal geändert.

tobiasp
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Okt 2008 23:08

Re: Übung 2 Lecture-Plan

Beitrag von tobiasp » 26. Jul 2011 21:08

Probiers mal mit "dvar" statt "var"

tastatur
Erstie
Erstie
Beiträge: 14
Registriert: 30. Mai 2006 15:10

Re: Übung 2 Lecture-Plan

Beitrag von tastatur » 27. Jul 2011 11:48

Danke, funktioniert aber leider nicht- bekomme stattdessen nur noch mehr Fehler durch den Compiler angezeigt.
Hat jemand ein lauffähiges Programm zur Aufgabe 2 - geht mir weniger um den Algorithmus als um die Datenstruktur und var Deklaration.

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Übung 2 Lecture-Plan

Beitrag von MisterD123 » 27. Jul 2011 15:52

ich hab hier noch was altes von letztem jahr. ist nicht vollständig, nur die ersten paar teilaufgaben oder so, aber es generiert zumindest schonmal stundenpläne. ;) Oder generierte zumindest letztes jahr noch, habs seit dem nicht mehr ausprobiert.

Lesen auf eigene Spoiler-Gefahr. Plagiieren kann ihrer Gesundheit schaden! (Sollten betroffene Veranstalter Probleme mit einer öffentlich verfügbaren Lösung sehen bitte bescheid sagen, dann nehm ich sie wieder raus.)

Code: Alles auswählen

int number_of_lectures = ...;
int number_of_lecturers = ...;
int number_of_slots = ...;
int number_of_halls = ...;

range lectures = 1..number_of_lectures;
range lecturers = 1..number_of_lecturers;
range slots = 1..number_of_slots;
range halls = 1..number_of_halls;

// properties of halls
int number_of_seats[halls] = ...;
int equipment_insufficient[halls, lecturers] = ...; //boolean
int adjecent_slot_incompatible_halls[halls, halls] = ...; //boolean

// properties of lectures
int number_of_students[lectures] = ...;
int slot_requirement[lectures] = ...;
int lecturer[lectures] = ...; //lecturers
int in_conflict[lectures, lectures] = ...; //boolean

// properties of slots
int slots_overlapping[slots, slots] = ...; //boolean
int slots_adjecent[slots, slots] = ...; //boolean

// result definition: a schedule assigning either 0 or a lecture id to room and slot.
// assignment of 0 means this room at this slot is unoccupied!
dvar int schedule[halls, slots] in 0..number_of_lectures;
//int schedule[halls, slots] = ...;

subject to {
	//since the model assigns lecture ids to [hall,slot], there cannot be duplicate assignments for a single
	//combination of hall and slot. Therefore, this condition does not require an explicit formulation.

	forall (l in lectures){
		// all lectures must occupy the proper number of slots
		//sum(h in halls, s in slots) (schedule[h,s] == l) == slot_requirement[l];
		count(schedule, l) == slot_requirement[l];
	}

	// for all lecture dates:
	forall (l in lectures, h in halls, s in slots){
		(l == schedule[h,s]) => (
			//the hall must suffice the lecturers equipment requirement
			(equipment_insufficient[h,lecturer[l]] == 0) &&
			//the hall must have a sufficient number of seats
			(number_of_students[l] <= number_of_seats[h])
		);
	}
	
	// for all pairs of different lecture dates
	forall (l1, l2 in lectures, h1, h2 in halls, s1, s2 in slots : (h1 != h2) || (s1 != s2)){
		(l1 == schedule[h1,s1]) && (l2 == schedule[h2,s2]) => (
			(
				// same lecturer
				(lecturer[l1] == lecturer[l2]) ||
				// or conflict by students
				(in_conflict[l1,l2] != 0) ||
				// or same hall
				(h1 == h2)
			) => (
				// must be different slots
				(s1 != s2) &&
				// and slots must not overlap
				(slots_overlapping[s1,s2] == 0)
			)
			
			&&
		
			//separate but adjecent slots => halls must not be to far apart
			( (s1 != s2) && (slots_adjecent[s1,s2] != 0) => (adjecent_slot_incompatible_halls[h1,h2] == 0) )
		);
	}
}

Code: Alles auswählen

number_of_lectures = 6;
number_of_lecturers = 3;
number_of_slots = 8;
number_of_halls = 3;

number_of_seats = [10,20,30]; //#halls : int
equipment_insufficient = [ //#halls x #lecturers : bool
	[1, 0, 0],
	[0, 1, 0],
	[0, 0, 0]
];

adjecent_slot_incompatible_halls = [ //#halls x #halls : bool
	[0, 1, 1],
	[1, 0, 0],
	[1, 0 ,0]
];

number_of_students = [5, 12, 28, 8, 17, 25]; //#lectures : int
slot_requirement = [2, 1, 2, 3, 3, 1]; //#lectures : int
lecturer = [2, 1, 2, 3, 1, 3]; //#lectures : lecturers
in_conflict = [ //#lectures x #lectures : bool
	[1, 0, 1, 0, 0, 0],
	[0, 1, 1, 0, 1, 1],
	[1, 1, 1, 0, 0, 1],
	[0, 0, 0, 1, 0, 1],
	[0, 1, 0, 0, 1, 0],
	[0, 1, 1, 1, 0, 1] 
];

slots_overlapping  = [ //#slots x #slots : boolean
	[1, 1, 0, 0,   0, 0, 0, 0],
	[1, 1, 1, 0,   0, 0, 0, 0],
	[0, 1, 1, 1,   0, 0, 0, 0],
	[0, 0, 1, 1,   0, 0, 0, 0],
	
	[0, 0, 0, 0,   1, 1, 0, 0],
	[0, 0, 0, 0,   1, 1, 1, 0],
	[0, 0, 0, 0,   0, 1, 1, 1],
	[0, 0, 0, 0,   0, 0, 1, 1]
];

slots_adjecent = [ //#slots x #slots : boolean
	[0, 0, 1, 0,   0, 0, 0, 0],
	[0, 0, 0, 1,   0, 0, 0, 0],
	[1, 0, 0, 0,   0, 0, 0, 0],
	[0, 1, 0, 0,   0, 0, 0, 0],

	[0, 0, 0, 0,   0, 0, 1, 0],
	[0, 0, 0, 0,   0, 0, 0, 1],
	[0, 0, 0, 0,   1, 0, 0, 0],
	[0, 0, 0, 0,   0, 1, 0, 0]
];

tastatur
Erstie
Erstie
Beiträge: 14
Registriert: 30. Mai 2006 15:10

Re: Übung 2 Lecture-Plan

Beitrag von tastatur » 27. Jul 2011 19:56

Danke für den Code. Bei mir läuft dieser unter IBM Ilog OPL Ide 6.3 aber NICHT im ILOG OPL CPlex Optimizer Studio. Nur als kleine Info für alle die mal ein Programm nicht zum laufen bekommen haben und nicth wirklich nachvollziehen konnten woran es liegt!

Antworten

Zurück zu „Algorithmische Modellierung“