001package net.sf.cpsolver.studentsct.heuristics.selection;
002
003import java.util.ArrayList;
004import java.util.HashSet;
005import java.util.Iterator;
006import java.util.List;
007import java.util.Set;
008
009import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
010import net.sf.cpsolver.ifs.model.Neighbour;
011import net.sf.cpsolver.ifs.solution.Solution;
012import net.sf.cpsolver.ifs.solver.Solver;
013import net.sf.cpsolver.ifs.util.DataProperties;
014import net.sf.cpsolver.ifs.util.JProf;
015import net.sf.cpsolver.ifs.util.Progress;
016import net.sf.cpsolver.studentsct.StudentSectioningModel;
017import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
018import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
019import net.sf.cpsolver.studentsct.model.CourseRequest;
020import net.sf.cpsolver.studentsct.model.Enrollment;
021import net.sf.cpsolver.studentsct.model.Request;
022import net.sf.cpsolver.studentsct.model.Student;
023
024import 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 Tomáš Müller<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
087public 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}