    001    package ttsolver.heuristics;
    002
    003    import ifs.solution.*;
    004    import ifs.util.*;
    005    import java.util.*;
    006    import ttsolver.*;
    007    import edu.purdue.smas.timetable.serverfwk.ParameterDefinition;
    008
    009    /**
    010     * Timetable (solution) comparator.
    011     * <br><br>
    012     * The quality of a solution is expressed as a weighted sum combining soft time and classroom preferences, satisfied soft
    013     * group constrains and the total number of student conflicts. This allows us to express the importance of different
    014     * types of soft constraints.
    015     * <br><br>
    016     * The solution comparator prefers a more complete solution (with a smaller number of unassigned variables) and a solution
    017     * with a smaller number of perturbations among solutions with the same number of unassigned variables. If both solutions
    018     * have the same number of unassigned variables and perturbations, the solution of better quality is selected.
    019     * <br><br>
    020     * Parameters:
    021     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    022     * <tr><td>Comparator.HardStudentConflictWeight</td><td>{@link Double}</td><td>Weight of hard student conflict (conflict between single-section classes)</td></tr>
    023     * <tr><td>Comparator.StudentConflictWeight</td><td>{@link Double}</td><td>Weight of student conflict</td></tr>
    024     * <tr><td>Comparator.TimePreferenceWeight</td><td>{@link Double}</td><td>Time preferences weight</td></tr>
    025     * <tr><td>Comparator.ContrPreferenceWeight</td><td>{@link Double}</td><td>Group constraint preferences weight</td></tr>
    026     * <tr><td>Comparator.RoomPreferenceWeight</td><td>{@link Double}</td><td>Room preferences weight</td></tr>
    027     * <tr><td>Comparator.UselessSlotWeight</td><td>{@link Double}</td><td>Useless slots weight</td></tr>
    028     * <tr><td>Comparator.TooBigRoomWeight</td><td>{@link Double}</td><td>Too big room weight</td></tr>
    029     * <tr><td>Comparator.DistanceInstructorPreferenceWeight</td><td>{@link Double}</td><td>Distance (of the rooms of the back-to-back classes) based instructor preferences weight</td></tr>
    030     * <tr><td>Comparator.PerturbationPenaltyWeight</td><td>{@link Double}</td><td>Perturbation penalty (see {@link UniversalPerturbationsCounter})</td></tr>
    031     * <tr><td>Comparator.DeptSpreadPenaltyWeight</td><td>{@link Double}</td><td>Department balancing penalty (see {@link ttsolver.constraint.DepartmentSpreadConstraint})</td></tr>
    032     * </table>
    033     *
    034     *
    035     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    036     * @version 1.0
    037     */
    038
    039    public class TimetableComparator implements SolutionComparator {
    040        protected static org.apache.log4j.Logger sLogger = org.apache.log4j.Logger.getLogger(TimetableComparator.class);
    041
    042        private double iEmptySingleSlotWeight;
    043        public static final String USELESS_SLOT_WEIGHT="Comparator.UselessSlotWeight";
    044        private double iTimePreferencesWeight;
    045        public static final String TIME_PREFERENCE_WEIGHT="Comparator.TimePreferenceWeight";
    046        private double iStudentConflictWeight;
    047        public static final String STUDENT_CONFLICT_WEIGHT="Comparator.StudentConflictWeight";
    048        private double iRoomPreferencesWeight;
    049        public static final String ROOM_PREFERENCE_WEIGHT="Comparator.RoomPreferenceWeight";
    050        private double iConstrPreferencesWeight;
    051        public static final String CONSTR_PREFERENCE_WEIGHT="Comparator.ContrPreferenceWeight";
    052        private double iHardStudentConflictWeight;
    053        public static final String HARD_STUDENT_CONFLICT_WEIGHT="Comparator.HardStudentConflictWeight";
    054        private double iTooBigRoomWeight;
    055        public static final String TOO_BIG_ROOM_WEIGHT = "Comparator.TooBigRoomWeight";
    056        private boolean iCompareMpp;
    057        public static final String DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT = "Comparator.DistanceInstructorPreferenceWeight";
    058        private double iDistanceInstructorPreferenceWeight;
    059        public static final String PERTURBATION_PENALTY_WEIGHT = "Comparator.PerturbationPenaltyWeight";
    060        private double iPerturbationPenaltyWeight;
    061        public static final String DEPT_SPREAD_PENALTY_WEIGHT = "Comparator.DeptSpreadPenaltyWeight";
    062        private double iDeptSpreadPenaltyWeight;
    063
    064        public static Collection parameters() {
    065            Vector ret = new FastVector();
    066
    067            ParameterDefinition.Dependency swDep = new ParameterDefinition.Dependency("General.SwitchStudents","true");
    068            ParameterDefinition.Dependency deptSpreadDep = new ParameterDefinition.Dependency("General.UseDepartmentSpreadConstraints","false");
    069
    070            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",USELESS_SLOT_WEIGHT, "Useless slots", ParameterDefinition.TYPE_DOUBLE, "0.0"));
    071            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",TIME_PREFERENCE_WEIGHT, "Time preferences", ParameterDefinition.TYPE_DOUBLE, "1.0"));
    072            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",ROOM_PREFERENCE_WEIGHT, "Room preferences", ParameterDefinition.TYPE_DOUBLE, "0.1"));
    073            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",STUDENT_CONFLICT_WEIGHT, "Student conflicts", ParameterDefinition.TYPE_DOUBLE, "0.2"));
    074            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",HARD_STUDENT_CONFLICT_WEIGHT, "Hard student conflicts", ParameterDefinition.TYPE_DOUBLE, "1.0").addDependency(swDep));
    075            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",CONSTR_PREFERENCE_WEIGHT, "Group constraint preferences", ParameterDefinition.TYPE_DOUBLE, "1.0"));
    076            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",TOO_BIG_ROOM_WEIGHT, "Too big rooms", ParameterDefinition.TYPE_DOUBLE, "0.0"));
    077            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT, "Distance instructor preferences", ParameterDefinition.TYPE_DOUBLE, "1.0"));
    078            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",PERTURBATION_PENALTY_WEIGHT, "Perturbation penalty", ParameterDefinition.TYPE_DOUBLE, "1.0"));
    079            ret.addElement(new ParameterDefinition("Solution Comparator - Weights",DEPT_SPREAD_PENALTY_WEIGHT, "Deparment balancing penalty", ParameterDefinition.TYPE_DOUBLE, "1.0").addDependency(deptSpreadDep));
    080
    081            return ret;
    082        }
    083
    084        public TimetableComparator(DataProperties properties) {
    085            iEmptySingleSlotWeight = properties.getPropertyDouble(USELESS_SLOT_WEIGHT,0.0);
    086            iTimePreferencesWeight = properties.getPropertyDouble(TIME_PREFERENCE_WEIGHT,1.0);
    087            iRoomPreferencesWeight = properties.getPropertyDouble(ROOM_PREFERENCE_WEIGHT,0.1);
    088            iConstrPreferencesWeight = properties.getPropertyDouble(CONSTR_PREFERENCE_WEIGHT,1.0);
    089            if (properties.getPropertyBoolean("General.SwitchStudents",true)) {
    090                iHardStudentConflictWeight = properties.getPropertyDouble(HARD_STUDENT_CONFLICT_WEIGHT,1.0);
    091                iStudentConflictWeight = properties.getPropertyDouble(STUDENT_CONFLICT_WEIGHT,0.2);
    092            } else {
    093                iHardStudentConflictWeight = 0.0;
    094                iStudentConflictWeight = properties.getPropertyDouble(STUDENT_CONFLICT_WEIGHT,1.0);
    095            }
    096            iDistanceInstructorPreferenceWeight = properties.getPropertyDouble(DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT, 1.0);
    097            iTooBigRoomWeight = properties.getPropertyDouble(TOO_BIG_ROOM_WEIGHT,0.0);
    098            iCompareMpp = properties.getPropertyBoolean("General.MPP", false);
    099            iPerturbationPenaltyWeight = properties.getPropertyDouble(PERTURBATION_PENALTY_WEIGHT,1.0);
    100            iDeptSpreadPenaltyWeight = properties.getPropertyDouble(DEPT_SPREAD_PENALTY_WEIGHT,1.0);
    101        }
    102
    103        public boolean isBetterThanBestSolution(Solution currentSolution) {
    104            if (currentSolution.getBestInfo()==null) return true;
    105            TimetableModel tm = (TimetableModel)currentSolution.getModel();
    106            int unassigned = tm.unassignedVariables().size();
    107            if (tm.getBestUnassignedVariables()!=unassigned)
    108                return tm.getBestUnassignedVariables()>unassigned;
    109
    110            int tooBigBest=0, tooBigCurr=0;
    111            if (iTooBigRoomWeight!=0.0) {
    112                tooBigBest = tm.bestTooBigRooms();
    113                tooBigCurr = tm.countTooBigRooms();
    114            }
    115            long uselessSlotsBest=0, uselessSlotsCur=0;
    116            if (iEmptySingleSlotWeight!=0.0) {
    117                uselessSlotsBest = tm.bestUselessSlots();
    118                uselessSlotsCur = tm.getUselessSlots();
    119            }
    120            long hardSCBest = 0, hardSCCurr = 0;
    121            if (iHardStudentConflictWeight!=0.0) {
    122                hardSCBest = tm.bestHardStudentConflicts();
    123                hardSCCurr = tm.getHardStudentConflicts();
    124            }
    125            double pertBest=0.0, pertCurr=0.0;
    126            if (iCompareMpp && iPerturbationPenaltyWeight!=0.0) {
    127                pertCurr = currentSolution.getPerturbationsCounter().getPerturbationPenalty(currentSolution);
    128                pertBest = currentSolution.getBestPerturbationsPenalty();
    129            }
    130            double deptSpreadBest=0.0, deptSpread=0.0;
    131            if (iDeptSpreadPenaltyWeight!=0.0) {
    132                deptSpread = tm.getDepartmentSpreadPenalty();
    133                deptSpreadBest = tm.bestDepartmentSpreadPenalty();
    134            }
    135
    136            double prefBest = (iEmptySingleSlotWeight*uselessSlotsBest)+
    137                           (iTimePreferencesWeight*tm.bestGlobalTimePreference())+
    138                           (iRoomPreferencesWeight*tm.bestGlobalRoomPreference())+
    139                           (iConstrPreferencesWeight*tm.bestGlobalGroupConstraintPreference())+
    140                           (iStudentConflictWeight*tm.bestViolatedStudentConflicts())+
    141                           (iHardStudentConflictWeight*hardSCBest)+
    142                           (iTooBigRoomWeight*tooBigBest)+
    143                           (iDistanceInstructorPreferenceWeight*tm.bestInstructorDistancePreference())+
    144                           (iPerturbationPenaltyWeight*pertBest)+
    145                           (iDeptSpreadPenaltyWeight*deptSpreadBest)
    146                           ;
    147            double prefCurr = (iEmptySingleSlotWeight*uselessSlotsCur)+
    148                           (iTimePreferencesWeight*tm.getGlobalTimePreference())+
    149                           (iRoomPreferencesWeight*tm.getGlobalRoomPreference())+
    150                           (iConstrPreferencesWeight*tm.getGlobalGroupConstraintPreference())+
    151                           (iStudentConflictWeight*tm.getViolatedStudentConflicts())+
    152                           (iHardStudentConflictWeight*hardSCCurr)+
    153                           (iTooBigRoomWeight*tooBigCurr)+
    154                           (iDistanceInstructorPreferenceWeight*tm.getInstructorDistancePreference())+
    155                           (iPerturbationPenaltyWeight*pertCurr)+
    156                           (iDeptSpreadPenaltyWeight*deptSpread)
    157                           ;
    158    /*
    159            if (currentSolution.getModel().unassignedVariables().isEmpty() && prefCurr>=prefBest) {
    160                sLogger.info("Complete but worse (cur="+prefCurr+" vs. best="+prefBest+") solution "+currentSolution.getInfo()+" was found.");
    161            }
    162     */
    163            return (prefCurr<prefBest);
    164        }
    165
    166    }