001package org.cpsolver.studentsct.heuristics.selection;
002
003import java.util.ArrayList;
004import java.util.Collections;
005import java.util.Comparator;
006import java.util.ConcurrentModificationException;
007import java.util.HashMap;
008import java.util.Iterator;
009import java.util.LinkedList;
010import java.util.List;
011import java.util.Queue;
012import java.util.concurrent.locks.Lock;
013
014import org.cpsolver.ifs.assignment.Assignment;
015import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection;
016import org.cpsolver.ifs.heuristics.NeighbourSelection;
017import org.cpsolver.ifs.model.Neighbour;
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.studentsct.StudentSectioningModel;
023import org.cpsolver.studentsct.model.CourseRequest;
024import org.cpsolver.studentsct.model.Enrollment;
025import org.cpsolver.studentsct.model.Request;
026
027/**
028 * Swap enrollments of different students of a course. This is to improve
029 * the enrollment alternativity {@link Enrollment#getPriority()} as well as
030 * selection preferences {@link Enrollment#percentSelected()}. 
031 * 
032 * <br>
033 * <br>
034 * 
035 * @version StudentSct 1.3 (Student Sectioning)<br>
036 *          Copyright (C) 2007 - 2018 Tomas Muller<br>
037 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
038 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
039 * <br>
040 *          This library is free software; you can redistribute it and/or modify
041 *          it under the terms of the GNU Lesser General Public License as
042 *          published by the Free Software Foundation; either version 3 of the
043 *          License, or (at your option) any later version. <br>
044 * <br>
045 *          This library is distributed in the hope that it will be useful, but
046 *          WITHOUT ANY WARRANTY; without even the implied warranty of
047 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
048 *          Lesser General Public License for more details. <br>
049 * <br>
050 *          You should have received a copy of the GNU Lesser General Public
051 *          License along with this library; if not see
052 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
053 */
054
055public class StudentEnrollmentSwapSelection implements NeighbourSelection<Request, Enrollment> {
056    private Selection iSelection = null;
057    protected Queue<Request> iRequests = null;
058
059    public StudentEnrollmentSwapSelection(DataProperties properties) {
060    }
061
062    public void init(Solver<Request, Enrollment> solver, String name) {
063        List<Request> variables = new ArrayList<Request>(solver.currentSolution().getModel().assignedVariables(solver.currentSolution().getAssignment()));
064        Collections.shuffle(variables);
065        iRequests = new LinkedList<Request>(variables);
066        if (iSelection == null) {
067            try {
068                iSelection = new Selection(solver.getProperties());
069                iSelection.init(solver);
070            } catch (Exception e) {
071                throw new RuntimeException(e.getMessage(), e);
072            }
073        }
074        Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size());
075    }
076
077    @Override
078    public void init(Solver<Request, Enrollment> solver) {
079        init(solver, "Enrollment swaps...");
080    }
081    
082    protected synchronized Request nextRequest() {
083        return iRequests.poll();
084    }
085    
086    public synchronized void addRequest(Request request) {
087        if (iRequests != null) iRequests.add(request);
088    }
089
090    @Override
091    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
092        Request request = null;
093        while ((request = nextRequest()) != null) {
094            Progress.getInstance(solution.getModel()).incProgress();
095            if (request instanceof CourseRequest) {
096                try {
097                    Enrollment e = request.getAssignment(solution.getAssignment());
098                    if (e == null || e.getPriority() > 0 || !((CourseRequest)request).getSelectedChoices().isEmpty()) {
099                        Neighbour<Request, Enrollment> n = iSelection.selectNeighbour(solution, request);
100                        if (n != null && n.value(solution.getAssignment()) <= 0.0)
101                            return n;
102                    }
103                } catch (ConcurrentModificationException e) {
104                    addRequest(request);
105                }
106            }
107        }
108        return null;
109    }
110    
111    class Selection extends BacktrackNeighbourSelection<Request, Enrollment> {
112        private int iMaxValues = 1000;
113        
114        Selection(DataProperties properties) throws Exception {
115            super(properties);
116            setTimeout(properties.getPropertyInt("Neighbour.EnrollmentSwapTimeout", 500));
117            iMaxValues = properties.getPropertyInt("Neighbour.EnrollmentSwapMaxValues", iMaxValues);
118        }
119        
120        @Override
121        protected Iterator<Enrollment> values(BacktrackNeighbourSelection<Request, Enrollment>.BacktrackNeighbourSelectionContext context, Request variable) {
122            if (variable instanceof CourseRequest) {
123                final CourseRequest request = (CourseRequest)variable;
124                final StudentSectioningModel model = (StudentSectioningModel)context.getModel();
125                final Assignment<Request, Enrollment> assignment = context.getAssignment();
126                List<Enrollment> values = null;
127                Enrollment current = request.getAssignment(context.getAssignment());
128                if (!request.getSelectedChoices().isEmpty() && current != null && current.getPriority() == 0) {
129                    values = request.getSelectedEnrollments(assignment, false);
130                } else {
131                    values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment));
132                }
133                Collections.sort(values, new Comparator<Enrollment>() {
134                    private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
135                    private Double value(Enrollment e) {
136                        Double value = iValues.get(e);
137                        if (value == null) {
138                            if (model.getStudentQuality() != null)
139                                value = model.getStudentWeights().getWeight(assignment, e, model.getStudentQuality().conflicts(e));
140                            else
141                                value = model.getStudentWeights().getWeight(assignment, e,
142                                        (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)),
143                                        (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().conflicts(e)));
144                            iValues.put(e, value);
145                        }
146                        return value;
147                    }
148                    @Override
149                    public int compare(Enrollment e1, Enrollment e2) {
150                        if (e1.equals(assignment.getValue(request))) return -1;
151                        if (e2.equals(assignment.getValue(request))) return 1;
152                        Double v1 = value(e1), v2 = value(e2);
153                        return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1);
154                    }
155                });
156                return values.iterator();
157            } else {
158                return variable.computeEnrollments(context.getAssignment()).iterator();
159            }
160        }
161        
162        @Override
163        protected void selectNeighbour(Solution<Request, Enrollment> solution, Request variable, BacktrackNeighbourSelectionContext context) {
164            Lock lock = solution.getLock().writeLock();
165            lock.lock();
166            try {
167                exploreEnrollmentSwaps(context, variable);
168            } finally {
169                lock.unlock();
170            }
171        }
172        
173        protected void exploreEnrollmentSwaps(BacktrackNeighbourSelectionContext context, Request variable) {
174            Enrollment current = context.getAssignment().getValue(variable);
175            double currentValue = (current == null ? 0.0 : current.toDouble(context.getAssignment()));
176            for (Iterator<Enrollment> e = values(context, variable); canContinueEvaluation(context) && e.hasNext();) {
177                Enrollment value = e.next();
178                if (value.equals(current)) continue;
179                if (current != null && currentValue <= value.toDouble(context.getAssignment())) continue;
180                if (context.isTimeoutReached() || context.isMaxItersReached()) break;
181                context.incIteration();
182                if (context.getModel().inConflict(context.getAssignment(), value)) {
183                    for (Enrollment other: new ArrayList<Enrollment>(value.getCourse().getContext(context.getAssignment()).getEnrollments())) {
184                        if (other.getStudent().equals(value.getStudent()) || !other.getSections().equals(value.getSections())) continue;
185                        context.getAssignment().unassign(0, other.variable());
186                        if (!context.getModel().inConflict(context.getAssignment(), value)) {
187                            if (current != null)
188                                context.getAssignment().unassign(0, current.variable());
189                            context.getAssignment().assign(0, value);
190                            for (Iterator<Enrollment> f = values(context, other.variable()); canContinueEvaluation(context) && f.hasNext();) {
191                                Enrollment fix = f.next();
192                                if (!context.getModel().inConflict(context.getAssignment(), fix)) {
193                                    context.getAssignment().assign(0, fix);
194                                    context.saveBest(variable, other.variable());
195                                    context.getAssignment().unassign(0, fix.variable());
196                                }
197                            }
198                            if (current == null)
199                                context.getAssignment().unassign(0, variable);
200                            else
201                                context.getAssignment().assign(0, current);
202                        }
203                        context.getAssignment().assign(0, other);
204                    }
205                } else {
206                    if (current != null)
207                        context.getAssignment().unassign(0, current.variable());
208                    context.getAssignment().assign(0, value);
209                    context.saveBest(variable);
210                    if (current == null)
211                        context.getAssignment().unassign(0, variable);
212                    else
213                        context.getAssignment().assign(0, current);
214                }
215            }
216        }        
217    }
218
219}