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