001    package net.sf.cpsolver.studentsct.heuristics;
002    
003    import java.util.ArrayList;
004    import java.util.List;
005    import java.util.Set;
006    
007    import net.sf.cpsolver.ifs.extension.ConflictStatistics;
008    import net.sf.cpsolver.ifs.extension.Extension;
009    import net.sf.cpsolver.ifs.extension.MacPropagation;
010    import net.sf.cpsolver.ifs.extension.ViolatedInitials;
011    import net.sf.cpsolver.ifs.heuristics.GeneralValueSelection;
012    import net.sf.cpsolver.ifs.heuristics.ValueSelection;
013    import net.sf.cpsolver.ifs.solution.Solution;
014    import net.sf.cpsolver.ifs.solver.Solver;
015    import net.sf.cpsolver.ifs.util.DataProperties;
016    import net.sf.cpsolver.ifs.util.ToolBox;
017    import net.sf.cpsolver.studentsct.StudentSectioningModel;
018    import net.sf.cpsolver.studentsct.model.Enrollment;
019    import net.sf.cpsolver.studentsct.model.Request;
020    import net.sf.cpsolver.studentsct.model.Student;
021    
022    /**
023     * Enrollment selection criterion. It is similar to
024     * {@link GeneralValueSelection}, however, it is not allowed to assign a
025     * enrollment to a dummy student {@link Student#isDummy()} that is conflicting
026     * with an enrollment of a real student.
027     * 
028     * @version StudentSct 1.2 (Student Sectioning)<br>
029     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
030     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
031     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
032     * <br>
033     *          This library is free software; you can redistribute it and/or modify
034     *          it under the terms of the GNU Lesser General Public License as
035     *          published by the Free Software Foundation; either version 3 of the
036     *          License, or (at your option) any later version. <br>
037     * <br>
038     *          This library is distributed in the hope that it will be useful, but
039     *          WITHOUT ANY WARRANTY; without even the implied warranty of
040     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
041     *          Lesser General Public License for more details. <br>
042     * <br>
043     *          You should have received a copy of the GNU Lesser General Public
044     *          License along with this library; if not see
045     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
046     */
047    public class EnrollmentSelection implements ValueSelection<Request, Enrollment> {
048        private double iRandomWalkProb = 0.0;
049        private double iInitialSelectionProb = 0.0;
050        private double iGoodSelectionProb = 0.0;
051        private int iMPPLimit = -1;
052    
053        private double iWeightDeltaInitialAssignment = 0.0;
054        private double iWeightPotentialConflicts = 0.0;
055        private double iWeightWeightedCoflicts = 0.0;
056        private double iWeightCoflicts = 1.0;
057        private double iWeightNrAssignments = 0.5;
058        private double iWeightValue = 0.0;
059    
060        protected int iTabuSize = 0;
061        protected List<Enrollment> iTabu = null;
062        protected int iTabuPos = 0;
063    
064        private boolean iMPP = false;
065        private ConflictStatistics<Request, Enrollment> iStat = null;
066        private MacPropagation<Request, Enrollment> iProp = null;
067        private ViolatedInitials<Request, Enrollment> iViolatedInitials = null;
068    
069        public EnrollmentSelection() {
070        }
071    
072        /**
073         * Constructor
074         * 
075         * @param properties
076         *            input configuration
077         */
078        public EnrollmentSelection(DataProperties properties) {
079            iMPP = properties.getPropertyBoolean("General.MPP", false);
080            if (iMPP) {
081                iMPPLimit = properties.getPropertyInt("Value.MPPLimit", -1);
082                iInitialSelectionProb = properties.getPropertyDouble("Value.InitialSelectionProb", 0.75);
083                iWeightDeltaInitialAssignment = properties.getPropertyDouble("Value.WeightDeltaInitialAssignments", 0.0);
084            }
085            iGoodSelectionProb = properties.getPropertyDouble("Value.GoodSelectionProb", 0.00);
086            iWeightWeightedCoflicts = properties.getPropertyDouble("Value.WeightWeightedConflicts", 1.0);
087            iWeightPotentialConflicts = properties.getPropertyDouble("Value.WeightPotentialConflicts", 0.0);
088    
089            iRandomWalkProb = properties.getPropertyDouble("Value.RandomWalkProb", 0.0);
090            iWeightCoflicts = properties.getPropertyDouble("Value.WeightConflicts", 1.0);
091            iWeightNrAssignments = properties.getPropertyDouble("Value.WeightNrAssignments", 0.5);
092            iWeightValue = properties.getPropertyDouble("Value.WeightValue", 0.0);
093            iTabuSize = properties.getPropertyInt("Value.Tabu", 0);
094            if (iTabuSize > 0)
095                iTabu = new ArrayList<Enrollment>(iTabuSize);
096        }
097    
098        /** Initialization */
099        @Override
100        public void init(Solver<Request, Enrollment> solver) {
101            for (Extension<Request, Enrollment> extension : solver.getExtensions()) {
102                if (ConflictStatistics.class.isInstance(extension))
103                    iStat = (ConflictStatistics<Request, Enrollment>) extension;
104                if (MacPropagation.class.isInstance(extension))
105                    iProp = (MacPropagation<Request, Enrollment>) extension;
106                if (ViolatedInitials.class.isInstance(extension))
107                    iViolatedInitials = (ViolatedInitials<Request, Enrollment>) extension;
108            }
109        }
110    
111        /** true, if it is allowed to assign given value */
112        public boolean isAllowed(Enrollment value) {
113            return isAllowed(value, null);
114        }
115    
116        /** true, if it is allowed to assign given value */
117        public boolean isAllowed(Enrollment value, Set<Enrollment> conflicts) {
118            if (value == null)
119                return true;
120            StudentSectioningModel model = (StudentSectioningModel) value.variable().getModel();
121            if (model.getNrLastLikeRequests(false) == 0 || model.getNrRealRequests(false) == 0)
122                return true;
123            Request request = value.variable();
124            if (request.getStudent().isDummy()) {
125                if (conflicts == null)
126                    conflicts = value.variable().getModel().conflictValues(value);
127                for (Enrollment conflict : conflicts) {
128                    if (!conflict.getRequest().getStudent().isDummy())
129                        return false;
130                }
131            } else {
132                if (conflicts == null)
133                    conflicts = value.variable().getModel().conflictValues(value);
134                if (conflicts.size() > (request.getAssignment() == null ? 1 : 0))
135                    return false;
136            }
137            return true;
138        }
139    
140        /** Value selection */
141        @Override
142        public Enrollment selectValue(Solution<Request, Enrollment> solution, Request selectedVariable) {
143            if (iMPP) {
144                if (selectedVariable.getInitialAssignment() != null) {
145                    if (solution.getModel().unassignedVariables().isEmpty()) {
146                        if (solution.getModel().perturbVariables().size() <= iMPPLimit)
147                            iMPPLimit = solution.getModel().perturbVariables().size() - 1;
148                    }
149                    if (iMPPLimit >= 0 && solution.getModel().perturbVariables().size() > iMPPLimit) {
150                        if (isAllowed(selectedVariable.getInitialAssignment()))
151                            return selectedVariable.getInitialAssignment();
152                    }
153                    if (selectedVariable.getInitialAssignment() != null && ToolBox.random() <= iInitialSelectionProb) {
154                        if (isAllowed(selectedVariable.getInitialAssignment()))
155                            return selectedVariable.getInitialAssignment();
156                    }
157                }
158            }
159    
160            List<Enrollment> values = selectedVariable.values();
161            if (ToolBox.random() <= iRandomWalkProb) {
162                Enrollment value = ToolBox.random(values);
163                if (isAllowed(value))
164                    return value;
165            }
166            if (iProp != null && selectedVariable.getAssignment() == null && ToolBox.random() <= iGoodSelectionProb) {
167                Set<Enrollment> goodValues = iProp.goodValues(selectedVariable);
168                if (!goodValues.isEmpty())
169                    values = new ArrayList<Enrollment>(goodValues);
170            }
171            if (values.size() == 1) {
172                Enrollment value = values.get(0);
173                if (isAllowed(value))
174                    return value;
175                else
176                    return null;
177            }
178    
179            List<Enrollment> bestValues = null;
180            double bestWeightedSum = 0;
181    
182            for (Enrollment value : values) {
183                if (iTabu != null && iTabu.contains(value))
184                    continue;
185                if (selectedVariable.getAssignment() != null && selectedVariable.getAssignment().equals(value))
186                    continue;
187    
188                Set<Enrollment> conf = solution.getModel().conflictValues(value);
189                if (conf.contains(value))
190                    continue;
191    
192                if (!isAllowed(value, conf))
193                    continue;
194    
195                double weightedConflicts = (iStat == null || iWeightWeightedCoflicts == 0.0 ? 0.0 : iStat.countRemovals(
196                        solution.getIteration(), conf, value));
197                double potentialConflicts = (iStat == null || iWeightPotentialConflicts == 0.0 ? 0.0 : iStat
198                        .countPotentialConflicts(solution.getIteration(), value, 3));
199    
200                long deltaInitialAssignments = 0;
201                if (iMPP && iWeightDeltaInitialAssignment != 0.0) {
202                    if (iViolatedInitials != null) {
203                        Set<Enrollment> violations = iViolatedInitials.getViolatedInitials(value);
204                        if (violations != null) {
205                            for (Enrollment aValue : violations) {
206                                if (aValue.variable().getAssignment() == null
207                                        || aValue.variable().getAssignment().equals(aValue))
208                                    deltaInitialAssignments += 2;
209                            }
210                        }
211                    }
212                    for (Enrollment aValue : conf) {
213                        if (aValue.variable().getInitialAssignment() != null)
214                            deltaInitialAssignments--;
215                    }
216                    if (selectedVariable.getInitialAssignment() != null
217                            && !selectedVariable.getInitialAssignment().equals(value)) {
218                        deltaInitialAssignments++;
219                    }
220                    if (iMPPLimit >= 0
221                            && (solution.getModel().perturbVariables().size() + deltaInitialAssignments) > iMPPLimit)
222                        continue;
223                }
224    
225                double weightedSum = (iWeightDeltaInitialAssignment * deltaInitialAssignments)
226                        + (iWeightPotentialConflicts * potentialConflicts) + (iWeightWeightedCoflicts * weightedConflicts)
227                        + (iWeightCoflicts * conf.size()) + (iWeightNrAssignments * value.countAssignments())
228                        + (iWeightValue * value.toDouble());
229    
230                if (bestValues == null || bestWeightedSum > weightedSum) {
231                    bestWeightedSum = weightedSum;
232                    if (bestValues == null)
233                        bestValues = new ArrayList<Enrollment>();
234                    else
235                        bestValues.clear();
236                    bestValues.add(value);
237                } else {
238                    if (bestWeightedSum == weightedSum)
239                        bestValues.add(value);
240                }
241            }
242    
243            Enrollment selectedValue = (bestValues == null ? null : ToolBox.random(bestValues));
244            if (selectedValue == null)
245                selectedValue = ToolBox.random(values);
246            if (iTabu != null) {
247                if (iTabu.size() == iTabuPos)
248                    iTabu.add(selectedValue);
249                else
250                    iTabu.set(iTabuPos, selectedValue);
251                iTabuPos = (iTabuPos + 1) % iTabuSize;
252            }
253            return (bestValues == null ? null : selectedValue);
254        }
255    
256    }