    001package org.cpsolver.studentsct.heuristics.selection;
    002
    003import java.util.ArrayList;
    004import java.util.Collections;
    005import java.util.HashSet;
    006import java.util.Iterator;
    007import java.util.LinkedList;
    008import java.util.List;
    009import java.util.Queue;
    010import java.util.Set;
    011
    012import org.cpsolver.ifs.assignment.Assignment;
    013import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection;
    014import org.cpsolver.ifs.heuristics.NeighbourSelection;
    015import org.cpsolver.ifs.heuristics.RouletteWheelSelection;
    016import org.cpsolver.ifs.model.Neighbour;
    017import org.cpsolver.ifs.model.SimpleNeighbour;
    018import org.cpsolver.ifs.solution.Solution;
    019import org.cpsolver.ifs.solver.Solver;
    020import org.cpsolver.ifs.util.DataProperties;
    021import org.cpsolver.ifs.util.Progress;
    022import org.cpsolver.ifs.util.ToolBox;
    023import org.cpsolver.studentsct.StudentSectioningModel;
    024import org.cpsolver.studentsct.model.Course;
    025import org.cpsolver.studentsct.model.CourseRequest;
    026import org.cpsolver.studentsct.model.Enrollment;
    027import org.cpsolver.studentsct.model.Offering;
    028import org.cpsolver.studentsct.model.Request;
    029import org.cpsolver.studentsct.model.RequestGroup;
    030import org.cpsolver.studentsct.model.Section;
    031import org.cpsolver.studentsct.model.Subpart;
    032
    033/**
    034 * Shuffle students along request groups. This selection tries to improve the
    035 * ability to keep students of the same request group together by moving students
    036 * of a request group that are spread over multiple sections into a single section
    037 * or into a fewer number of sections.
    038 *
    039 * @author  Tomáš Müller
    040 * @version StudentSct 1.3 (Student Sectioning)<br>
    041 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    042 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    043 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    044 * <br>
    045 *          This library is free software; you can redistribute it and/or modify
    046 *          it under the terms of the GNU Lesser General Public License as
    047 *          published by the Free Software Foundation; either version 3 of the
    048 *          License, or (at your option) any later version. <br>
    049 * <br>
    050 *          This library is distributed in the hope that it will be useful, but
    051 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    052 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    053 *          Lesser General Public License for more details. <br>
    054 * <br>
    055 *          You should have received a copy of the GNU Lesser General Public
    056 *          License along with this library; if not see
    057 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    058 */
    059public class ShuffleStudentsSelection implements NeighbourSelection<Request, Enrollment> {
    060    private Queue<Shuffle> iQueue = null;
    061    private ShuffleBacktrackNeighbourSelection iBacktrack;
    062
    063    /**
    064     * Constructor
    065     * @param properties the selection has no properties at the moment
    066     */
    067    public ShuffleStudentsSelection(DataProperties properties) {
    068    }
    069
    070    @Override
    071    public void init(Solver<Request, Enrollment> solver) {
    072        StudentSectioningModel model = (StudentSectioningModel)solver.currentSolution().getModel();
    073        iQueue = new LinkedList<Shuffle>();
    074        Assignment<Request, Enrollment> assignment = solver.currentSolution().getAssignment();
    075        // Check all request groups that have a spread < 1.0
    076        RouletteWheelSelection<RequestGroup> groups = new RouletteWheelSelection<RequestGroup>();
    077        for (Offering offering: model.getOfferings()) {
    078            if (offering.isDummy()) continue;
    079            for (Course course: offering.getCourses()) {
    080                for (RequestGroup group: course.getRequestGroups()) {
    081                    double spread = group.getAverageSpread(solver.currentSolution().getAssignment());
    082                    if (spread >= 1.0) continue;
    083                    groups.add(group, 1.0 - spread);
    084                }
    085            }
    086        }
    087        // If there are some, pick one randomly (using roulette wheel selection)
    088        if (groups.hasMoreElements()) {
    089            RequestGroup group = groups.nextElement();
    090            RouletteWheelSelection<Subpart> subparts = new RouletteWheelSelection<Subpart>();
    091            for (CourseRequest cr: group.getRequests()) {
    092                Enrollment e = assignment.getValue(cr);
    093                if (e != null)
    094                    for (Section section: e.getSections())
    095                        if (group.getSectionSpread(assignment, section) < 1.0)
    096                            subparts.addExisting(section.getSubpart(), 1.0);
    097            }
    098            if (subparts.hasMoreElements()) {
    099                // Pick a subpart that has sections with a section spread < 1.0
    100                Subpart subpart = subparts.nextElement();
    101                RouletteWheelSelection<Section> sections = new RouletteWheelSelection<Section>();
    102                section: for (Section section: subpart.getSections()) {
    103                    // Only take sections that all requests can use
    104                    for (CourseRequest cr: group.getRequests()) {
    105                        boolean match = false;
    106                        for (Enrollment e: cr.values(assignment))
    107                            if (e.getSections().contains(section)) { match = true; break; }
    108                        if (!match) continue section;
    109                    }
    110                    // Take sections with conflicts with lower probability
    111                    int nrConflicts = 0;
    112                    if (!section.isAllowOverlap())
    113                        requests: for (CourseRequest cr: group.getRequests()) {
    114                            for (Request r: cr.getStudent().getRequests()) {
    115                                if (r.equals(cr)) continue;
    116                                Enrollment e = assignment.getValue(r);
    117                                if (e != null && !e.isAllowOverlap() && section.isOverlapping(e.getSections())) {
    118                                    nrConflicts++; continue requests;
    119                                }
    120                            }
    121                        }
    122                    sections.add(section, 1 + group.getRequests().size() - nrConflicts);
    123                }
    124                Set<Section> filter = new HashSet<Section>(); double space = 0.0;
    125                // Pick enough sections
    126                while (sections.hasMoreElements()) {
    127                    Section section = sections.nextElement();
    128                    if (filter.add(section)) {
    129                        if (section.getLimit() < 0) break;
    130                        space += section.getLimit();
    131                    }
    132                    if (space >= group.getTotalWeight()) break;
    133                }
    134                // Add all requests that should be moved into the queue
    135                for (CourseRequest cr: group.getRequests()) {
    136                    Shuffle shuffle = new Shuffle(group, cr, filter);
    137                    Enrollment e = assignment.getValue(cr);
    138                    if (e != null && shuffle.matchFilter(e)) continue;
    139                    iQueue.add(shuffle);
    140                }
    141            } else {
    142                // No subpart -> no section filter
    143                for (CourseRequest cr: group.getRequests())
    144                    iQueue.add(new Shuffle(group, cr, null));
    145            }
    146        }
    147        // Shuffle the queue
    148        Collections.shuffle((LinkedList<Shuffle>)iQueue);
    149        // Initialize the backtrack selection, if needed
    150        if (iBacktrack == null) {
    151            try {
    152                iBacktrack = new ShuffleBacktrackNeighbourSelection(solver.getProperties());
    153                iBacktrack.init(solver);
    154            } catch (Exception e) {
    155                throw new RuntimeException(e.getMessage(), e);
    156            }
    157        }
    158        // Change progress
    159        Progress.getInstance(solver.currentSolution().getModel()).setPhase("Shuffling students along request groups...", iQueue.size());
    160    }
    161
    162    @Override
    163    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    164        Shuffle shuffle = null;
    165        while ((shuffle = iQueue.poll()) != null) {
    166            Progress.getInstance(solution.getModel()).incProgress();
    167            // Take an item from the queue, try backtrack first
    168            Neighbour<Request, Enrollment> n = iBacktrack.selectNeighbour(solution, shuffle);
    169            if (n != null) return n;
    170            // If fails, just assign the request randomly and hope for the best
    171            List<Enrollment> adepts = new ArrayList<Enrollment>();
    172            for (Enrollment e: shuffle.getRequest().values(solution.getAssignment())) {
    173                if (shuffle.matchFilter(e)) adepts.add(e);
    174            }
    175            if (!adepts.isEmpty()) {
    176                return new SimpleNeighbour<Request, Enrollment>(shuffle.getRequest(), ToolBox.random(adepts));
    177            }
    178        }
    179        return null;
    180    }
    181
    182    /**
    183     * One item to be shuffled
    184     */
    185    private static class Shuffle {
    186        RequestGroup iGroup;
    187        CourseRequest iRequest;
    188        Set<Section> iFilter;
    189
    190        /**
    191         * Constructor
    192         * @param group selected request group
    193         * @param request selected request of a request group
    194         * @param filter section filter (if used, only enrollments that contain one of the given sections can be used)
    195         */
    196        Shuffle(RequestGroup group, CourseRequest request, Set<Section> filter) {
    197            iGroup = group;
    198            iRequest = request;
    199            iFilter = filter;
    200        }
    201
    202        /**
    203         * Selected request group
    204         * @return a request group
    205         */
    206        public CourseRequest getRequest() { return iRequest; }
    207
    208        /**
    209         * Is there a section filter set?
    210         * @return true, if only enrollments with matching sections can be used
    211         */
    212        public boolean hasFilter() { return iFilter != null && !iFilter.isEmpty(); }
    213
    214        /**
    215         * Is the given request matching this object?
    216         * @param variable a request
    217         * @return true if the given variable is a course request for a matching course
    218         */
    219        public boolean matchRequest(Request variable) {
    220            return variable instanceof CourseRequest && ((CourseRequest)variable).getCourses().contains(iGroup.getCourse());
    221        }
    222
    223        /**
    224         * Is the given enrollment matching the section filter
    225         * @param e an enrollment
    226         * @return true if the enrollment contains at least one section of the filter
    227         */
    228        public boolean matchFilter(Enrollment e) {
    229            if (iFilter == null || iFilter.isEmpty()) return true;
    230            for (Section s: e.getSections())
    231                if (iFilter.contains(s)) return true;
    232            return false;
    233        }
    234    }
    235
    236    /**
    237     * A special version of the {@link BacktrackNeighbourSelection} that filters the enrollments with the
    238     * provided section filter.
    239     *
    240     */
    241    public static class ShuffleBacktrackNeighbourSelection extends BacktrackNeighbourSelection<Request, Enrollment> {
    242
    243        /**
    244         * Constructor
    245         * @param properties configuration
    246         * @throws Exception thrown when initialization fails
    247         */
    248        ShuffleBacktrackNeighbourSelection(DataProperties properties) throws Exception {
    249            super(properties);
    250            setTimeout(properties.getPropertyInt("Shuffle.BackTrackTimeout", getTimeout()));
    251            setDepth(properties.getPropertyInt("Shuffle.BackTrackDepth", getDepth()));
    252            setMaxIters(properties.getPropertyInt("Shuffle.BackTrackMaxIters", getMaxIters()));
    253        }
    254
    255        /**
    256         * List of values of the given variable that will be considered (filtered using {@link ShuffleStudentsSelection.Shuffle#matchFilter(Enrollment)} if applicable).
    257         * @param context assignment context
    258         * @param variable given variable
    259         * @return values of the given variable that will be considered
    260         */
    261        @Override
    262        protected Iterator<Enrollment> values(BacktrackNeighbourSelectionContext context, Request variable) {
    263            Shuffle shuffle = ((ShuffleBacktrackNeighbourSelectionContext)context).getShuffle();
    264            if (shuffle.matchRequest(variable) && shuffle.hasFilter()) {
    265                List<Enrollment> values = new ArrayList<Enrollment>();
    266                for (Iterator<Enrollment> i = super.values(context, variable); i.hasNext(); ) {
    267                    Enrollment e = i.next();
    268                    if (shuffle.matchFilter(e)) values.add(e);
    269                }
    270                return values.iterator();
    271            } else {
    272                return super.values(context, variable);
    273            }
    274        }
    275
    276        protected Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution, Shuffle shuffle) {
    277            BacktrackNeighbourSelectionContext context = new ShuffleBacktrackNeighbourSelectionContext(solution, shuffle);
    278            selectNeighbour(solution, shuffle.getRequest(), context);
    279            return context.getBackTrackNeighbour();
    280        }
    281
    282        private class ShuffleBacktrackNeighbourSelectionContext extends BacktrackNeighbourSelectionContext {
    283            private Shuffle iShuffle = null;
    284
    285            private ShuffleBacktrackNeighbourSelectionContext(Solution<Request, Enrollment> solution, Shuffle shuffle) {
    286                super(solution);
    287                iShuffle = shuffle;
    288            }
    289
    290            private Shuffle getShuffle() { return iShuffle; }
    291        }
    292    }
    293
    294}