    001    package ttsolver.heuristics;
    002
    003    import ifs.extension.*;
    004    import ifs.heuristics.*;
    005    import ifs.model.*;
    006    import ifs.solution.*;
    007    import ifs.solver.*;
    008    import ifs.util.*;
    009    import ifs.perturbations.*;
    010
    011    import java.util.*;
    012
    013    import ttsolver.constraint.*;
    014    import ttsolver.model.*;
    015    import ttsolver.*;
    016    import edu.purdue.smas.timetable.serverfwk.ParameterDefinition;
    017
    018    /**
    019     * Placement (value) selection.
    020     * <br><br>
    021     * We have implemented a hierarchical handling of the value selection criteria (see {@link HeuristicSelector}).
    022     * <br><br>
    023     * The value selection heuristics also allow for random selection of a value with a given probability
    024     * (random walk, e.g., 2%) and, in the case of MPP, to select the initial value (if it exists) with a given probability (e.g., 70%).
    025     * <br><br>
    026     * Parameters (general):
    027     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    028     * <tr><td>Placement.RandomWalkProb</td><td>{@link Double}</td><td>Random walk probability</td></tr>
    029     * <tr><td>Placement.GoodSelectionProb</td><td>{@link Double}</td><td>Good value (not removed from domain) selection probability (MAC related)</td></tr>
    030     * <tr><td>Placement.TabuLength</td><td>{@link Integer}</td><td>Tabu-list length (-1 means do not use tabu-list)</td></tr>
    031     * <tr><td>Placement.MPP_InitialProb</td><td>{@link Double}</td><td>MPP initial selection probability </td></tr>
    032     * <tr><td>Placement.MPP_Limit</td><td>{@link Integer}</td><td>MPP: limit on the number of perturbations (-1 for no limit)</td></tr>
    033     * <tr><td>Placement.MPP_PenaltyLimit</td><td>{@link Double}</td><td>MPP: limit on the perturbations penalty (-1 for no limit)</td></tr>
    034     * </table>
    035     * <br>
    036     * Parameters (for each level of selection):
    037     * <table border='1'><tr><th>Parameter</th><th>Type</th><th>Comment</th></tr>
    038     * <tr><td>Placement.NrAssignmentsWeight1<br>Placement.NrAssignmentsWeight2<br>Placement.NrAssignmentsWeight3</td><td>{@link Double}</td><td>Number of previous assignments of the value weight</td></tr>
    039     * <tr><td>Placement.NrConflictsWeight1,2,3</td><td>{@link Double}</td><td>Number of conflicts weight</td></tr>
    040     * <tr><td>Placement.WeightedConflictsWeight1,2,3</td><td>{@link Double}</td><td>Weighted conflicts weight (Conflict-based Statistics related)</td></tr>
    041     * <tr><td>Placement.NrPotentialConflictsWeight1,2,3</td><td>{@link Double}</td><td>Number of potential conflicts weight (Conflict-based Statistics related)</td></tr>
    042     * <tr><td>Placement.MPP_DeltaInitialAssignmentWeight1,2,3</td><td>{@link Double}</td><td>Delta initial assigments weight (MPP, violated initials related)</td></tr>
    043     * <tr><td>Placement.NrHardStudConfsWeight1,2,3</td><td>{@link Double}</td><td>Hard student conflicts weight (student conflicts between single-section classes)</td></tr>
    044     * <tr><td>Placement.NrStudConfsWeight1,2,3</td><td>{@link Double}</td><td>Student conflicts weight</td></tr>
    045     * <tr><td>Placement.TimePreferenceWeight1,2,3</td><td>{@link Double}</td><td>Time preference weight</td></tr>
    046     * <tr><td>Placement.DeltaTimePreferenceWeight1,2,3</td><td>{@link Double}</td><td>Time preference delta weight (difference between before and after assignemnt of the value)</td></tr>
    047     * <tr><td>Placement.ConstrPreferenceWeight1,2,3</td><td>{@link Double}</td><td>Constraint preference weight</td></tr>
    048     * <tr><td>Placement.RoomPreferenceWeight1,2,3</td><td>{@link Double}</td><td>Room preference weight</td></tr>
    049     * <tr><td>Placement.UselessSlotsWeight1,2,3</td><td>{@link Double}</td><td>Useless slot weight</td></tr>
    050     * <tr><td>Placement.TooBigRoomWeight1,2,3</td><td>{@link Double}</td><td>Too big room weight</td></tr>
    051     * <tr><td>Placement.DistanceInstructorPreferenceWeight1,2,3</td><td>{@link Double}</td><td>Distance (of the rooms of the back-to-back classes) based instructor preferences weight</td></tr>
    052     * <tr><td>Placement.DeptSpreadPenaltyWeight1,2,3</td><td>{@link Double}</td><td>Department spreading: penalty of when a slot over initial allowance is used</td></tr>
    053     * <tr><td>Placement.ThresholdKoef1,2</td><td>{@link Double}</td><td>Threshold koeficient of the level</td></tr>
    054     * </table>
    055     *
    056     * @see PlacementSelection
    057     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    058     * @version 1.0
    059     */
    060
    061    public class PlacementSelection implements ValueSelection {
    062        static final int NR_LEVELS = 3;
    063        private static final double PRECISION = 1.0;
    064        private static final boolean USE_THRESHOLD = true;
    065        private boolean iUseThreshold = USE_THRESHOLD;
    066
    067        private double iGoodSelectionProb;
    068        public static final String GOOD_SELECTION_PROB = "Placement.GoodSelectionProb";
    069        private double iRandomWalkProb;
    070        public static final String RW_SELECTION_PROB = "Placement.RandomWalkProb";
    071        private double iInitialSelectionProb;
    072        public static final String INITIAL_SELECTION_PROB = "Placement.MPP_InitialProb";
    073        private int iMPPLimit;
    074        public static final String NR_MPP_LIMIT = "Placement.MPP_Limit";
    075        private double iMPPPenaltyLimit;
    076        public static final String NR_MPP_PENALTY_LIMIT = "Placement.MPP_PenaltyLimit";
    077
    078        private double[] iNrConflictsWeight = new double[NR_LEVELS];
    079        public static final String NR_CONFLICTS_WEIGHT = "Placement.NrConflictsWeight";
    080        private double[] iNrPotentialConflictsWeight = new double[NR_LEVELS];
    081        public static final String NR_POTENTIAL_CONFLICTS_WEIGHT = "Placement.NrPotentialConflictsWeight";
    082        private double[] iNrWeightedConflictsWeight = new double[NR_LEVELS];
    083        public static final String WEIGHTED_CONFLICTS_WEIGHT = "Placement.WeightedConflictsWeight";
    084        private double[] iDeltaTimePreferenceWeight = new double[NR_LEVELS];
    085        public static final String DELTA_TIME_PREFERENCE_WEIGHT = "Placement.DeltaTimePreferenceWeight";
    086        private double[] iPerturbationPenaltyWeight = new double[NR_LEVELS];
    087        public static final String DELTA_INITIAL_ASSIGNMENT_WEIGHT = "Placement.MPP_DeltaInitialAssignmentWeight";
    088        private double[] iNrStudentConflictsWeight = new double[NR_LEVELS];
    089        public static final String NR_STUDENT_CONF_WEIGHT = "Placement.NrStudConfsWeight";
    090        private double[] iNrHardStudentConflictsWeight = new double[NR_LEVELS];
    091        public static final String NR_HARD_STUDENT_CONF_WEIGHT = "Placement.NrHardStudConfsWeight";
    092        private double[] iUselessSlotsWeight = new double[NR_LEVELS];
    093        public static final String USELESS_SLOTS_WEIGHT = "Placement.UselessSlotsWeight";
    094        private double[] iSumConstrPreferencesWeight = new double[NR_LEVELS];
    095        public static final String SUM_CONSTR_PREFERENCE_WEIGHT = "Placement.ConstrPreferenceWeight";
    096        private double[] iSumRoomPreferencesWeight = new double[NR_LEVELS];
    097        public static final String SUM_ROOM_PREFERENCE_WEIGHT = "Placement.RoomPreferenceWeight";
    098        private double[] iSumTimePreferencesWeight = new double[NR_LEVELS];
    099        public static final String SUM_TIME_PREFERENCE_WEIGHT = "Placement.TimePreferenceWeight";
    100        private double[] iNrAssignmentsWeight = new double[NR_LEVELS];
    101        public static final String NR_ASSIGNMENTS_WEIGHT = "Placement.NrAssignmentsWeight";
    102        private double[] iThresholdKoef = new double[NR_LEVELS];
    103        public static final String NR_THRESHOLD_KOEF = "Placement.ThresholdKoef";
    104        private double[] iTooBigRoomWeight = new double[NR_LEVELS];
    105        public static final String TOO_BIG_ROOM_WEIGHT = "Placement.TooBigRoomWeight";
    106        private double[] iDeptSpreadWeight = new double[NR_LEVELS];
    107        public static final String DEPT_SPREAD_WEIGHT = "Placement.DeptSpreadPenaltyWeight";
    108        private double[] iDistanceInstructorPreferenceWeight = new double[NR_LEVELS];
    109        public static final String DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT = "Placement.DistanceInstructorPreferenceWeight";
    110
    111        private int       iTabuSize                  = 0;
    112        private ArrayList iTabu                      = null;
    113        private int       iTabuPos                   = 0;
    114        public static final String TABU_LENGTH       = "Placement.TabuLength";
    115
    116        private ConflictStatistics iStat = null;
    117        private MacPropagation iProp = null;
    118        private ViolatedInitials iViolatedInitials = null;
    119        private PerturbationsCounter iPerturbationsCounter = null;
    120
    121        private boolean iRW = false;
    122        private boolean iMPP = false;
    123        private boolean iSW = false;
    124
    125        public static Vector parameters() {
    126            Vector ret = new FastVector();
    127
    128            ParameterDefinition.Dependency mppDep = new ParameterDefinition.Dependency("General.MPP","true");
    129            //ParameterDefinition.Dependency rwDep = new ParameterDefinition.Dependency("General.RandomWalk","true");
    130            //ParameterDefinition.Dependency propDep = new ParameterDefinition.Dependency("General.MAC","true");
    131            ParameterDefinition.Dependency swDep = new ParameterDefinition.Dependency("General.SwitchStudents","true");
    132            ParameterDefinition.Dependency deptSpreadDep = new ParameterDefinition.Dependency("General.UseDepartmentSpreadConstraints","true");
    133            ParameterDefinition.Dependency autoconfigure = new ParameterDefinition.Dependency("Placement.AutoConfigure", "false");
    134            ParameterDefinition.Dependency useCBS = new ParameterDefinition.Dependency("ConflictStatistics.Enabled", "true");
    135            ParameterDefinition.Dependency notUseCBS = new ParameterDefinition.Dependency("ConflictStatistics.Enabled", "false");
    136
    137            ret.addElement(new ParameterDefinition("Placement Selection",RW_SELECTION_PROB, "Random-walk probability", ParameterDefinition.TYPE_DOUBLE, "0.00"));
    138            ret.addElement(new ParameterDefinition("Placement Selection",INITIAL_SELECTION_PROB, "Select initial probability", ParameterDefinition.TYPE_DOUBLE, "0.75").addDependency(mppDep));
    139            //ret.addElement(new ParameterDefinition("Placement Selection",GOOD_SELECTION_PROB,"Good placement selection probability", ParameterDefinition.TYPE_DOUBLE, "1.00").addDependency(propDep));
    140            ret.addElement(new ParameterDefinition("Placement Selection",NR_MPP_LIMIT, "Added perturbations limit", ParameterDefinition.TYPE_INTEGER, "-1").addDependency(mppDep));
    141            ret.addElement(new ParameterDefinition("Placement Selection",NR_MPP_PENALTY_LIMIT, "Perturbations penalty limit", ParameterDefinition.TYPE_DOUBLE, "-1.0").addDependency(mppDep));
    142            //ret.addElement(new ParameterDefinition("Placement Selection",TABU_LENGTH, "Tabu-list length", ParameterDefinition.TYPE_INTEGER, "-1"));
    143            ret.addElement(new ParameterDefinition("Placement Selection", "Placement.AutoConfigure", "Automatic configuration", ParameterDefinition.TYPE_BOOLEAN, "true"));
    144
    145            for (int level=0;level<NR_LEVELS;level++) {
    146                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), NR_CONFLICTS_WEIGHT+(level+1), "Hard conflicts", ParameterDefinition.TYPE_DOUBLE, (level==0?"1.0":"0.0")).addDependency(autoconfigure).addDependency(notUseCBS));
    147                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), WEIGHTED_CONFLICTS_WEIGHT+(level+1), "Weighted hard conflicts (CBS)", ParameterDefinition.TYPE_DOUBLE, (level==0?"1.0":"0.0")).addDependency(autoconfigure).addDependency(useCBS));
    148                //ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), NR_POTENTIAL_CONFLICTS_WEIGHT+(level+1), "Potential hard conflicts", ParameterDefinition.TYPE_DOUBLE, "0.0").addDependency(autoconfigure));
    149                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), DELTA_TIME_PREFERENCE_WEIGHT+(level+1), "Time preferences delta", ParameterDefinition.TYPE_DOUBLE, (level==0?"0.5":"0.0")).addDependency(autoconfigure));
    150                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), DELTA_INITIAL_ASSIGNMENT_WEIGHT+(level+1), "Perturbation penalty", ParameterDefinition.TYPE_DOUBLE, (level==0?"0.5":level==1?"1.0":"0.0")).addDependency(mppDep).addDependency(autoconfigure));
    151                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), NR_STUDENT_CONF_WEIGHT+(level+1), "Student conflicts", ParameterDefinition.TYPE_DOUBLE, (level==0?"0.1":level==1?"0.2":"0.0")).addDependency(autoconfigure));
    152                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), NR_HARD_STUDENT_CONF_WEIGHT+(level+1), "Hard student conflicts", ParameterDefinition.TYPE_DOUBLE, (level==0?"0.5":level==1?"1.0":"0.0")).addDependency(swDep).addDependency(autoconfigure));
    153                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), USELESS_SLOTS_WEIGHT+(level+1), "Useless slots", ParameterDefinition.TYPE_DOUBLE, "0.0").addDependency(autoconfigure));
    154                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), SUM_CONSTR_PREFERENCE_WEIGHT+(level+1), "Group constraint preferences", ParameterDefinition.TYPE_DOUBLE, (level==0?"0.0":level==1?"1.0":"0.0")).addDependency(autoconfigure));
    155                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), SUM_ROOM_PREFERENCE_WEIGHT+(level+1), "Room preferences", ParameterDefinition.TYPE_DOUBLE, (level==1?"0.1":"0.0")).addDependency(autoconfigure));
    156                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), SUM_TIME_PREFERENCE_WEIGHT+(level+1), "Time preferences", ParameterDefinition.TYPE_DOUBLE, (level==1?"1.0":"0.0")).addDependency(autoconfigure));
    157                //ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), NR_ASSIGNMENTS_WEIGHT+(level+1), "Number of assignments", ParameterDefinition.TYPE_DOUBLE, "0.0").addDependency(autoconfigure));
    158                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), TOO_BIG_ROOM_WEIGHT+(level+1), "Too big rooms", ParameterDefinition.TYPE_DOUBLE, "0.0").addDependency(autoconfigure));
    159                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), DEPT_SPREAD_WEIGHT+(level+1), "Deparment balancing penalty", ParameterDefinition.TYPE_DOUBLE, (level==0?"0.5":level==1?"1.0":"0.0")).addDependency(deptSpreadDep).addDependency(autoconfigure));
    160                ret.addElement(new ParameterDefinition("Placement Selection - Weights Level "+(level+1), DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT+(level+1), "Distance instructor preference", ParameterDefinition.TYPE_DOUBLE, (level==0?"0.5":level==1?"1.0":"0.0")).addDependency(autoconfigure));
    161                if (USE_THRESHOLD) ret.addElement(new ParameterDefinition("Placement Selection", NR_THRESHOLD_KOEF+(level+1), "Threshold koeficient for level "+(level+1), ParameterDefinition.TYPE_DOUBLE, (level==0?"0.1":"0.0")).addDependency(autoconfigure));
    162            }
    163
    164            return ret;
    165        }
    166
    167        public void init(Solver solver) {
    168            for (Enumeration i=solver.getExtensions().elements();i.hasMoreElements();) {
    169                Extension extension = (Extension)i.nextElement();
    170                if (extension instanceof ConflictStatistics)
    171                    iStat = (ConflictStatistics) extension;
    172                if (extension instanceof MacPropagation)
    173                    iProp = (MacPropagation)extension;
    174                if (extension instanceof ViolatedInitials)
    175                    iViolatedInitials = (ViolatedInitials)extension;
    176            }
    177            iPerturbationsCounter = solver.getPerturbationsCounter();
    178        }
    179
    180        public PlacementSelection(DataProperties properties) {
    181            iMPP                     = properties.getPropertyBoolean("General.MPP", false);
    182            iRW                      = properties.getPropertyBoolean("General.RandomWalk", true);
    183            iSW                      = properties.getPropertyBoolean("General.SwitchStudents",true);
    184            boolean autoconfigure = properties.getPropertyBoolean("Placement.AutoConfigure", false);
    185            iRandomWalkProb = (iRW?properties.getPropertyDouble(RW_SELECTION_PROB,0.00):0.0);
    186            iGoodSelectionProb = properties.getPropertyDouble(GOOD_SELECTION_PROB,1.00);
    187            iInitialSelectionProb = (iMPP?properties.getPropertyDouble(INITIAL_SELECTION_PROB, 0.75):0.0);
    188            iMPPLimit = (iMPP?properties.getPropertyInt(NR_MPP_LIMIT, -1):-1);
    189            iMPPPenaltyLimit = (iMPP?properties.getPropertyDouble(NR_MPP_PENALTY_LIMIT, -1.0):-1.0);
    190            iTabuSize = properties.getPropertyInt(TABU_LENGTH, -1);
    191            if (iTabuSize>0) iTabu=new ArrayList(iTabuSize);
    192            iUseThreshold = properties.getPropertyBoolean("Placement.UseThreshold", USE_THRESHOLD);
    193
    194            for (int level=0; level<NR_LEVELS; level++) {
    195                iNrConflictsWeight[level] = properties.getPropertyDouble(NR_CONFLICTS_WEIGHT+(level+1),(level==0?1.0:0.0));
    196                iNrPotentialConflictsWeight[level] = properties.getPropertyDouble(NR_POTENTIAL_CONFLICTS_WEIGHT+(level+1),0.0);
    197                iNrWeightedConflictsWeight[level] = properties.getPropertyDouble(WEIGHTED_CONFLICTS_WEIGHT+(level+1),(level==0?1.0:0.0));
    198                iDeltaTimePreferenceWeight[level] = properties.getPropertyDouble(DELTA_TIME_PREFERENCE_WEIGHT+(level+1), (level==0?0.5:0.0));
    199                iPerturbationPenaltyWeight[level] = (iMPP?properties.getPropertyDouble(DELTA_INITIAL_ASSIGNMENT_WEIGHT+(level+1), (level==0?0.5:level==1?1.0:0.0)):0.0);
    200                iNrStudentConflictsWeight[level] = properties.getPropertyDouble(NR_STUDENT_CONF_WEIGHT+(level+1),(level==0?0.1:(level==1?0.2:0.0)));
    201                iNrHardStudentConflictsWeight[level] = (iSW?properties.getPropertyDouble(NR_HARD_STUDENT_CONF_WEIGHT+(level+1),(level==0?0.5:level==1?1.0:0.0)):0.0);
    202                iUselessSlotsWeight[level] = properties.getPropertyDouble(USELESS_SLOTS_WEIGHT+(level+1), 0.0);
    203                iSumConstrPreferencesWeight[level] = properties.getPropertyDouble(SUM_CONSTR_PREFERENCE_WEIGHT+(level+1), (level==0?0.5:level==1?1.0:0.0));
    204                iSumRoomPreferencesWeight[level] = properties.getPropertyDouble(SUM_ROOM_PREFERENCE_WEIGHT+(level+1), (level==1?0.1:0.0));
    205                iSumTimePreferencesWeight[level] = properties.getPropertyDouble(SUM_TIME_PREFERENCE_WEIGHT+(level+1), (level==1?1.0:0.0));
    206                iNrAssignmentsWeight[level] = properties.getPropertyDouble(NR_ASSIGNMENTS_WEIGHT+(level+1), 0.0);
    207                iThresholdKoef[level] = (USE_THRESHOLD?properties.getPropertyDouble(NR_THRESHOLD_KOEF+(level+1), (level==0?0.1:0.0)):0.0);
    208                iTooBigRoomWeight[level] = properties.getPropertyDouble(TOO_BIG_ROOM_WEIGHT+(level+1), 0.0);
    209                iDeptSpreadWeight[level] = properties.getPropertyDouble(DEPT_SPREAD_WEIGHT+(level+1), (level==0?0.5:level==1?1.0:0.0));
    210                iDistanceInstructorPreferenceWeight[level] = properties.getPropertyDouble(DISTANCE_INSTRUCTOR_PREFERENCE_WEIGHT+(level+1), (level==0?0.1:level==1?1.0:0.0));
    211            }
    212
    213            if (autoconfigure) {
    214                iNrConflictsWeight[0] = 3.0;
    215                iNrPotentialConflictsWeight[0] = 0.0;
    216                iNrWeightedConflictsWeight[0] = 3.0;
    217                iDeltaTimePreferenceWeight[0] = properties.getPropertyDouble("Comparator.TimePreferenceWeight",1.0)/2.0;
    218                iNrAssignmentsWeight[0] = 0.0;
    219                iThresholdKoef[0] = 0.1;
    220
    221                iNrStudentConflictsWeight[0] = properties.getPropertyDouble("Comparator.StudentConflictWeight",0.2);
    222                iNrHardStudentConflictsWeight[0] = properties.getPropertyDouble("Comparator.HardStudentConflictWeight",1.0);
    223                iUselessSlotsWeight[0] = properties.getPropertyDouble("Comparator.UselessSlotWeight",0.0);
    224                iSumConstrPreferencesWeight[0] = properties.getPropertyDouble("Comparator.ContrPreferenceWeight",1.0);
    225                iSumRoomPreferencesWeight[0] = properties.getPropertyDouble("Comparator.RoomPreferenceWeight",0.1);
    226                iSumTimePreferencesWeight[0] = properties.getPropertyDouble("Comparator.TimePreferenceWeight",1.0);
    227                iTooBigRoomWeight[0] = properties.getPropertyDouble("Comparator.TooBigRoomWeight",0.0);
    228                iDeptSpreadWeight[0] = properties.getPropertyDouble("Comparator.DeptSpreadPenaltyWeight",1.0);
    229                iDistanceInstructorPreferenceWeight[0] = properties.getPropertyDouble("Comparator.DistanceInstructorPreferenceWeight",1.0);
    230                iPerturbationPenaltyWeight[0] = (iMPP?properties.getPropertyDouble("Comparator.PerturbationPenaltyWeight",1.0):0.0);
    231
    232                iNrConflictsWeight[1] = 0.0;
    233                iNrPotentialConflictsWeight[1] = 0.0;
    234                iNrWeightedConflictsWeight[1] = 0.0;
    235                iDeltaTimePreferenceWeight[1] = 0.0;
    236                iNrAssignmentsWeight[1] = 0.0;
    237                iThresholdKoef[1] = 0.0;
    238
    239                iNrStudentConflictsWeight[1] = properties.getPropertyDouble("Comparator.StudentConflictWeight",0.2);
    240                iNrHardStudentConflictsWeight[1] = properties.getPropertyDouble("Comparator.HardStudentConflictWeight",1.0);
    241                iUselessSlotsWeight[1] = properties.getPropertyDouble("Comparator.UselessSlotWeight",0.0);
    242                iSumConstrPreferencesWeight[1] = properties.getPropertyDouble("Comparator.ContrPreferenceWeight",1.0);
    243                iSumRoomPreferencesWeight[1] = properties.getPropertyDouble("Comparator.RoomPreferenceWeight",0.1);
    244                iSumTimePreferencesWeight[1] = properties.getPropertyDouble("Comparator.TimePreferenceWeight",1.0);
    245                iTooBigRoomWeight[1] = properties.getPropertyDouble("Comparator.TooBigRoomWeight",0.0);
    246                iDeptSpreadWeight[1] = properties.getPropertyDouble("Comparator.DeptSpreadPenaltyWeight",1.0);
    247                iDistanceInstructorPreferenceWeight[1] = properties.getPropertyDouble("Comparator.DistanceInstructorPreferenceWeight",1.0);
    248                iPerturbationPenaltyWeight[1] = (iMPP?properties.getPropertyDouble("Comparator.PerturbationPenaltyWeight",1.0):0.0);
    249
    250                iNrConflictsWeight[2] = 0.0;
    251                iNrPotentialConflictsWeight[2] = 0.0;
    252                iNrWeightedConflictsWeight[2] = 0.0;
    253                iDeltaTimePreferenceWeight[2] = 0.0;
    254                iPerturbationPenaltyWeight[2] = 0.0;
    255                iNrStudentConflictsWeight[2] = 0.0;
    256                iNrHardStudentConflictsWeight[2] = 0.0;
    257                iUselessSlotsWeight[2] = 0.0;
    258                iSumConstrPreferencesWeight[2] = 0.0;
    259                iSumRoomPreferencesWeight[2] = 0.0;
    260                iSumTimePreferencesWeight[2] = 0.0;
    261                iNrAssignmentsWeight[2] = 0.0;
    262                iThresholdKoef[2] = 0.0;
    263                iTooBigRoomWeight[2] = 0.0;
    264                iDeptSpreadWeight[2] = 0.0;
    265                iDistanceInstructorPreferenceWeight[2] = 0.0;
    266            }
    267        }
    268
    269        public Value selectValue(Solution solution, Variable selectedVariable) {
    270            /*if (iMPPLimit>=0 && solution.getModel().unassignedVariables().isEmpty() && iMPPLimit>solution.getModel().perturbVariables().size()) {
    271                ToolBox.print("A complete solution with "+solution.getModel().perturbVariables().size()+" perturbances found");
    272                iMPPLimit = solution.getModel().perturbVariables().size()-1;
    273                ToolBox.print("MPP limit decreased to "+iMPPLimit);
    274            }*/
    275            if (selectedVariable.getInitialAssignment()!=null) {
    276                if (iMPPLimit>=0 && solution.getModel().perturbVariables().size()>=iMPPLimit) return checkValue(selectedVariable.getInitialAssignment());
    277                if (iMPPPenaltyLimit>=0.0 && solution.getPerturbationsCounter()!=null && solution.getPerturbationsCounter().getPerturbationPenalty(solution)>iMPPPenaltyLimit) return checkValue(selectedVariable.getInitialAssignment());
    278                if (selectedVariable.getInitialAssignment()!=null && ToolBox.random()<=iInitialSelectionProb) return checkValue(selectedVariable.getInitialAssignment());
    279            }
    280
    281            Vector values = selectedVariable.values();
    282            if (iRW && ToolBox.random()<=iRandomWalkProb) return checkValue((Value)ToolBox.random(values));
    283            if (iProp!=null && selectedVariable.getAssignment()==null && ToolBox.random()<=iGoodSelectionProb) {
    284                Collection goodValues = iProp.goodValues(selectedVariable);
    285                if (!goodValues.isEmpty()) values=new FastVector(goodValues);
    286            }
    287            if (values.size()==1) return checkValue((Value)values.firstElement());
    288
    289            long[] bestCost = new long[NR_LEVELS];
    290            Vector selectionValues = null;
    291
    292
    293            HeuristicSelector selector = (iUseThreshold?new HeuristicSelector(iThresholdKoef):null);
    294            for (Enumeration i1=values.elements();i1.hasMoreElements();) {
    295                Value value = (Value) i1.nextElement();
    296                if (iTabu!=null && iTabu.contains(value)) continue;
    297                if (selectedVariable.getAssignment()!=null && selectedVariable.getAssignment().equals(value)) continue;
    298                ParamRetriever paramRetriever = new ParamRetriever(solution, (Lecture)selectedVariable, (Placement)value);
    299
    300                if (iUseThreshold) {
    301                    double[] costs = new double[NR_LEVELS];
    302                    for (int level=0;level<NR_LEVELS;level++) {
    303                        double cost =
    304                        (iNrConflictsWeight[level]==0.0?0.0:iNrConflictsWeight[level]*paramRetriever.nrContlicts())+
    305                        (iNrWeightedConflictsWeight[level]==0.0?0.0:iNrWeightedConflictsWeight[level]*paramRetriever.weightedConflicts())+
    306                        (iNrPotentialConflictsWeight[level]==0.0?0.0:iNrPotentialConflictsWeight[level]*paramRetriever.potentialConflicts(3))+
    307                        (iDeltaTimePreferenceWeight[level]==0.0?0.0:iDeltaTimePreferenceWeight[level]*paramRetriever.deltaTimePreference())+
    308                        (iPerturbationPenaltyWeight[level]==0.0?0.0:iPerturbationPenaltyWeight[level]*paramRetriever.perturbationsPenalty())+
    309                        (iNrStudentConflictsWeight[level]==0.0?0.0:iNrStudentConflictsWeight[level]*paramRetriever.sumStudentConflicts())+
    310                        (iNrHardStudentConflictsWeight[level]==0.0?0.0:iNrHardStudentConflictsWeight[level]*paramRetriever.sumHardStudentConflicts())+
    311                        (iUselessSlotsWeight[level]==0.0?0.0:iUselessSlotsWeight[level]*paramRetriever.emptySingleHalfHours())+
    312                        (iSumConstrPreferencesWeight[level]==0.0?0.0:iSumConstrPreferencesWeight[level]*paramRetriever.constrPreference())+
    313                        (iSumRoomPreferencesWeight[level]==0.0?0.0:iSumRoomPreferencesWeight[level]*paramRetriever.roomPreference())+
    314                        (iSumTimePreferencesWeight[level]==0.0?0.0:iSumTimePreferencesWeight[level]*paramRetriever.timePreference())+
    315                        (iNrAssignmentsWeight[level]==0.0?0.0:iNrAssignmentsWeight[level]*paramRetriever.nrAssignments())+
    316                        (iTooBigRoomWeight[level]==0.0?0.0:paramRetriever.tooBig()?iTooBigRoomWeight[level]:0.0)+
    317                        (iDeptSpreadWeight[level]==0.0?0.0:iDeptSpreadWeight[level]*paramRetriever.deptSpread())+
    318                        (iDistanceInstructorPreferenceWeight[level]==0.0?0.0:iDistanceInstructorPreferenceWeight[level]*paramRetriever.distanceInstructorPreference())
    319                        ;
    320                        costs[level]=cost;
    321                    }
    322                    selector.add(costs, value);
    323                } else {
    324                    boolean fail = false;
    325                    boolean best = false;
    326                    for (int level=0;!fail && level<1;level++) {
    327                        long cost = Math.round( PRECISION * (
    328                        (iNrConflictsWeight[level]==0.0?0.0:iNrConflictsWeight[level]*paramRetriever.nrContlicts())+
    329                        (iNrWeightedConflictsWeight[level]==0.0?0.0:iNrWeightedConflictsWeight[level]*paramRetriever.weightedConflicts())+
    330                        (iNrPotentialConflictsWeight[level]==0.0?0.0:iNrPotentialConflictsWeight[level]*paramRetriever.potentialConflicts(0))+
    331                        (iDeltaTimePreferenceWeight[level]==0.0?0.0:iDeltaTimePreferenceWeight[level]*paramRetriever.deltaTimePreference())+
    332                        (iPerturbationPenaltyWeight[level]==0.0?0.0:iPerturbationPenaltyWeight[level]*paramRetriever.perturbationsPenalty())+
    333                        (iNrStudentConflictsWeight[level]==0.0?0.0:iNrStudentConflictsWeight[level]*paramRetriever.sumStudentConflicts())+
    334                        (iNrHardStudentConflictsWeight[level]==0.0?0.0:iNrHardStudentConflictsWeight[level]*paramRetriever.sumHardStudentConflicts())+
    335                        (iUselessSlotsWeight[level]==0.0?0.0:iUselessSlotsWeight[level]*paramRetriever.emptySingleHalfHours())+
    336                        (iSumConstrPreferencesWeight[level]==0.0?0.0:iSumConstrPreferencesWeight[level]*paramRetriever.constrPreference())+
    337                        (iSumRoomPreferencesWeight[level]==0.0?0.0:iSumRoomPreferencesWeight[level]*paramRetriever.roomPreference())+
    338                        (iSumTimePreferencesWeight[level]==0.0?0.0:iSumTimePreferencesWeight[level]*paramRetriever.timePreference())+
    339                        (iNrAssignmentsWeight[level]==0.0?0.0:iNrAssignmentsWeight[level]*paramRetriever.nrAssignments())+
    340                        (iTooBigRoomWeight[level]==0.0?0.0:paramRetriever.tooBig()?iTooBigRoomWeight[level]:0.0)+
    341                        (iDeptSpreadWeight[level]==0.0?0.0:iDeptSpreadWeight[level]*paramRetriever.deptSpread())+
    342                        (iDistanceInstructorPreferenceWeight[level]==0.0?0.0:iDistanceInstructorPreferenceWeight[level]*paramRetriever.distanceInstructorPreference())
    343    /*                    (iNrConflictsWeight[level]*conflicts)+
    344                        (iNrWeightedConflictsWeight[level]*weightedConflicts)+
    345                        (iDeltaTimePreferenceWeight[level]*deltaTimePreference)+
    346                        (iDeltaInitialAssignmentsWeight[level]*deltaInitialAssignments)+
    347                        (iNrStudentConflictsWeight[level]*sumStudentConflicts)+
    348                        (iNrHardStudentConflictsWeight[level]*sumHardStudentConflicts)+
    349                        (iUselessSlotsWeight[level]*emptySingleHalfHours)+
    350                        (iSumConstrPreferencesWeight[level]*constrPreference)+
    351                        (iSumRoomPreferencesWeight[level]*roomPreference)+
    352                        (iSumTimePreferencesWeight[level]*timePrefernce)+
    353                        (iNrAssignmentsWeight[level]*nrAssignments)*/
    354                        ));
    355                        if (selectionValues!=null && !best) {
    356                            if (cost>bestCost[level]) { fail=true; }
    357                            if (cost<bestCost[level]) { bestCost[level]=cost; selectionValues.clear(); best=true; }
    358                        } else {
    359                            bestCost[level]=cost;
    360                        }
    361                    }
    362                    if (selectionValues==null) selectionValues = new FastVector(values.size());
    363                    if (!fail) selectionValues.addElement(value);
    364                }
    365
    366            }
    367            //ToolBox.print("Best "+selectionValues.size()+" locations for variable "+selectedVariable.getId()+" have "+bestConflicts+" conflicts ("+bestRemovals+" weighted) and "+bestStudentConflicts+" ("+bestOriginalStudentConflicts+" * "+bestKoef+" + "+bestPenalty+") preference.");
    368            Value selectedValue = null;
    369            if (iUseThreshold) {
    370                selectionValues = selector.selection();
    371
    372                if (selectedVariable.getInitialAssignment()!=null) {
    373                    for (Enumeration e=selectionValues.elements();e.hasMoreElements();) {
    374                        Value value = (Value)((HeuristicSelector.Element) e.nextElement()).getObject();
    375                        if (value.equals(selectedVariable.getInitialAssignment())) {
    376                            selectedValue = value;
    377                            break;
    378                        }
    379                    }
    380                    //&& selectionValues.contains(selectedVariable.getInitialAssignment())) return selectedVariable.getInitialAssignment();
    381                }
    382
    383                if (selectedValue==null) {
    384                    HeuristicSelector.Element selection = (HeuristicSelector.Element)ToolBox.random(selectionValues);
    385                    selectedValue = (Value)(selection==null?null:selection.getObject());
    386                }
    387            } else {
    388                if (selectedVariable.getInitialAssignment()!=null && selectionValues.contains(selectedVariable.getInitialAssignment())) return checkValue(selectedVariable.getInitialAssignment());
    389                selectedValue = (Value)ToolBox.random(selectionValues);
    390            }
    391            if (selectedValue!=null && iTabu!=null) {
    392                if (iTabu.size()==iTabuPos)
    393                    iTabu.add(selectedValue);
    394                else
    395                    iTabu.set(iTabuPos, selectedValue);
    396                iTabuPos = (iTabuPos + 1) % iTabuSize;
    397            }
    398            return checkValue(selectedValue);
    399        }
    400
    401        private Value checkValue(Value aValue) {
    402            if (aValue==null) return null;
    403            DepartmentSpreadConstraint c = ((Lecture)aValue.variable()).getDeptSpreadConstraint();
    404            if (c!=null && c.inConflict(aValue)) c.incUnassignmentCounter(aValue);
    405            return aValue;
    406        }
    407
    408        private class ParamRetriever {
    409            private Lecture iLecture;
    410            private Placement iPlacement;
    411            private Solution iSolution;
    412            private ParamRetriever(Solution solution, Lecture lecture, Placement placement) {
    413                iSolution = solution;
    414                iLecture = lecture;
    415                iPlacement = placement;
    416            }
    417
    418            Collection iConf = null;
    419            private Collection conf() {
    420                if (iConf == null) iConf = iSolution.getModel().conflictValues(iPlacement);
    421                return iConf;
    422            }
    423
    424            public long nrContlicts() {
    425                return conf().size();
    426            }
    427
    428            private Double iWeightedConflicts = null;
    429            public double weightedConflicts() {
    430                if (iWeightedConflicts==null)
    431                    iWeightedConflicts = new Double(iStat==null?0.0:iStat.countRemovals(iSolution.getIteration(), conf(), iPlacement));
    432                return iWeightedConflicts.doubleValue();
    433            }
    434
    435            private Double iPotentialConflicts = null;
    436            public double potentialConflicts(int limit) {
    437                if (iPotentialConflicts==null)
    438                    iPotentialConflicts = new Double(iStat==null?0.0:iStat.countPotentialConflicts(iSolution.getIteration(),iPlacement, limit));
    439                return iPotentialConflicts.doubleValue();
    440            }
    441
    442            Double iDeltaTimePreference = null;
    443            public double deltaTimePreference() {
    444                if (iDeltaTimePreference==null) {
    445                    double deltaTimePreference = 0;
    446                    for (Iterator it1=conf().iterator(); it1.hasNext(); ) {
    447                        Placement placement = (Placement)it1.next();
    448                        double timePref = placement.getTimeLocation().getNormalizedPreference();
    449                        deltaTimePreference -= timePref - ((Lecture)placement.variable()).getBestTimePreference();
    450                    }
    451                    deltaTimePreference += iPlacement.getTimeLocation().getNormalizedPreference() - iLecture.getBestTimePreference();
    452                    iDeltaTimePreference = new Double(deltaTimePreference);
    453                }
    454                return iDeltaTimePreference.doubleValue();
    455            }
    456
    457            Double iPerturbationsPenalty = null;
    458            public double perturbationsPenalty() {
    459                if (iPerturbationsPenalty==null) {
    460                    iPerturbationsPenalty = new Double(iPerturbationsCounter.getPerturbationPenalty(iSolution,iPlacement,conf()));
    461                }
    462                return iPerturbationsPenalty.doubleValue();
    463            }
    464
    465            Integer iSumStudentConflicts = null;
    466            public int sumStudentConflicts() {
    467                if (iSumStudentConflicts==null)
    468                    iSumStudentConflicts = new Integer(iLecture.countStudentConflicts(iPlacement));
    469                return iSumStudentConflicts.intValue();
    470            }
    471
    472            Integer iConstrPreference = null;
    473            public int constrPreference() {
    474                if (iConstrPreference==null) {
    475                    int constrPreference = 0;
    476                    for (Enumeration i2=iLecture.softConstraints().elements();i2.hasMoreElements();) {
    477                        Constraint constraint = (Constraint)i2.nextElement();
    478                        if (constraint instanceof GroupConstraint) {
    479                            GroupConstraint gc = (GroupConstraint)constraint;
    480                            constrPreference += gc.getCurrentPreference(iPlacement);
    481                        }
    482                    }
    483                    iConstrPreference = new Integer(constrPreference);
    484                }
    485                return iConstrPreference.intValue();
    486            }
    487
    488            Integer iEmptySingleHalfHours = null;
    489            public int emptySingleHalfHours() {
    490                if (iEmptySingleHalfHours==null) {
    491                    int emptySingleHalfHours = 0;
    492                    for (Enumeration i2=iLecture.hardConstraints().elements();i2.hasMoreElements();) {
    493                        Constraint constraint = (Constraint)i2.nextElement();
    494                        if (constraint instanceof RoomConstraint) {
    495                            RoomConstraint rc = (RoomConstraint)constraint;
    496                            for (int i=0; i<iPlacement.getTimeLocation().getStartSlots().length; i++) {
    497                                int startSlot = iPlacement.getTimeLocation().getStartSlots()[i];
    498                                int endSlot = startSlot + iPlacement.getTimeLocation().getLength() - 1;
    499                                if (((startSlot%edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY)>=2) && rc.getResource()[startSlot-1]==null && rc.getResource()[startSlot-2]!=null)
    500                                    emptySingleHalfHours++;
    501                                if (((endSlot%edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY)<edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY-2) && rc.getResource()[startSlot+1]==null && rc.getResource()[startSlot+2]!=null)
    502                                    emptySingleHalfHours++;
    503                            }
    504                        }
    505                    }
    506                    iEmptySingleHalfHours = new Integer(emptySingleHalfHours);
    507                }
    508                return iEmptySingleHalfHours.intValue();
    509            }
    510
    511            Integer iSumHardStudentConflicts = null;
    512            public int sumHardStudentConflicts() {
    513                if (iSumHardStudentConflicts==null) {
    514                    boolean haveAlternative = (iLecture.sameLectures()==null?false:iLecture.sameLectures().size()>1);
    515                    int sumHardStudentConflicts = 0;
    516                    if (!haveAlternative) for (Enumeration i2=iLecture.jenrlConstraints().elements();i2.hasMoreElements();) {
    517                        JenrlConstraint jenrl = (JenrlConstraint)i2.nextElement();
    518                        Vector anotherSameLectures = ((Lecture)jenrl.another(iLecture)).sameLectures();
    519                        if (anotherSameLectures==null || anotherSameLectures.size()==1)
    520                            sumHardStudentConflicts += jenrl.jenrl(iLecture, iPlacement);
    521                    }
    522                    iSumHardStudentConflicts = new Integer(sumHardStudentConflicts);
    523                }
    524                return iSumHardStudentConflicts.intValue();
    525            }
    526
    527            public int roomPreference() {
    528                return iPlacement.getRoomLocation().getPreference();
    529            }
    530
    531            public long nrAssignments() {
    532                return iPlacement.countAssignments();
    533            }
    534
    535            public double timePreference() {
    536                return iPlacement.getTimeLocation().getNormalizedPreference();
    537            }
    538
    539            public boolean tooBig() {
    540                return iPlacement.getRoomLocation().getRoomSize()>TimetableModel.getMaxCapacity(iLecture.countStudents());
    541            }
    542
    543            Integer iDeptSpreadCache = null;
    544            public int deptSpread() {
    545                if (iLecture.getDeptSpreadConstraint()==null) return 0;
    546                if (iDeptSpreadCache==null)
    547                    iDeptSpreadCache = new Integer(iLecture.getDeptSpreadConstraint().getPenalty(iPlacement));
    548                return iDeptSpreadCache.intValue();
    549            }
    550
    551            Integer iDistanceInstructorPreferenceCache = null;
    552            public int distanceInstructorPreference() {
    553                if (iDistanceInstructorPreferenceCache==null) {
    554                    int pref = 0;
    555                    if (iPlacement.getInstructorId()!=null) {
    556                        for (Enumeration i2=iLecture.constraints().elements();i2.hasMoreElements();) {
    557                            Constraint constraint = (Constraint)i2.nextElement();
    558                            if (constraint instanceof InstructorConstraint) {
    559                                pref += ((InstructorConstraint)constraint).getPreference(iPlacement);
    560                                break;
    561                            }
    562                        }
    563                    }
    564                    iDistanceInstructorPreferenceCache = new Integer(pref);
    565                }
    566                return iDistanceInstructorPreferenceCache.intValue();
    567            }
    568        }
    569    }