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