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