001    package net.sf.cpsolver.coursett.model;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.HashSet;
006    import java.util.HashMap;
007    import java.util.List;
008    import java.util.Locale;
009    import java.util.Map;
010    import java.util.Set;
011    
012    import net.sf.cpsolver.coursett.Constants;
013    import net.sf.cpsolver.coursett.constraint.ClassLimitConstraint;
014    import net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint;
015    import net.sf.cpsolver.coursett.constraint.GroupConstraint;
016    import net.sf.cpsolver.coursett.constraint.InstructorConstraint;
017    import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
018    import net.sf.cpsolver.coursett.constraint.RoomConstraint;
019    import net.sf.cpsolver.coursett.constraint.SpreadConstraint;
020    import net.sf.cpsolver.coursett.criteria.BackToBackInstructorPreferences;
021    import net.sf.cpsolver.coursett.criteria.BrokenTimePatterns;
022    import net.sf.cpsolver.coursett.criteria.DepartmentBalancingPenalty;
023    import net.sf.cpsolver.coursett.criteria.DistributionPreferences;
024    import net.sf.cpsolver.coursett.criteria.Perturbations;
025    import net.sf.cpsolver.coursett.criteria.RoomPreferences;
026    import net.sf.cpsolver.coursett.criteria.RoomViolations;
027    import net.sf.cpsolver.coursett.criteria.SameSubpartBalancingPenalty;
028    import net.sf.cpsolver.coursett.criteria.StudentCommittedConflict;
029    import net.sf.cpsolver.coursett.criteria.StudentConflict;
030    import net.sf.cpsolver.coursett.criteria.StudentDistanceConflict;
031    import net.sf.cpsolver.coursett.criteria.StudentHardConflict;
032    import net.sf.cpsolver.coursett.criteria.StudentOverlapConflict;
033    import net.sf.cpsolver.coursett.criteria.TimePreferences;
034    import net.sf.cpsolver.coursett.criteria.TimeViolations;
035    import net.sf.cpsolver.coursett.criteria.TooBigRooms;
036    import net.sf.cpsolver.coursett.criteria.UselessHalfHours;
037    import net.sf.cpsolver.coursett.criteria.placement.AssignmentCount;
038    import net.sf.cpsolver.coursett.criteria.placement.DeltaTimePreference;
039    import net.sf.cpsolver.coursett.criteria.placement.HardConflicts;
040    import net.sf.cpsolver.coursett.criteria.placement.PotentialHardConflicts;
041    import net.sf.cpsolver.coursett.criteria.placement.WeightedHardConflicts;
042    import net.sf.cpsolver.ifs.constant.ConstantModel;
043    import net.sf.cpsolver.ifs.criteria.Criterion;
044    import net.sf.cpsolver.ifs.model.Constraint;
045    import net.sf.cpsolver.ifs.util.DataProperties;
046    import net.sf.cpsolver.ifs.util.DistanceMetric;
047    
048    /**
049     * Timetable model.
050     * 
051     * @version CourseTT 1.2 (University Course Timetabling)<br>
052     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
053     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
054     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
055     * <br>
056     *          This library is free software; you can redistribute it and/or modify
057     *          it under the terms of the GNU Lesser General Public License as
058     *          published by the Free Software Foundation; either version 3 of the
059     *          License, or (at your option) any later version. <br>
060     * <br>
061     *          This library is distributed in the hope that it will be useful, but
062     *          WITHOUT ANY WARRANTY; without even the implied warranty of
063     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
064     *          Lesser General Public License for more details. <br>
065     * <br>
066     *          You should have received a copy of the GNU Lesser General Public
067     *          License along with this library; if not see
068     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
069     */
070    
071    public class TimetableModel extends ConstantModel<Lecture, Placement> {
072        private static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableModel.class);
073        private static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
074                new java.text.DecimalFormatSymbols(Locale.US));
075    
076        private List<InstructorConstraint> iInstructorConstraints = new ArrayList<InstructorConstraint>();
077        private List<JenrlConstraint> iJenrlConstraints = new ArrayList<JenrlConstraint>();
078        private List<RoomConstraint> iRoomConstraints = new ArrayList<RoomConstraint>();
079        private List<DepartmentSpreadConstraint> iDepartmentSpreadConstraints = new ArrayList<DepartmentSpreadConstraint>();
080        private List<SpreadConstraint> iSpreadConstraints = new ArrayList<SpreadConstraint>();
081        private List<GroupConstraint> iGroupConstraints = new ArrayList<GroupConstraint>();
082        private List<ClassLimitConstraint> iClassLimitConstraints = new ArrayList<ClassLimitConstraint>();
083        private DataProperties iProperties = null;
084        private int iYear = -1;
085    
086        private HashSet<Student> iAllStudents = new HashSet<Student>();
087        
088        private DistanceMetric iDistanceMetric = null;
089    
090    
091        public TimetableModel(DataProperties properties) {
092            super();
093            iProperties = properties;
094            iDistanceMetric = new DistanceMetric(properties);
095            if (properties.getPropertyBoolean("OnFlySectioning.Enabled", false))
096                addModelListener(new OnFlySectioning(this));
097            String criteria = properties.getProperty("General.Criteria",
098                    // Objectives
099                    StudentConflict.class.getName() + ";" +
100                    StudentDistanceConflict.class.getName() + ";" +
101                    StudentHardConflict.class.getName() + ";" +
102                    StudentCommittedConflict.class.getName() + ";" +
103                    StudentOverlapConflict.class.getName() + ";" +
104                    UselessHalfHours.class.getName() + ";" +
105                    BrokenTimePatterns.class.getName() + ";" +
106                    TooBigRooms.class.getName() + ";" +
107                    TimePreferences.class.getName() + ";" +
108                    RoomPreferences.class.getName() + ";" +
109                    DistributionPreferences.class.getName() + ";" +
110                    SameSubpartBalancingPenalty.class.getName() + ";" +
111                    DepartmentBalancingPenalty.class.getName() + ";" +
112                    BackToBackInstructorPreferences.class.getName() + ";" +
113                    Perturbations.class.getName() + ";" +
114                    // Additional placement selection criteria
115                    AssignmentCount.class.getName() + ";" +
116                    DeltaTimePreference.class.getName() + ";" +
117                    HardConflicts.class.getName() + ";" +
118                    PotentialHardConflicts.class.getName() + ";" +
119                    WeightedHardConflicts.class.getName());
120            // Interactive mode -- count time / room violations
121            if (properties.getPropertyBoolean("General.InteractiveMode", false))
122                criteria += ";" + TimeViolations.class.getName() + ";" + RoomViolations.class.getName();
123            // Additional (custom) criteria
124            criteria += ";" + properties.getProperty("General.AdditionalCriteria", "");
125            for (String criterion: criteria.split("\\;")) {
126                if (criterion == null || criterion.isEmpty()) continue;
127                try {
128                    @SuppressWarnings("unchecked")
129                    Class<Criterion<Lecture, Placement>> clazz = (Class<Criterion<Lecture, Placement>>)Class.forName(criterion);
130                    addCriterion(clazz.newInstance());
131                } catch (Exception e) {
132                    sLogger.error("Unable to use " + criterion + ": " + e.getMessage());
133                }
134            }
135        }
136    
137        public DistanceMetric getDistanceMetric() {
138            return iDistanceMetric;
139        }
140    
141        public DataProperties getProperties() {
142            return iProperties;
143        }
144    
145        /**
146         * Student final sectioning (switching students between sections of the same
147         * class in order to minimize overall number of student conflicts)
148         */
149        public void switchStudents() {
150            FinalSectioning sect = new FinalSectioning(this);
151            sect.run();
152        }
153    
154        @Override
155        public String toString() {
156            return "TimetableModel{" + "\n  super=" + super.toString()
157                    + "\n  studentConflicts=" + sDoubleFormat.format(getCriterion(StudentConflict.class).getValue())
158                    + "\n  roomPreferences=" + sDoubleFormat.format(getCriterion(RoomPreferences.class).getValue())
159                    + "\n  timePreferences=" + sDoubleFormat.format(getCriterion(TimePreferences.class).getValue())
160                    + "\n  groupConstraintPreferences=" + sDoubleFormat.format(getCriterion(DistributionPreferences.class).getValue())
161                    + "\n}";
162        }
163    
164        public Map<String, String> getBounds() {
165            Map<String, String> ret = new HashMap<String, String>();
166            ret.put("Room preferences min", "" + getCriterion(RoomPreferences.class).getBounds()[0]);
167            ret.put("Room preferences max", "" + getCriterion(RoomPreferences.class).getBounds()[1]);
168            ret.put("Time preferences min", "" + getCriterion(TimePreferences.class).getBounds()[0]);
169            ret.put("Time preferences max", "" + getCriterion(TimePreferences.class).getBounds()[1]);
170            ret.put("Distribution preferences min", "" + getCriterion(DistributionPreferences.class).getBounds()[0]);
171            ret.put("Distribution preferences max", "" + getCriterion(DistributionPreferences.class).getBounds()[1]);
172            if (getProperties().getPropertyBoolean("General.UseDistanceConstraints", false)) {
173                ret.put("Back-to-back instructor preferences max", "" + getCriterion(BackToBackInstructorPreferences.class).getBounds()[1]);
174            }
175            ret.put("Too big rooms max", "" + getCriterion(TooBigRooms.class).getBounds()[0]);
176            ret.put("Useless half-hours", "" + getCriterion(UselessHalfHours.class).getBounds()[0]);
177            return ret;
178        }
179    
180        /** Global info */
181        @Override
182        public Map<String, String> getInfo() {
183            Map<String, String> ret = super.getInfo();
184            ret.put("Memory usage", getMem());
185            
186            Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class);
187            Criterion<Lecture, Placement> rv = getCriterion(RoomViolations.class);
188            ret.put("Room preferences", getPerc(rp.getValue(), rp.getBounds()[0], rp.getBounds()[1]) + "% (" + Math.round(rp.getValue()) + ")"
189                    + (rv != null && rv.getValue() >= 0.5 ? " [hard:" + Math.round(rv.getValue()) + "]" : ""));
190            
191            Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class);
192            Criterion<Lecture, Placement> tv = getCriterion(TimeViolations.class);
193            ret.put("Time preferences", getPerc(tp.getValue(), tp.getBounds()[0], tp.getBounds()[1]) + "% (" + sDoubleFormat.format(tp.getValue()) + ")"
194                    + (tv != null && tv.getValue() >= 0.5 ? " [hard:" + Math.round(tv.getValue()) + "]" : ""));
195    
196            Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class);
197            ret.put("Distribution preferences", getPerc(dp.getValue(), dp.getBounds()[0], dp.getBounds()[1]) + "% (" + sDoubleFormat.format(dp.getValue()) + ")");
198            
199            Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class);
200            Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class);
201            Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class);
202            Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class);
203            ret.put("Student conflicts", Math.round(scc.getValue() + sc.getValue()) +
204                    " [committed:" + Math.round(scc.getValue()) +
205                    ", distance:" + Math.round(sdc.getValue()) +
206                    ", hard:" + Math.round(shc.getValue()) + "]");
207            
208            if (!getSpreadConstraints().isEmpty()) {
209                Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class);
210                ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(), ip.getBounds()[0], ip.getBounds()[1]) + "% (" + Math.round(ip.getValue()) + ")");
211            }
212    
213            if (!getDepartmentSpreadConstraints().isEmpty()) {
214                Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class);
215                ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue()));
216            }
217            
218            Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class);
219            ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue()));
220            
221            Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class);
222            ret.put("Too big rooms", getPercRev(tbr.getValue(), tbr.getBounds()[1], tbr.getBounds()[0]) + "% (" + Math.round(tbr.getValue()) + ")");
223            
224            Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class);
225            Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class);
226    
227            ret.put("Useless half-hours", getPercRev(uh.getValue() + bt.getValue(), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds()[0]) +
228                    "% (" + Math.round(uh.getValue()) + " + " + Math.round(bt.getValue()) + ")");
229            return ret;
230        }
231    
232        @Override
233        public Map<String, String> getInfo(Collection<Lecture> variables) {
234            Map<String, String> ret = super.getInfo(variables);
235            
236            ret.put("Memory usage", getMem());
237            
238            Criterion<Lecture, Placement> rp = getCriterion(RoomPreferences.class);
239            ret.put("Room preferences", getPerc(rp.getValue(variables), rp.getBounds(variables)[0], rp.getBounds(variables)[1]) + "% (" + Math.round(rp.getValue(variables)) + ")");
240            
241            Criterion<Lecture, Placement> tp = getCriterion(TimePreferences.class);
242            ret.put("Time preferences", getPerc(tp.getValue(variables), tp.getBounds(variables)[0], tp.getBounds(variables)[1]) + "% (" + sDoubleFormat.format(tp.getValue(variables)) + ")"); 
243    
244            Criterion<Lecture, Placement> dp = getCriterion(DistributionPreferences.class);
245            ret.put("Distribution preferences", getPerc(dp.getValue(variables), dp.getBounds(variables)[0], dp.getBounds(variables)[1]) + "% (" + sDoubleFormat.format(dp.getValue(variables)) + ")");
246            
247            Criterion<Lecture, Placement> sc = getCriterion(StudentConflict.class);
248            Criterion<Lecture, Placement> shc = getCriterion(StudentHardConflict.class);
249            Criterion<Lecture, Placement> sdc = getCriterion(StudentDistanceConflict.class);
250            Criterion<Lecture, Placement> scc = getCriterion(StudentCommittedConflict.class);
251            ret.put("Student conflicts", Math.round(scc.getValue(variables) + sc.getValue(variables)) +
252                    " [committed:" + Math.round(scc.getValue(variables)) +
253                    ", distance:" + Math.round(sdc.getValue(variables)) +
254                    ", hard:" + Math.round(shc.getValue(variables)) + "]");
255            
256            if (!getSpreadConstraints().isEmpty()) {
257                Criterion<Lecture, Placement> ip = getCriterion(BackToBackInstructorPreferences.class);
258                ret.put("Back-to-back instructor preferences", getPerc(ip.getValue(variables), ip.getBounds(variables)[0], ip.getBounds(variables)[1]) + "% (" + Math.round(ip.getValue(variables)) + ")");
259            }
260    
261            if (!getDepartmentSpreadConstraints().isEmpty()) {
262                Criterion<Lecture, Placement> dbp = getCriterion(DepartmentBalancingPenalty.class);
263                ret.put("Department balancing penalty", sDoubleFormat.format(dbp.getValue(variables)));
264            }
265            
266            Criterion<Lecture, Placement> sbp = getCriterion(SameSubpartBalancingPenalty.class);
267            ret.put("Same subpart balancing penalty", sDoubleFormat.format(sbp.getValue(variables)));
268            
269            Criterion<Lecture, Placement> tbr = getCriterion(TooBigRooms.class);
270            ret.put("Too big rooms", getPercRev(tbr.getValue(variables), tbr.getBounds(variables)[1], tbr.getBounds(variables)[0]) + "% (" + Math.round(tbr.getValue(variables)) + ")");
271            
272            Criterion<Lecture, Placement> uh = getCriterion(UselessHalfHours.class);
273            Criterion<Lecture, Placement> bt = getCriterion(BrokenTimePatterns.class);
274    
275            ret.put("Useless half-hours", getPercRev(uh.getValue(variables) + bt.getValue(variables), 0, Constants.sPreferenceLevelStronglyDiscouraged * bt.getBounds(variables)[0]) +
276                    "% (" + Math.round(uh.getValue(variables)) + " + " + Math.round(bt.getValue(variables)) + ")");
277            return ret;
278        }
279    
280        @Override
281        public void addConstraint(Constraint<Lecture, Placement> constraint) {
282            super.addConstraint(constraint);
283            if (constraint instanceof InstructorConstraint) {
284                iInstructorConstraints.add((InstructorConstraint) constraint);
285            } else if (constraint instanceof JenrlConstraint) {
286                iJenrlConstraints.add((JenrlConstraint) constraint);
287            } else if (constraint instanceof RoomConstraint) {
288                iRoomConstraints.add((RoomConstraint) constraint);
289            } else if (constraint instanceof DepartmentSpreadConstraint) {
290                iDepartmentSpreadConstraints.add((DepartmentSpreadConstraint) constraint);
291            } else if (constraint instanceof SpreadConstraint) {
292                iSpreadConstraints.add((SpreadConstraint) constraint);
293            } else if (constraint instanceof ClassLimitConstraint) {
294                iClassLimitConstraints.add((ClassLimitConstraint) constraint);
295            } else if (constraint instanceof GroupConstraint) {
296                iGroupConstraints.add((GroupConstraint) constraint);
297            }
298        }
299    
300        @Override
301        public void removeConstraint(Constraint<Lecture, Placement> constraint) {
302            super.removeConstraint(constraint);
303            if (constraint instanceof InstructorConstraint) {
304                iInstructorConstraints.remove(constraint);
305            } else if (constraint instanceof JenrlConstraint) {
306                iJenrlConstraints.remove(constraint);
307            } else if (constraint instanceof RoomConstraint) {
308                iRoomConstraints.remove(constraint);
309            } else if (constraint instanceof DepartmentSpreadConstraint) {
310                iDepartmentSpreadConstraints.remove(constraint);
311            } else if (constraint instanceof SpreadConstraint) {
312                iSpreadConstraints.remove(constraint);
313            } else if (constraint instanceof ClassLimitConstraint) {
314                iClassLimitConstraints.remove(constraint);
315            } else if (constraint instanceof GroupConstraint) {
316                iGroupConstraints.remove(constraint);
317            }
318        }
319    
320        /** The list of all instructor constraints */
321        public List<InstructorConstraint> getInstructorConstraints() {
322            return iInstructorConstraints;
323        }
324    
325        /** The list of all group constraints */
326        public List<GroupConstraint> getGroupConstraints() {
327            return iGroupConstraints;
328        }
329    
330        /** The list of all jenrl constraints */
331        public List<JenrlConstraint> getJenrlConstraints() {
332            return iJenrlConstraints;
333        }
334    
335        /** The list of all room constraints */
336        public List<RoomConstraint> getRoomConstraints() {
337            return iRoomConstraints;
338        }
339    
340        /** The list of all departmental spread constraints */
341        public List<DepartmentSpreadConstraint> getDepartmentSpreadConstraints() {
342            return iDepartmentSpreadConstraints;
343        }
344    
345        public List<SpreadConstraint> getSpreadConstraints() {
346            return iSpreadConstraints;
347        }
348    
349        public List<ClassLimitConstraint> getClassLimitConstraints() {
350            return iClassLimitConstraints;
351        }
352        @Override
353        public double getTotalValue() {
354            double ret = 0;
355            for (Criterion<Lecture, Placement> criterion: getCriteria())
356                ret += criterion.getWeightedValue();
357            return ret;
358        }
359    
360        @Override
361        public double getTotalValue(Collection<Lecture> variables) {
362            double ret = 0;
363            for (Criterion<Lecture, Placement> criterion: getCriteria())
364                ret += criterion.getWeightedValue(variables);
365            return ret;
366        }
367    
368        public int getYear() {
369            return iYear;
370        }
371    
372        public void setYear(int year) {
373            iYear = year;
374        }
375    
376        public Set<Student> getAllStudents() {
377            return iAllStudents;
378        }
379    
380        public void addStudent(Student student) {
381            iAllStudents.add(student);
382        }
383    
384        public void removeStudent(Student student) {
385            iAllStudents.remove(student);
386        }
387    
388        /**
389         * Returns amount of allocated memory.
390         * 
391         * @return amount of allocated memory to be written in the log
392         */
393        public static synchronized String getMem() {
394            Runtime rt = Runtime.getRuntime();
395            return sDoubleFormat.format(((double) (rt.totalMemory() - rt.freeMemory())) / 1048576) + "M";
396        }
397    }