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