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.Comparator;
008import java.util.ConcurrentModificationException;
009import java.util.HashMap;
010import java.util.Iterator;
011import java.util.LinkedList;
012import java.util.List;
013import java.util.Map;
014import java.util.Queue;
015import java.util.concurrent.locks.Lock;
016
017import org.cpsolver.ifs.assignment.Assignment;
018import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection;
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.util.DataProperties;
025import org.cpsolver.ifs.util.Progress;
026import org.cpsolver.studentsct.StudentSectioningModel;
027import org.cpsolver.studentsct.model.CourseRequest;
028import org.cpsolver.studentsct.model.Enrollment;
029import org.cpsolver.studentsct.model.Request;
030
031/**
032 * Swap enrollments of different students of a course. This is to improve
033 * the enrollment alternativity {@link Enrollment#getPriority()} as well as
034 * selection preferences {@link Enrollment#percentSelected()}. 
035 * 
036 * <br>
037 * <br>
038 * 
039 * @version StudentSct 1.3 (Student Sectioning)<br>
040 *          Copyright (C) 2007 - 2018 Tomas Muller<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 */
058
059public class StudentEnrollmentSwapSelection implements NeighbourSelection<Request, Enrollment>, InfoProvider<Request, Enrollment> {
060    private static DecimalFormat sDF = new DecimalFormat("0.00");
061    private Selection iSelection = null;
062    protected Queue<Request> iRequests = null;
063    
064    protected long iNbrIterations = 0;
065    protected long iTotalTime = 0;
066    protected long iNbrTimeoutReached = 0;
067    protected long iNbrNoSolution = 0;
068
069    public StudentEnrollmentSwapSelection(DataProperties properties) {
070    }
071
072    public void init(Solver<Request, Enrollment> solver, String name) {
073        List<Request> variables = new ArrayList<Request>(solver.currentSolution().getModel().assignedVariables(solver.currentSolution().getAssignment()));
074        Collections.shuffle(variables);
075        iRequests = new LinkedList<Request>(variables);
076        if (iSelection == null) {
077            try {
078                iSelection = new Selection(solver.getProperties());
079                iSelection.init(solver);
080            } catch (Exception e) {
081                throw new RuntimeException(e.getMessage(), e);
082            }
083        }
084        Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size());
085        iNbrIterations = 0;
086        iNbrTimeoutReached = 0;
087        iNbrNoSolution = 0;
088        iTotalTime = 0;
089    }
090
091    @Override
092    public void init(Solver<Request, Enrollment> solver) {
093        init(solver, "Enrollment swaps...");
094    }
095    
096    protected synchronized Request nextRequest() {
097        return iRequests.poll();
098    }
099    
100    public synchronized void addRequest(Request request) {
101        if (iRequests != null) iRequests.add(request);
102    }
103
104    @Override
105    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
106        Request request = null;
107        while ((request = nextRequest()) != null) {
108            Progress.getInstance(solution.getModel()).incProgress();
109            if (request instanceof CourseRequest) {
110                try {
111                    Enrollment e = request.getAssignment(solution.getAssignment());
112                    if (e == null || e.getPriority() > 0 || !((CourseRequest)request).getSelectedChoices().isEmpty()) {
113                        Neighbour<Request, Enrollment> n = iSelection.selectNeighbour(solution, request);
114                        if (iSelection.getContext() != null) {
115                            iNbrIterations ++;
116                            iTotalTime += iSelection.getContext().getTime();
117                            if (iSelection.getContext().isTimeoutReached()) iNbrTimeoutReached ++;
118                            if (n == null) iNbrNoSolution ++;
119                        }
120                        if (n != null && n.value(solution.getAssignment()) <= 0.0)
121                            return n;
122                    }
123                } catch (ConcurrentModificationException e) {
124                    addRequest(request);
125                }
126            }
127        }
128        return null;
129    }
130    
131    class Selection extends BacktrackNeighbourSelection<Request, Enrollment> {
132        private int iMaxValues = 1000;
133        
134        Selection(DataProperties properties) throws Exception {
135            super(properties);
136            setTimeout(properties.getPropertyInt("Neighbour.EnrollmentSwapTimeout", 500));
137            iMaxValues = properties.getPropertyInt("Neighbour.EnrollmentSwapMaxValues", iMaxValues);
138        }
139        
140        @Override
141        protected Iterator<Enrollment> values(BacktrackNeighbourSelection<Request, Enrollment>.BacktrackNeighbourSelectionContext context, Request variable) {
142            if (variable instanceof CourseRequest) {
143                final CourseRequest request = (CourseRequest)variable;
144                final StudentSectioningModel model = (StudentSectioningModel)context.getModel();
145                final Assignment<Request, Enrollment> assignment = context.getAssignment();
146                List<Enrollment> values = null;
147                Enrollment current = request.getAssignment(context.getAssignment());
148                if (!request.getSelectedChoices().isEmpty() && current != null && current.getPriority() == 0) {
149                    values = request.getSelectedEnrollments(assignment, false);
150                } else {
151                    values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment));
152                }
153                Collections.sort(values, new Comparator<Enrollment>() {
154                    private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
155                    private Double value(Enrollment e) {
156                        Double value = iValues.get(e);
157                        if (value == null) {
158                            if (model.getStudentQuality() != null)
159                                value = model.getStudentWeights().getWeight(assignment, e, model.getStudentQuality().conflicts(e));
160                            else
161                                value = model.getStudentWeights().getWeight(assignment, e,
162                                        (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)),
163                                        (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().conflicts(e)));
164                            iValues.put(e, value);
165                        }
166                        return value;
167                    }
168                    @Override
169                    public int compare(Enrollment e1, Enrollment e2) {
170                        if (e1.equals(assignment.getValue(request))) return -1;
171                        if (e2.equals(assignment.getValue(request))) return 1;
172                        Double v1 = value(e1), v2 = value(e2);
173                        return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1);
174                    }
175                });
176                return values.iterator();
177            } else {
178                return variable.computeEnrollments(context.getAssignment()).iterator();
179            }
180        }
181        
182        @Override
183        protected void selectNeighbour(Solution<Request, Enrollment> solution, Request variable, BacktrackNeighbourSelectionContext context) {
184            iContext = context;
185            Lock lock = solution.getLock().writeLock();
186            lock.lock();
187            try {
188                exploreEnrollmentSwaps(context, variable);
189            } finally {
190                lock.unlock();
191            }
192        }
193        
194        protected void exploreEnrollmentSwaps(BacktrackNeighbourSelectionContext context, Request variable) {
195            Enrollment current = context.getAssignment().getValue(variable);
196            double currentValue = (current == null ? 0.0 : current.toDouble(context.getAssignment()));
197            for (Iterator<Enrollment> e = values(context, variable); canContinueEvaluation(context) && e.hasNext();) {
198                Enrollment value = e.next();
199                if (value.equals(current)) continue;
200                if (current != null && currentValue <= value.toDouble(context.getAssignment())) continue;
201                if (context.isTimeoutReached() || context.isMaxItersReached()) break;
202                context.incIteration();
203                if (context.getModel().inConflict(context.getAssignment(), value)) {
204                    for (Enrollment other: new ArrayList<Enrollment>(value.getCourse().getContext(context.getAssignment()).getEnrollments())) {
205                        if (other.getStudent().equals(value.getStudent()) || !other.getSections().equals(value.getSections())) continue;
206                        context.getAssignment().unassign(0, other.variable());
207                        if (!context.getModel().inConflict(context.getAssignment(), value)) {
208                            if (current != null)
209                                context.getAssignment().unassign(0, current.variable());
210                            context.getAssignment().assign(0, value);
211                            for (Iterator<Enrollment> f = values(context, other.variable()); canContinueEvaluation(context) && f.hasNext();) {
212                                Enrollment fix = f.next();
213                                if (!context.getModel().inConflict(context.getAssignment(), fix)) {
214                                    context.getAssignment().assign(0, fix);
215                                    context.saveBest(variable, other.variable());
216                                    context.getAssignment().unassign(0, fix.variable());
217                                }
218                            }
219                            if (current == null)
220                                context.getAssignment().unassign(0, variable);
221                            else
222                                context.getAssignment().assign(0, current);
223                        }
224                        context.getAssignment().assign(0, other);
225                    }
226                } else {
227                    if (current != null)
228                        context.getAssignment().unassign(0, current.variable());
229                    context.getAssignment().assign(0, value);
230                    context.saveBest(variable);
231                    if (current == null)
232                        context.getAssignment().unassign(0, variable);
233                    else
234                        context.getAssignment().assign(0, current);
235                }
236            }
237        }        
238    }
239    
240    @Override
241    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
242        if (iNbrIterations > 0)
243            info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" +
244                    iNbrIterations + " iterations, " +
245                    (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") +
246                    sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iSelection.getTimeout() / 1000.0) + " seconds reached)");
247    }
248
249    @Override
250    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
251    }
252}