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