001    package net.sf.cpsolver.studentsct.heuristics.selection;
002    
003    import java.util.ArrayList;
004    import java.util.HashSet;
005    import java.util.Iterator;
006    import java.util.List;
007    import java.util.Set;
008    
009    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
010    import net.sf.cpsolver.ifs.model.Neighbour;
011    import net.sf.cpsolver.ifs.solution.Solution;
012    import net.sf.cpsolver.ifs.solver.Solver;
013    import net.sf.cpsolver.ifs.util.DataProperties;
014    import net.sf.cpsolver.ifs.util.JProf;
015    import net.sf.cpsolver.ifs.util.Progress;
016    import net.sf.cpsolver.studentsct.StudentSectioningModel;
017    import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
018    import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
019    import net.sf.cpsolver.studentsct.model.CourseRequest;
020    import net.sf.cpsolver.studentsct.model.Enrollment;
021    import net.sf.cpsolver.studentsct.model.Request;
022    import net.sf.cpsolver.studentsct.model.Student;
023    
024    import org.apache.log4j.Logger;
025    
026    /**
027     * Pick a student (one by one) with an incomplete schedule, try to find an
028     * improvement, identify problematic students. <br>
029     * <br>
030     * For each request that does not have an assignment and that can be assined
031     * (see {@link Student#canAssign(Request)}) a randomly selected sub-domain is
032     * visited. For every such enrollment, a set of conflicting enrollments is
033     * computed and a possible student that can get an alternative enrollment is
034     * identified (if there is any). For each such move a value (the cost of moving
035     * the problematic student somewhere else) is computed and the best possible
036     * move is selected at the end. If there is no such move, a set of problematic
037     * students is identified, i.e., the students whose enrollments are preventing
038     * this student to get a request. <br>
039     * <br>
040     * Each student can be selected for this swap move multiple times, but only if
041     * there is still a request that can be resolved. At the end (when there is no
042     * other neighbour), the set of all such problematic students can be returned
043     * using the {@link ProblemStudentsProvider} interface. <br>
044     * <br>
045     * Parameters: <br>
046     * <table border='1'>
047     * <tr>
048     * <th>Parameter</th>
049     * <th>Type</th>
050     * <th>Comment</th>
051     * </tr>
052     * <tr>
053     * <td>Neighbour.SwapStudentsTimeout</td>
054     * <td>{@link Integer}</td>
055     * <td>Timeout for each neighbour selection (in milliseconds).</td>
056     * </tr>
057     * <tr>
058     * <td>Neighbour.SwapStudentsMaxValues</td>
059     * <td>{@link Integer}</td>
060     * <td>Limit for the number of considered values for each course request (see
061     * {@link CourseRequest#computeRandomEnrollments(int)}).</td>
062     * </tr>
063     * </table>
064     * <br>
065     * <br>
066     * 
067     * @version StudentSct 1.2 (Student Sectioning)<br>
068     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
069     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
070     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
071     * <br>
072     *          This library is free software; you can redistribute it and/or modify
073     *          it under the terms of the GNU Lesser General Public License as
074     *          published by the Free Software Foundation; either version 3 of the
075     *          License, or (at your option) any later version. <br>
076     * <br>
077     *          This library is distributed in the hope that it will be useful, but
078     *          WITHOUT ANY WARRANTY; without even the implied warranty of
079     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
080     *          Lesser General Public License for more details. <br>
081     * <br>
082     *          You should have received a copy of the GNU Lesser General Public
083     *          License along with this library; if not see
084     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
085     */
086    
087    public class SwapStudentSelection implements NeighbourSelection<Request, Enrollment>, ProblemStudentsProvider {
088        private static Logger sLog = Logger.getLogger(SwapStudentSelection.class);
089        private Set<Student> iProblemStudents = new HashSet<Student>();
090        private Student iStudent = null;
091        private Iterator<Student> iStudentsEnumeration = null;
092        private int iTimeout = 5000;
093        private int iMaxValues = 100;
094        public static boolean sDebug = false;
095        protected StudentOrder iOrder = new StudentChoiceRealFirstOrder();
096    
097        /**
098         * Constructor
099         * 
100         * @param properties
101         *            configuration
102         */
103        public SwapStudentSelection(DataProperties properties) {
104            iTimeout = properties.getPropertyInt("Neighbour.SwapStudentsTimeout", iTimeout);
105            iMaxValues = properties.getPropertyInt("Neighbour.SwapStudentsMaxValues", iMaxValues);
106            if (properties.getProperty("Neighbour.SwapStudentsOrder") != null) {
107                try {
108                    iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.SwapStudentsOrder"))
109                            .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties });
110                } catch (Exception e) {
111                    sLog.error("Unable to set student order, reason:" + e.getMessage(), e);
112                }
113            }
114        }
115    
116        /** Initialization */
117        @Override
118        public void init(Solver<Request, Enrollment> solver) {
119            List<Student> students = iOrder.order(((StudentSectioningModel) solver.currentSolution().getModel())
120                    .getStudents());
121            iStudentsEnumeration = students.iterator();
122            iProblemStudents.clear();
123            Progress.getInstance(solver.currentSolution().getModel()).setPhase("Student swap...", students.size());
124        }
125    
126        /**
127         * For each student that does not have a complete schedule, try to find a
128         * request and a student that can be moved out of an enrollment so that the
129         * selected student can be assigned to the selected request.
130         */
131        @Override
132        public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
133            if (iStudent != null && !iStudent.isComplete()) {
134                Selection selection = getSelection(iStudent);
135                Neighbour<Request, Enrollment> neighbour = selection.select();
136                if (neighbour != null)
137                    return neighbour;
138                else
139                    iProblemStudents.addAll(selection.getProblemStudents());
140            }
141            iStudent = null;
142            while (iStudentsEnumeration.hasNext()) {
143                Student student = iStudentsEnumeration.next();
144                Progress.getInstance(solution.getModel()).incProgress();
145                if (student.isComplete() || student.nrAssignedRequests() == 0)
146                    continue;
147                Selection selection = getSelection(student);
148                Neighbour<Request, Enrollment> neighbour = selection.select();
149                if (neighbour != null) {
150                    iStudent = student;
151                    return neighbour;
152                } else
153                    iProblemStudents.addAll(selection.getProblemStudents());
154            }
155            return null;
156        }
157    
158        /** List of problematic students */
159        @Override
160        public Set<Student> getProblemStudents() {
161            return iProblemStudents;
162        }
163    
164        /** Selection subclass for a student */
165        public Selection getSelection(Student student) {
166            return new Selection(student);
167        }
168    
169        /** This class looks for a possible swap move for the given student */
170        public class Selection {
171            private Student iStudent;
172            private long iT0, iT1;
173            private boolean iTimeoutReached;
174            private Enrollment iBestEnrollment;
175            private double iBestValue;
176            private Set<Student> iProblemStudents;
177            private List<Enrollment> iBestSwaps;
178    
179            /**
180             * Constructor
181             * 
182             * @param student
183             *            given student
184             */
185            public Selection(Student student) {
186                iStudent = student;
187            }
188    
189            /**
190             * The actual selection
191             */
192            public SwapStudentNeighbour select() {
193                if (sDebug)
194                    sLog.debug("select(S" + iStudent.getId() + ")");
195                iT0 = JProf.currentTimeMillis();
196                iTimeoutReached = false;
197                iBestEnrollment = null;
198                iProblemStudents = new HashSet<Student>();
199                Double initialValue = null;
200                for (Request request : iStudent.getRequests()) {
201                    if (initialValue == null)
202                        initialValue = request.getModel().getTotalValue();
203                    if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
204                        if (!iTimeoutReached) {
205                            if (sDebug)
206                                sLog.debug("  -- timeout reached");
207                            iTimeoutReached = true;
208                        }
209                        break;
210                    }
211                    if (request.getAssignment() != null)
212                        continue;
213                    if (!iStudent.canAssign(request))
214                        continue;
215                    if (sDebug)
216                        sLog.debug("  -- checking request " + request);
217                    List<Enrollment> values = null;
218                    if (iMaxValues > 0 && request instanceof CourseRequest) {
219                        values = ((CourseRequest) request).computeRandomEnrollments(iMaxValues);
220                    } else
221                        values = request.values();
222                    for (Enrollment enrollment : values) {
223                        if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) {
224                            if (!iTimeoutReached) {
225                                if (sDebug)
226                                    sLog.debug("  -- timeout reached");
227                                iTimeoutReached = true;
228                            }
229                            break;
230                        }
231                        if (sDebug)
232                            sLog.debug("      -- enrollment " + enrollment);
233                        Set<Enrollment> conflicts = enrollment.variable().getModel().conflictValues(enrollment);
234                        if (conflicts.contains(enrollment))
235                            continue;
236                        
237                        double bound = enrollment.toDouble();
238                        for (Enrollment conflict: conflicts)
239                            bound += conflict.variable().getBound();
240                        if (iBestEnrollment != null && bound >= iBestValue)
241                            continue;
242                        
243                        for (Enrollment conflict: conflicts)
244                            conflict.variable().unassign(0);
245                        enrollment.variable().assign(0, enrollment);
246                        
247                        boolean allResolved = true;
248                        List<Enrollment> swaps = new ArrayList<Enrollment>(conflicts.size());
249                        for (Enrollment conflict : conflicts) {
250                            if (sDebug)
251                                sLog.debug("        -- conflict " + conflict);
252                            Enrollment other = bestSwap(conflict, enrollment, iProblemStudents);
253                            if (other == null) {
254                                if (sDebug)
255                                    sLog.debug("          -- unable to resolve");
256                                allResolved = false;
257                                break;
258                            }
259                            other.variable().assign(0, other);
260                            swaps.add(other);
261                            if (sDebug)
262                                sLog.debug("          -- can be resolved by switching to " + other.getName());
263                        }
264                        double value = request.getModel().getTotalValue() - initialValue;
265                        
266                        for (Enrollment other: swaps)
267                            other.variable().unassign(0);
268                        enrollment.variable().unassign(0);
269                        for (Enrollment conflict: conflicts)
270                            conflict.variable().assign(0, conflict);
271                        
272                        if (allResolved && value <= 0.0 && (iBestEnrollment == null || iBestValue > value)) {
273                            iBestEnrollment = enrollment;
274                            iBestValue = value;
275                            iBestSwaps = swaps;
276                        }
277                    }
278                }
279                iT1 = JProf.currentTimeMillis();
280                if (sDebug)
281                    sLog.debug("  -- done, best enrollment is " + iBestEnrollment);
282                if (iBestEnrollment == null) {
283                    if (iProblemStudents.isEmpty())
284                        iProblemStudents.add(iStudent);
285                    if (sDebug)
286                        sLog.debug("  -- problem students are: " + iProblemStudents);
287                    return null;
288                }
289                if (sDebug)
290                    sLog.debug("  -- value " + iBestValue);
291                Enrollment[] assignment = new Enrollment[iStudent.getRequests().size()];
292                int idx = 0;
293                for (Request request : iStudent.getRequests()) {
294                    assignment[idx++] = (iBestEnrollment.getRequest().equals(request) ? iBestEnrollment
295                            : (Enrollment) request.getAssignment());
296                }
297                return new SwapStudentNeighbour(iBestValue, iBestEnrollment, iBestSwaps);
298            }
299    
300            /** Was timeout reached during the selection */
301            public boolean isTimeoutReached() {
302                return iTimeoutReached;
303            }
304    
305            /** Time spent in the last selection */
306            public long getTime() {
307                return iT1 - iT0;
308            }
309    
310            /** The best enrollment found. */
311            public Enrollment getBestEnrollment() {
312                return iBestEnrollment;
313            }
314    
315            /** Cost of the best enrollment found */
316            public double getBestValue() {
317                return iBestValue;
318            }
319    
320            /** Set of problematic students computed in the last selection */
321            public Set<Student> getProblemStudents() {
322                return iProblemStudents;
323            }
324    
325        }
326    
327        /**
328         * Identify the best swap for the given student
329         * 
330         * @param conflict
331         *            conflicting enrollment
332         * @param enrl
333         *            enrollment that is visited (to be assigned to the given
334         *            student)
335         * @param problematicStudents
336         *            the current set of problematic students
337         * @return best alternative enrollment for the student of the conflicting
338         *         enrollment
339         */
340        public static Enrollment bestSwap(Enrollment conflict, Enrollment enrl, Set<Student> problematicStudents) {
341            Enrollment bestEnrollment = null;
342            double bestValue = 0;
343            for (Enrollment enrollment : conflict.getRequest().values()) {
344                if (conflict.variable().getModel().inConflict(enrollment))
345                    continue;
346                double value = enrollment.toDouble();
347                if (bestEnrollment == null || bestValue > value) {
348                    bestEnrollment = enrollment;
349                    bestValue = value;
350                }
351            }
352            if (bestEnrollment == null && problematicStudents != null) {
353                boolean added = false;
354                for (Enrollment enrollment : conflict.getRequest().values()) {
355                    Set<Enrollment> conflicts = conflict.variable().getModel().conflictValues(enrollment);
356                    for (Enrollment c : conflicts) {
357                        if (enrl.getStudent().isDummy() && !c.getStudent().isDummy())
358                            continue;
359                        if (enrl.getStudent().equals(c.getStudent()) || conflict.getStudent().equals(c.getStudent()))
360                            continue;
361                        problematicStudents.add(c.getStudent());
362                    }
363                }
364                if (!added && !enrl.getStudent().equals(conflict.getStudent()))
365                    problematicStudents.add(conflict.getStudent());
366            }
367            return bestEnrollment;
368        }
369    
370        /** Neighbour that contains the swap */
371        public static class SwapStudentNeighbour extends Neighbour<Request, Enrollment> {
372            private double iValue;
373            private Enrollment iEnrollment;
374            private List<Enrollment> iSwaps;
375    
376            /**
377             * Constructor
378             * 
379             * @param value
380             *            cost of the move
381             * @param enrollment
382             *            the enrollment which is to be assigned to the given
383             *            student
384             * @param swaps
385             *            enrollment swaps
386             */
387            public SwapStudentNeighbour(double value, Enrollment enrollment, List<Enrollment> swaps) {
388                iValue = value;
389                iEnrollment = enrollment;
390                iSwaps = swaps;
391            }
392    
393            @Override
394            public double value() {
395                return iValue;
396            }
397    
398            /**
399             * Perform the move. All the requeired swaps are identified and
400             * performed as well.
401             **/
402            @Override
403            public void assign(long iteration) {
404                if (iEnrollment.variable().getAssignment() != null)
405                    iEnrollment.variable().unassign(iteration);
406                for (Enrollment swap : iSwaps) {
407                    swap.variable().unassign(iteration);
408                }
409                iEnrollment.variable().assign(iteration, iEnrollment);
410                for (Enrollment swap : iSwaps) {
411                    swap.variable().assign(iteration, swap);
412                }
413            }
414    
415            @Override
416            public String toString() {
417                StringBuffer sb = new StringBuffer("SwSt{");
418                sb.append(" " + iEnrollment.getRequest().getStudent());
419                sb.append(" (" + iValue + ")");
420                sb.append("\n " + iEnrollment.getRequest());
421                sb.append(" " + iEnrollment);
422                for (Enrollment swap : iSwaps) {
423                    sb.append("\n " + swap.getRequest());
424                    sb.append(" " + swap.variable().getAssignment());
425                    sb.append(" -> " + swap);
426                }
427                sb.append("\n}");
428                return sb.toString();
429            }
430        }
431    }