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