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