001    package net.sf.cpsolver.ifs.example.tt;
002    
003    import java.io.File;
004    import java.io.FileInputStream;
005    import java.io.FileOutputStream;
006    import java.io.IOException;
007    import java.util.ArrayList;
008    import java.util.HashSet;
009    import java.util.HashMap;
010    import java.util.Iterator;
011    import java.util.List;
012    import java.util.Map;
013    import java.util.Set;
014    import java.util.TreeSet;
015    
016    import net.sf.cpsolver.ifs.model.Constraint;
017    import net.sf.cpsolver.ifs.model.Model;
018    import net.sf.cpsolver.ifs.solution.Solution;
019    import net.sf.cpsolver.ifs.util.DataProperties;
020    import net.sf.cpsolver.ifs.util.ToolBox;
021    
022    import org.dom4j.Document;
023    import org.dom4j.DocumentException;
024    import org.dom4j.DocumentHelper;
025    import org.dom4j.Element;
026    import org.dom4j.io.OutputFormat;
027    import org.dom4j.io.SAXReader;
028    import org.dom4j.io.XMLWriter;
029    
030    /**
031     * Simple Timetabling Problem. <br>
032     * <br>
033     * The problem is modelled in such a way that every lecture was represented by a
034     * variable, resource as a constraint and every possible location of an activity
035     * in the time and space was represented by a single value. It means that a
036     * value stands for a selection of the time (starting time slot), and one of the
037     * available rooms. Binary dependencies are of course represented as constraints
038     * as well.
039     * 
040     * @version IFS 1.2 (Iterative Forward Search)<br>
041     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
042     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
043     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
044     * <br>
045     *          This library is free software; you can redistribute it and/or modify
046     *          it under the terms of the GNU Lesser General Public License as
047     *          published by the Free Software Foundation; either version 3 of the
048     *          License, or (at your option) any later version. <br>
049     * <br>
050     *          This library is distributed in the hope that it will be useful, but
051     *          WITHOUT ANY WARRANTY; without even the implied warranty of
052     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
053     *          Lesser General Public License for more details. <br>
054     * <br>
055     *          You should have received a copy of the GNU Lesser General Public
056     *          License along with this library; if not see
057     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
058     */
059    public class TimetableModel extends Model<Activity, Location> {
060        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableModel.class);
061        private int iNrDays, iNrHours;
062    
063        public TimetableModel(int nrDays, int nrHours) {
064            super();
065            iNrDays = nrDays;
066            iNrHours = nrHours;
067        }
068    
069        public int getNrDays() {
070            return iNrDays;
071        }
072    
073        public int getNrHours() {
074            return iNrHours;
075        }
076    
077        @SuppressWarnings("unchecked")
078        public static TimetableModel generate(DataProperties cfg) {
079            int nrDays = cfg.getPropertyInt("Generator.NrDays", 5);
080            int nrHours = cfg.getPropertyInt("Generator.NrHours", 20);
081            int nrSlots = nrDays * nrHours;
082            TimetableModel m = new TimetableModel(nrDays, nrHours);
083    
084            int nrRooms = cfg.getPropertyInt("Generator.NrRooms", 20);
085            int nrInstructors = cfg.getPropertyInt("Generator.NrInstructors", 20);
086            int nrClasses = cfg.getPropertyInt("Generator.NrClasses", 20);
087            int nrGroupsOfRooms = cfg.getPropertyInt("Generator.NrGroupsOfRooms", 20);
088            int nrRoomsInGroupMin = cfg.getPropertyInt("Generator.NrRoomsInGroupMin", 1);
089            int nrRoomsInGroupMax = cfg.getPropertyInt("Generator.NrRoomsInGroupMax", 10);
090            int nrRoomInGroupMin = cfg.getPropertyInt("Generator.NrRoomInGroupMin", 1);
091            double fillFactor = cfg.getPropertyDouble("Generator.FillFactor", 0.8);
092            int maxLength = cfg.getPropertyInt("Generator.ActivityLengthMax", 5);
093            double hardFreeResource = cfg.getPropertyDouble("Generator.HardFreeResource", 0.05);
094            double softFreeResource = cfg.getPropertyDouble("Generator.SoftFreeResource", 0.3);
095            double softUsedResource = cfg.getPropertyDouble("Generator.SoftUsedResource", 0.05);
096            double softUsedActivity = cfg.getPropertyDouble("Generator.SoftUsedActivity", 0.05);
097            double softFreeActivity = cfg.getPropertyDouble("Generator.SoftFreeActivity", 0.3);
098            double hardFreeActivity = cfg.getPropertyDouble("Generator.HardFreeActivity", 0.05);
099            int nrDependencies = cfg.getPropertyInt("Generator.NrDependencies", 50);
100    
101            Resource rooms[] = new Resource[nrRooms];
102            ArrayList<ArrayList<Resource>> groupForRoom[] = new ArrayList[nrRooms];
103            for (int i = 0; i < nrRooms; i++) {
104                rooms[i] = new Resource("r" + (i + 1), Resource.TYPE_ROOM, "Room " + (i + 1));
105                groupForRoom[i] = new ArrayList<ArrayList<Resource>>();
106                m.addConstraint(rooms[i]);
107            }
108            ArrayList<Resource> groupOfRooms[] = new ArrayList[nrGroupsOfRooms];
109            for (int i = 0; i < nrGroupsOfRooms; i++) {
110                groupOfRooms[i] = new ArrayList<Resource>();
111                for (int j = 0; j < ToolBox.random(1 + nrRoomsInGroupMax - nrRoomsInGroupMin) + nrRoomsInGroupMin; j++) {
112                    int r = 0;
113                    do {
114                        r = ToolBox.random(nrRooms);
115                    } while (groupOfRooms[i].contains(rooms[r]));
116                    groupOfRooms[i].add(rooms[r]);
117                    groupForRoom[r].add(groupOfRooms[i]);
118                }
119            }
120            for (int i = 0; i < nrRooms; i++) {
121                int cnt = 0;
122                for (int j = 0; j < nrGroupsOfRooms; j++)
123                    if (groupOfRooms[j].contains(rooms[i]))
124                        cnt++;
125                while (cnt < nrRoomInGroupMin) {
126                    int r = 0;
127                    do {
128                        r = ToolBox.random(nrGroupsOfRooms);
129                    } while (groupOfRooms[r].contains(rooms[i]));
130                    groupOfRooms[r].add(rooms[i]);
131                    groupForRoom[i].add(groupOfRooms[r]);
132                    cnt++;
133                }
134            }
135            Resource instructors[] = new Resource[nrInstructors];
136            for (int i = 0; i < nrInstructors; i++) {
137                instructors[i] = new Resource("t" + (i + 1), Resource.TYPE_INSTRUCTOR, "Teacher " + (i + 1));
138                m.addConstraint(instructors[i]);
139            }
140            Resource classes[] = new Resource[nrClasses];
141            for (int i = 0; i < nrClasses; i++) {
142                classes[i] = new Resource("c" + (i + 1), Resource.TYPE_CLASS, "Class " + (i + 1));
143                m.addConstraint(classes[i]);
144            }
145    
146            int[][] timetable4room = new int[nrRooms][nrSlots];
147            int[][] timetable4instr = new int[nrInstructors][nrSlots];
148            int[][] timetable4class = new int[nrClasses][nrSlots];
149            int act = 0;
150            for (int i = 0; i < timetable4room.length; i++)
151                for (int j = 0; j < timetable4room[i].length; j++)
152                    timetable4room[i][j] = 0;
153            for (int i = 0; i < timetable4instr.length; i++)
154                for (int j = 0; j < timetable4instr[i].length; j++)
155                    timetable4instr[i][j] = 0;
156            for (int i = 0; i < timetable4class.length; i++)
157                for (int j = 0; j < timetable4class[i].length; j++)
158                    timetable4class[i][j] = 0;
159    
160            int totalSlots = nrRooms * nrSlots;
161            int usedSlots = 0;
162            ArrayList<Integer> starts = new ArrayList<Integer>();
163            ArrayList<Integer> arooms = new ArrayList<Integer>();
164            while ((((double) usedSlots / ((double) totalSlots))) < fillFactor) {
165                int attempt = 0;
166                int slot = ToolBox.random(nrSlots);
167                int room = ToolBox.random(nrRooms);
168                while (attempt < 500 && timetable4room[room][slot] != 0) {
169                    slot = ToolBox.random(nrSlots);
170                    room = ToolBox.random(nrRooms);
171                }
172                if (attempt == 500) {
173                    int s = slot;
174                    int r = room;
175                    while (timetable4room[r][s] != 0) {
176                        r++;
177                        if (r == nrRooms)
178                            r = 0;
179                        if (r == room)
180                            s++;
181                        if (s == nrSlots)
182                            s = 0;
183                    }
184                    slot = s;
185                    room = r;
186                }
187                int length = maxLength;// ToolBox.random(maxLength)+1;
188                int aclass = ToolBox.random(nrClasses);
189                int instr = ToolBox.random(nrInstructors);
190                attempt = 0;
191                while (attempt < 500 && (timetable4class[aclass][slot] != 0 || timetable4instr[instr][slot] != 0)) {
192                    aclass = ToolBox.random(nrClasses);
193                    instr = ToolBox.random(nrInstructors);
194                }
195                if (attempt == 500)
196                    continue;
197                int len = 1;
198                while (len < length) {
199                    if ((((slot + len) % nrHours) != 0) && timetable4room[room][slot + len] == 0
200                            && timetable4instr[instr][slot + len] == 0 && timetable4class[aclass][slot + len] == 0)
201                        len++;
202                    else
203                        break;
204                }
205                ArrayList<Resource> roomGr = ToolBox.random(groupForRoom[room]);
206                act++;
207                usedSlots += len;
208                Activity a = new Activity(len, "a" + act, "Activity " + act);
209                a.addResourceGroup(roomGr);
210                a.addResourceGroup(instructors[instr]);
211                a.addResourceGroup(classes[aclass]);
212                m.addVariable(a);
213                starts.add(slot);
214                arooms.add(room);
215                for (int i = slot; i < slot + len; i++) {
216                    timetable4room[room][i] = act;
217                    timetable4instr[instr][i] = act;
218                    timetable4class[aclass][i] = act;
219                }
220            }
221            int nrHardFreeRes = 0;
222            int nrSoftFreeRes = 0;
223            int nrSoftUsedRes = 0;
224            for (int slot = 0; slot < nrSlots; slot++) {
225                for (int room = 0; room < nrRooms; room++) {
226                    if (timetable4room[room][slot] == 0) {
227                        if (ToolBox.random() < hardFreeResource) {
228                            nrHardFreeRes++;
229                            rooms[room].addProhibitedSlot(slot);
230                        } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) {
231                            nrSoftFreeRes++;
232                            rooms[room].addDiscouragedSlot(slot);
233                        }
234                    } else if (ToolBox.random() < softUsedResource) {
235                        nrSoftUsedRes++;
236                        rooms[room].addDiscouragedSlot(slot);
237                    }
238                }
239                for (int instr = 0; instr < nrInstructors; instr++) {
240                    if (timetable4instr[instr][slot] == 0) {
241                        if (ToolBox.random() < hardFreeResource) {
242                            nrHardFreeRes++;
243                            instructors[instr].addProhibitedSlot(slot);
244                        } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) {
245                            nrSoftFreeRes++;
246                            instructors[instr].addDiscouragedSlot(slot);
247                        }
248                    } else if (ToolBox.random() < softUsedResource) {
249                        nrSoftUsedRes++;
250                        instructors[instr].addDiscouragedSlot(slot);
251                    }
252                }
253                for (int aclass = 0; aclass < nrClasses; aclass++) {
254                    if (timetable4class[aclass][slot] == 0) {
255                        if (ToolBox.random() < hardFreeResource) {
256                            nrHardFreeRes++;
257                            classes[aclass].addProhibitedSlot(slot);
258                        } else if (ToolBox.random() < softFreeResource / (1.0 - hardFreeResource)) {
259                            nrSoftFreeRes++;
260                            classes[aclass].addDiscouragedSlot(slot);
261                        }
262                    } else if (ToolBox.random() < softUsedResource) {
263                        nrSoftUsedRes++;
264                        classes[aclass].addDiscouragedSlot(slot);
265                    }
266                }
267            }
268            int nrSoftFreeAct = 0;
269            int nrSoftUsedAct = 0;
270            int nrHardFreeAct = 0;
271            for (int i = 0; i < m.variables().size(); i++) {
272                Activity activity = m.variables().get(i);
273                for (int slot = 0; slot < nrSlots; slot++) {
274                    int start = starts.get(i);
275                    if (slot < start || slot >= start + activity.getLength()) {
276                        if (ToolBox.random() < hardFreeActivity) {
277                            nrHardFreeAct++;
278                            activity.addProhibitedSlot(slot);
279                        } else if (ToolBox.random() < (softFreeActivity / (1.0 - hardFreeActivity))) {
280                            nrSoftFreeAct++;
281                            activity.addDiscouragedSlot(slot);
282                        }
283                    } else {
284                        if (ToolBox.random() < softUsedActivity) {
285                            nrSoftUsedAct++;
286                            activity.addDiscouragedSlot(slot);
287                        }
288                    }
289                }
290                activity.init();
291            }
292            for (int i = 0; i < nrDependencies;) {
293                int ac1 = ToolBox.random(m.variables().size());
294                int ac2 = ToolBox.random(m.variables().size());
295                while (ac1 == ac2) {
296                    ac2 = ToolBox.random(m.variables().size());
297                }
298                int s1 = starts.get(ac1);
299                int s2 = starts.get(ac2);
300                Activity a1 = m.variables().get(ac1);
301                Activity a2 = m.variables().get(ac2);
302                Dependence dep = null;
303                if (s1 < s2) {
304                    if (s1 + a1.getLength() == s2)
305                        dep = new Dependence("d" + (i + 1), Dependence.TYPE_CLOSELY_BEFORE);
306                    else if (s1 + a1.getLength() < s2)
307                        dep = new Dependence("d" + (i + 1), Dependence.TYPE_BEFORE);
308                } else {
309                    if (s2 == s1 + a1.getLength())
310                        dep = new Dependence("d" + (i + 1), Dependence.TYPE_CLOSELY_AFTER);
311                    else if (s2 > s1 + a1.getLength())
312                        dep = new Dependence("d" + (i + 1), Dependence.TYPE_AFTER);
313                }
314                if (dep != null) {
315                    dep.addVariable(a1);
316                    dep.addVariable(a2);
317                    m.addConstraint(dep);
318                    i++;
319                }
320            }
321            for (int i = 0; i < m.variables().size(); i++) {
322                Activity activity = m.variables().get(i);
323                // sLogger.debug("-- processing activity "+activity.getName());
324                int start = starts.get(i);
325                int room = arooms.get(i);
326                Location location = null;
327                for (Location l : activity.values()) {
328                    if (l.getSlot() == start && l.getResource(0).getResourceId().equals("r" + (room + 1))) {
329                        location = l;
330                        break;
331                    }
332                }
333                if (location != null) {
334                    Set<Location> conflicts = m.conflictValues(location);
335                    if (!conflicts.isEmpty()) {
336                        sLogger.warn("Unable to assign " + location.getName() + " to " + activity.getName() + ", reason:");
337                        for (Constraint<Activity, Location> c : activity.constraints()) {
338                            Set<Location> cc = new HashSet<Location>();
339                            c.computeConflicts(location, cc);
340                            if (!cc.isEmpty())
341                                sLogger.warn("  -- Constraint " + c.getName() + " causes conflicts " + cc);
342                        }
343                    } else {
344                        activity.assign(0, location);
345                        activity.setInitialAssignment(location);
346                    }
347                    // sLogger.debug("  -- location "+location.getName()+" found");
348                    activity.setInitialAssignment(location);
349                } else {
350                    sLogger.warn("Unable to assign " + activity.getName() + " -- no location matching slot=" + start
351                            + " room='R" + (room + 1) + "'");
352                }
353            }
354            if (!cfg.getPropertyBoolean("General.InitialAssignment", true)) {
355                for (int i = 0; i < m.variables().size(); i++) {
356                    Activity activity = m.variables().get(i);
357                    activity.unassign(0);
358                }
359            }
360    
361            int forcedPerturbances = cfg.getPropertyInt("General.ForcedPerturbances", 0);
362            if (forcedPerturbances > 0) {
363                List<Activity> initialVariables = new ArrayList<Activity>();
364                for (Activity v : m.variables()) {
365                    if (v.getInitialAssignment() != null)
366                        initialVariables.add(v);
367                }
368                for (int i = 0; i < forcedPerturbances; i++) {
369                    if (initialVariables.isEmpty())
370                        break;
371                    Activity var = ToolBox.random(initialVariables);
372                    initialVariables.remove(var);
373                    var.removeInitialValue();
374                }
375            }
376    
377            sLogger.debug("-- Generator Info ---------------------------------------------------------");
378            sLogger.debug("  Total number of " + m.variables().size() + " activities generated.");
379            sLogger.debug("  Total number of " + usedSlots + " slots are filled (" + ((100.0 * usedSlots) / totalSlots)
380                    + "% filled).");
381            sLogger.debug("  Average length of an activity is " + (((double) usedSlots) / m.variables().size()));
382            sLogger.debug("  Total number of hard constraints posted on free slots on activities: " + nrHardFreeAct);
383            sLogger.debug("  Total number of soft constraints posted on free slots on activities: " + nrSoftFreeAct);
384            sLogger.debug("  Total number of soft constraints posted on used slots on activities: " + nrSoftUsedAct);
385            sLogger.debug("  Total number of hard constraints posted on free slots on resources: " + nrHardFreeRes);
386            sLogger.debug("  Total number of soft constraints posted on free slots on resources: " + nrSoftFreeRes);
387            sLogger.debug("  Total number of soft constraints posted on used slots on resources: " + nrSoftUsedRes);
388            sLogger.debug("  Total number of " + nrDependencies + " dependencies generated.");
389            sLogger.debug("---------------------------------------------------------------------------");
390    
391            return m;
392        }
393    
394        public static void main(String[] args) {
395            try {
396                // Configure logging
397                org.apache.log4j.BasicConfigurator.configure();
398                
399                // Load properties (take first argument as input file, containing key=value lines)
400                DataProperties properties = new DataProperties();
401                properties.load(new FileInputStream(args[0]));
402                
403                // Generate model
404                TimetableModel model = TimetableModel.generate(new DataProperties());
405                System.out.println(model.getInfo());
406                
407                // Save solution (take second argument as output file)
408                model.saveAsXML(properties, true, new Solution<Activity, Location>(model), new File(args[1]));
409            } catch (Exception e) {
410                e.printStackTrace();
411            }
412        }
413    
414        public void saveAsXML(DataProperties cfg, boolean gen, Solution<Activity, Location> solution, File outFile)
415                throws IOException {
416            outFile.getParentFile().mkdirs();
417            sLogger.debug("Writting XML data to:" + outFile);
418    
419            Document document = DocumentHelper.createDocument();
420            document.addComment("Interactive Timetabling - University Timetable Generator (version 2.0)");
421    
422            if (!assignedVariables().isEmpty()) {
423                StringBuffer comments = new StringBuffer("Solution Info:\n");
424                Map<String, String> solutionInfo = (solution == null ? getInfo() : solution.getInfo());
425                for (String key : new TreeSet<String>(solutionInfo.keySet())) {
426                    String value = solutionInfo.get(key);
427                    comments.append("    " + key + ": " + value + "\n");
428                }
429                document.addComment(comments.toString());
430            }
431    
432            Element root = document.addElement("Timetable");
433            if (gen) {
434                Element generator = root.addElement("Generator");
435                generator.addAttribute("version", "2.0");
436                generator.addElement("DaysPerWeek").setText(String.valueOf(iNrDays));
437                generator.addElement("SlotsPerDay").setText(String.valueOf(iNrHours));
438                generator.addElement("NrRooms").setText(cfg.getProperty("Generator.NrRooms", "20"));
439                generator.addElement("NrInstructors").setText(cfg.getProperty("Generator.NrInstructors", "20"));
440                generator.addElement("NrClasses").setText(cfg.getProperty("Generator.NrClasses", "20"));
441                generator.addElement("FillFactor").setText(cfg.getProperty("Generator.FillFactor", "0.8"));
442                generator.addElement("ActivityLengthMax").setText(cfg.getProperty("Generator.ActivityLengthMax", "5"));
443                generator.addElement("NrGroupsOfRooms").setText(cfg.getProperty("Generator.NrGroupsOfRooms", "20"));
444                generator.addElement("NrRoomsInGroupMin").setText(cfg.getProperty("Generator.NrRoomsInGroupMin", "1"));
445                generator.addElement("NrRoomsInGroupMax").setText(cfg.getProperty("Generator.NrRoomsInGroupMax", "10"));
446                generator.addElement("NrRoomInGroupMin").setText(cfg.getProperty("Generator.NrRoomInGroupMin", "1"));
447                generator.addElement("HardFreeResource").setText(cfg.getProperty("Generator.HardFreeResource", "0.05"));
448                generator.addElement("SoftFreeResource").setText(cfg.getProperty("Generator.SoftFreeResource", "0.3"));
449                generator.addElement("SoftUsedResource").setText(cfg.getProperty("Generator.SoftUsedResource", "0.05"));
450                generator.addElement("SoftUsedActivity").setText(cfg.getProperty("Generator.SoftUsedActivity", "0.05"));
451                generator.addElement("SoftFreeActivity").setText(cfg.getProperty("Generator.SoftFreeActivity", "0.3"));
452                generator.addElement("HardFreeActivity").setText(cfg.getProperty("Generator.HardFreeActivity", "0.05"));
453                generator.addElement("NrDependencies").setText(cfg.getProperty("Generator.NrDependencies", "50"));
454            }
455    
456            ArrayList<Resource> rooms = new ArrayList<Resource>();
457            ArrayList<Resource> classes = new ArrayList<Resource>();
458            ArrayList<Resource> instructors = new ArrayList<Resource>();
459            ArrayList<Resource> specials = new ArrayList<Resource>();
460            ArrayList<Dependence> dependencies = new ArrayList<Dependence>();
461    
462            for (Constraint<Activity, Location> c : constraints()) {
463                if (c instanceof Resource) {
464                    Resource r = (Resource) c;
465                    switch (r.getType()) {
466                        case Resource.TYPE_ROOM:
467                            rooms.add(r);
468                            break;
469                        case Resource.TYPE_CLASS:
470                            classes.add(r);
471                            break;
472                        case Resource.TYPE_INSTRUCTOR:
473                            instructors.add(r);
474                            break;
475                        default:
476                            specials.add(r);
477                    }
478                } else if (c instanceof Dependence) {
479                    dependencies.add((Dependence) c);
480                }
481            }
482    
483            Element problem = root.addElement("Problem");
484            problem.addAttribute("version", "2.0");
485            Element problemGen = problem.addElement("General");
486            problemGen.addElement("DaysPerWeek").setText(String.valueOf(iNrDays));
487            problemGen.addElement("SlotsPerDay").setText(String.valueOf(iNrHours));
488            Element resourceGen = problemGen.addElement("Resources");
489            resourceGen.addElement("Classrooms").setText(String.valueOf(rooms.size()));
490            resourceGen.addElement("Teachers").setText(String.valueOf(instructors.size()));
491            resourceGen.addElement("Classes").setText(String.valueOf(classes.size()));
492            resourceGen.addElement("Special").setText(String.valueOf(specials.size()));
493            problemGen.addElement("Activities").setText(String.valueOf(variables().size()));
494            problemGen.addElement("Dependences").setText(String.valueOf(dependencies.size()));
495    
496            Element resources = problem.addElement("Resources");
497    
498            Element resEl = resources.addElement("Classrooms");
499            for (Resource r : rooms) {
500                Element el = resEl.addElement("Resource");
501                el.addAttribute("id", r.getResourceId());
502                el.addElement("Name").setText(r.getName());
503                Element pref = el.addElement("TimePreferences");
504                for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
505                    pref.addElement("Soft").setText(slot.toString());
506                for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
507                    pref.addElement("Hard").setText(slot.toString());
508            }
509    
510            resEl = resources.addElement("Teachers");
511            for (Resource r : instructors) {
512                Element el = resEl.addElement("Resource");
513                el.addAttribute("id", r.getResourceId());
514                el.addElement("Name").setText(r.getName());
515                Element pref = el.addElement("TimePreferences");
516                for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
517                    pref.addElement("Soft").setText(slot.toString());
518                for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
519                    pref.addElement("Hard").setText(slot.toString());
520            }
521    
522            resEl = resources.addElement("Classes");
523            for (Resource r : classes) {
524                Element el = resEl.addElement("Resource");
525                el.addAttribute("id", r.getResourceId());
526                el.addElement("Name").setText(r.getName());
527                Element pref = el.addElement("TimePreferences");
528                for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
529                    pref.addElement("Soft").setText(slot.toString());
530                for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
531                    pref.addElement("Hard").setText(slot.toString());
532            }
533    
534            resEl = resources.addElement("Special");
535            for (Resource r : specials) {
536                Element el = resEl.addElement("Resource");
537                el.addAttribute("id", r.getResourceId());
538                el.addElement("Name").setText(r.getName());
539                Element pref = el.addElement("TimePreferences");
540                for (Integer slot : new TreeSet<Integer>(r.getDiscouragedSlots()))
541                    pref.addElement("Soft").setText(slot.toString());
542                for (Integer slot : new TreeSet<Integer>(r.getProhibitedSlots()))
543                    pref.addElement("Hard").setText(slot.toString());
544            }
545    
546            boolean hasSolution = false;
547            Element actEl = problem.addElement("Activities");
548            for (Activity a : variables()) {
549                Element el = actEl.addElement("Activity");
550                el.addAttribute("id", a.getActivityId());
551                el.addElement("Name").setText(a.getName());
552                el.addElement("Length").setText(String.valueOf(a.getLength()));
553                if (a.getAssignment() != null)
554                    hasSolution = true;
555                Element pref = el.addElement("TimePreferences");
556                for (Integer slot : new TreeSet<Integer>(a.getDiscouragedSlots()))
557                    pref.addElement("Soft").setText(slot.toString());
558                for (Integer slot : new TreeSet<Integer>(a.getProhibitedSlots()))
559                    pref.addElement("Hard").setText(slot.toString());
560                Element reqRes = el.addElement("RequiredResources");
561                for (List<Resource> gr : a.getResourceGroups()) {
562                    if (gr.size() == 1) {
563                        reqRes.addElement("Resource").setText(gr.get(0).getResourceId());
564                    } else {
565                        Element grEl = reqRes.addElement("Group").addAttribute("conjunctive", "no");
566                        for (Resource r : gr)
567                            grEl.addElement("Resource").setText(r.getResourceId());
568                    }
569                }
570            }
571    
572            Element depEl = problem.addElement("Dependences");
573            for (Dependence d : dependencies) {
574                Element el = depEl.addElement("Dependence");
575                el.addAttribute("id", d.getResourceId());
576                el.addElement("FirstActivity").setText((d.first()).getActivityId());
577                el.addElement("SecondActivity").setText((d.second()).getActivityId());
578                switch (d.getType()) {
579                    case Dependence.TYPE_AFTER:
580                        el.addElement("Operator").setText("After");
581                        break;
582                    case Dependence.TYPE_BEFORE:
583                        el.addElement("Operator").setText("Before");
584                        break;
585                    case Dependence.TYPE_CLOSELY_BEFORE:
586                        el.addElement("Operator").setText("Closely before");
587                        break;
588                    case Dependence.TYPE_CLOSELY_AFTER:
589                        el.addElement("Operator").setText("Closely after");
590                        break;
591                    case Dependence.TYPE_CONCURRENCY:
592                        el.addElement("Operator").setText("Concurrently");
593                        break;
594                    default:
595                        el.addElement("Operator").setText("Unknown");
596                }
597            }
598    
599            if (hasSolution) {
600                Element solutionEl = root.addElement("Solution");
601                solutionEl.addAttribute("version", "2.0");
602                for (Activity a : variables()) {
603                    Element el = solutionEl.addElement("Activity");
604                    el.addAttribute("id", a.getActivityId());
605                    if (a.getAssignment() != null) {
606                        Location location = a.getAssignment();
607                        el.addElement("StartTime").setText(String.valueOf(location.getSlot()));
608                        Element res = el.addElement("UsedResources");
609                        for (int i = 0; i < location.getResources().length; i++)
610                            res.addElement("Resource").setText(location.getResources()[i].getResourceId());
611                    }
612                }
613            }
614    
615            FileOutputStream fos = new FileOutputStream(outFile);
616            (new XMLWriter(fos, OutputFormat.createPrettyPrint())).write(document);
617            fos.flush();
618            fos.close();
619        }
620    
621        public static TimetableModel loadFromXML(File inFile, boolean assign) throws IOException, DocumentException {
622            Document document = (new SAXReader()).read(inFile);
623            Element root = document.getRootElement();
624            if (!"Timetable".equals(root.getName())) {
625                sLogger.error("Given XML file is not interactive timetabling problem.");
626                return null;
627            }
628    
629            Element problem = root.element("Problem");
630            Element problemGen = problem.element("General");
631            TimetableModel m = new TimetableModel(Integer.parseInt(problemGen.elementText("DaysPerWeek")), Integer
632                    .parseInt(problemGen.elementText("SlotsPerDay")));
633    
634            Element resources = problem.element("Resources");
635    
636            HashMap<String, Resource> resTab = new HashMap<String, Resource>();
637    
638            Element resEl = resources.element("Classrooms");
639            for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
640                Element el = (Element) i.next();
641                Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_ROOM, el.elementText("Name"));
642                Element pref = el.element("TimePreferences");
643                for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
644                    r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
645                for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
646                    r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
647                m.addConstraint(r);
648                resTab.put(r.getResourceId(), r);
649            }
650    
651            resEl = resources.element("Teachers");
652            for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
653                Element el = (Element) i.next();
654                Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_INSTRUCTOR, el.elementText("Name"));
655                Element pref = el.element("TimePreferences");
656                for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
657                    r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
658                for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
659                    r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
660                m.addConstraint(r);
661                resTab.put(r.getResourceId(), r);
662            }
663    
664            resEl = resources.element("Classes");
665            for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
666                Element el = (Element) i.next();
667                Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_CLASS, el.elementText("Name"));
668                Element pref = el.element("TimePreferences");
669                for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
670                    r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
671                for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
672                    r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
673                m.addConstraint(r);
674                resTab.put(r.getResourceId(), r);
675            }
676    
677            resEl = resources.element("Special");
678            for (Iterator<?> i = resEl.elementIterator("Resource"); i.hasNext();) {
679                Element el = (Element) i.next();
680                Resource r = new Resource(el.attributeValue("id"), Resource.TYPE_OTHER, el.elementText("Name"));
681                Element pref = el.element("TimePreferences");
682                for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
683                    r.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
684                for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
685                    r.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
686                m.addConstraint(r);
687                resTab.put(r.getResourceId(), r);
688            }
689    
690            Element actEl = problem.element("Activities");
691            HashMap<String, Activity> actTab = new HashMap<String, Activity>();
692            for (Iterator<?> i = actEl.elementIterator("Activity"); i.hasNext();) {
693                Element el = (Element) i.next();
694                Activity a = new Activity(Integer.parseInt(el.elementText("Length")), el.attributeValue("id"), el
695                        .elementText("Name"));
696                Element pref = el.element("TimePreferences");
697                for (Iterator<?> j = pref.elementIterator("Soft"); j.hasNext();)
698                    a.addDiscouragedSlot(Integer.parseInt(((Element) j.next()).getText()));
699                for (Iterator<?> j = pref.elementIterator("Hard"); j.hasNext();)
700                    a.addProhibitedSlot(Integer.parseInt(((Element) j.next()).getText()));
701                Element req = el.element("RequiredResources");
702                for (Iterator<?> j = req.elementIterator(); j.hasNext();) {
703                    Element rqEl = (Element) j.next();
704                    if ("Resource".equals(rqEl.getName())) {
705                        a.addResourceGroup(resTab.get(rqEl.getText()));
706                    } else if ("Group".equals(rqEl.getName())) {
707                        if ("no".equalsIgnoreCase(rqEl.attributeValue("conjunctive"))
708                                || "false".equalsIgnoreCase(rqEl.attributeValue("conjunctive"))) {
709                            List<Resource> gr = new ArrayList<Resource>();
710                            for (Iterator<?> k = rqEl.elementIterator("Resource"); k.hasNext();)
711                                gr.add(resTab.get(((Element) k.next()).getText()));
712                            a.addResourceGroup(gr);
713                        } else {
714                            for (Iterator<?> k = rqEl.elementIterator("Resource"); k.hasNext();)
715                                a.addResourceGroup(resTab.get(((Element) k.next()).getText()));
716                        }
717                    }
718                }
719                m.addVariable(a);
720                a.init();
721                actTab.put(a.getActivityId(), a);
722            }
723    
724            Element depEl = problem.element("Dependences");
725            for (Iterator<?> i = depEl.elementIterator("Dependence"); i.hasNext();) {
726                Element el = (Element) i.next();
727                int type = Dependence.TYPE_NO_DEPENDENCE;
728                String typeStr = el.elementText("Operator");
729                if ("After".equals(typeStr))
730                    type = Dependence.TYPE_AFTER;
731                else if ("Before".equals(typeStr))
732                    type = Dependence.TYPE_BEFORE;
733                else if ("After".equals(typeStr))
734                    type = Dependence.TYPE_AFTER;
735                else if ("Closely before".equals(typeStr))
736                    type = Dependence.TYPE_CLOSELY_BEFORE;
737                else if ("Closely after".equals(typeStr))
738                    type = Dependence.TYPE_CLOSELY_AFTER;
739                else if ("Concurrently".equals(typeStr))
740                    type = Dependence.TYPE_CONCURRENCY;
741                Dependence d = new Dependence(el.attributeValue("id"), type);
742                d.addVariable(actTab.get(el.elementText("FirstActivity")));
743                d.addVariable(actTab.get(el.elementText("SecondActivity")));
744                m.addConstraint(d);
745            }
746    
747            Element solEl = root.element("Solution");
748            if (solEl != null) {
749                for (Iterator<?> i = solEl.elementIterator("Activity"); i.hasNext();) {
750                    Element el = (Element) i.next();
751                    Activity a = actTab.get(el.attributeValue("id"));
752                    if (a == null)
753                        continue;
754                    int slot = Integer.parseInt(el.elementText("StartTime"));
755                    Element usResEl = el.element("UsedResources");
756                    List<Resource> res = new ArrayList<Resource>();
757                    for (Iterator<?> j = usResEl.elementIterator("Resource"); j.hasNext();)
758                        res.add(resTab.get(((Element) j.next()).getText()));
759                    for (Location loc : a.values()) {
760                        if (loc.getSlot() != slot || loc.getResources().length != res.size())
761                            continue;
762                        boolean same = true;
763                        for (int j = 0; j < loc.getResources().length && same; j++)
764                            if (!res.get(j).equals(loc.getResources()[j]))
765                                same = false;
766                        if (!same)
767                            continue;
768                        a.setInitialAssignment(loc);
769                        if (assign)
770                            a.assign(0, loc);
771                        break;
772                    }
773                }
774            }
775            return m;
776        }
777    }