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.ListIterator;
014import java.util.Map;
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.solver.SolverListener;
025import org.cpsolver.ifs.util.DataProperties;
026import org.cpsolver.ifs.util.Progress;
027import org.cpsolver.studentsct.StudentSectioningModel;
028import org.cpsolver.studentsct.heuristics.selection.BacktrackSelection.RequestComparator;
029import org.cpsolver.studentsct.model.CourseRequest;
030import org.cpsolver.studentsct.model.Enrollment;
031import org.cpsolver.studentsct.model.Request;
032import org.cpsolver.studentsct.model.Request.RequestPriority;
033import org.cpsolver.studentsct.model.Student.StudentPriority;
034
035/**
036 * Swap enrollments of different students of a course. This is to improve
037 * the enrollment alternativity {@link Enrollment#getPriority()} as well as
038 * selection preferences {@link Enrollment#percentSelected()}. 
039 * 
040 * <br>
041 * <br>
042 * 
043 * @author  Tomáš Müller
044 * @version StudentSct 1.3 (Student Sectioning)<br>
045 *          Copyright (C) 2007 - 2018 Tomáš Müller<br>
046 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
047 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
048 * <br>
049 *          This library is free software; you can redistribute it and/or modify
050 *          it under the terms of the GNU Lesser General Public License as
051 *          published by the Free Software Foundation; either version 3 of the
052 *          License, or (at your option) any later version. <br>
053 * <br>
054 *          This library is distributed in the hope that it will be useful, but
055 *          WITHOUT ANY WARRANTY; without even the implied warranty of
056 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
057 *          Lesser General Public License for more details. <br>
058 * <br>
059 *          You should have received a copy of the GNU Lesser General Public
060 *          License along with this library; if not see
061 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
062 */
063
064public class StudentEnrollmentSwapSelection implements NeighbourSelection<Request, Enrollment>, InfoProvider<Request, Enrollment>, SolverListener<Request, Enrollment> {
065    private static DecimalFormat sDF = new DecimalFormat("0.00");
066    private Selection iSelection = null;
067    protected LinkedList<Request> iRequests = null;
068    
069    protected long iNbrIterations = 0;
070    protected long iTotalTime = 0;
071    protected long iNbrTimeoutReached = 0;
072    protected long iNbrNoSolution = 0;
073    protected RequestComparator iRequestComparator;
074
075    public StudentEnrollmentSwapSelection(DataProperties properties) {
076        iRequestComparator = new RequestComparator(properties);
077    }
078
079    public void init(Solver<Request, Enrollment> solver, String name) {
080        List<Request> variables = new ArrayList<Request>(solver.currentSolution().getModel().assignedVariables(solver.currentSolution().getAssignment()));
081        Collections.shuffle(variables);
082        Collections.sort(variables, iRequestComparator);
083        iRequests = new LinkedList<Request>(variables);
084        if (iSelection == null) {
085            try {
086                iSelection = new Selection(solver.getProperties());
087                iSelection.init(solver);
088            } catch (Exception e) {
089                throw new RuntimeException(e.getMessage(), e);
090            }
091        }
092        Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size());
093        iNbrIterations = 0;
094        iNbrTimeoutReached = 0;
095        iNbrNoSolution = 0;
096        iTotalTime = 0;
097    }
098
099    @Override
100    public void init(Solver<Request, Enrollment> solver) {
101        init(solver, "Enrollment swaps...");
102    }
103    
104    protected synchronized Request nextRequest() {
105        return iRequests.poll();
106    }
107    
108    public synchronized void addRequest(Request request) {
109        if (iRequests != null && request != null && !request.getStudent().isDummy()) {
110            if (request.getStudent().getPriority().ordinal() < StudentPriority.Normal.ordinal() || request.getRequestPriority().ordinal() < RequestPriority.Normal.ordinal()) {
111                for (ListIterator<Request> i = iRequests.listIterator(); i.hasNext();) {
112                    Request r = i.next();
113                    if (iRequestComparator.compare(r, request) > 0) {
114                        i.previous(); // go one back
115                        i.add(request);
116                        return;
117                    }
118                }
119            }
120            iRequests.add(request);
121        }
122    }
123
124    @Override
125    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
126        Request request = null;
127        while ((request = nextRequest()) != null) {
128            Progress p = Progress.getInstance(solution.getModel()); 
129            p.incProgress();
130            if (p.getProgress() > 2.0 * p.getProgressMax()) return null;
131            if (request instanceof CourseRequest) {
132                try {
133                    Enrollment e = request.getAssignment(solution.getAssignment());
134                    if (e == null || e.getPriority() > 0 || !((CourseRequest)request).getSelectedChoices().isEmpty()) {
135                        Neighbour<Request, Enrollment> n = iSelection.selectNeighbour(solution, request);
136                        if (iSelection.getContext() != null) {
137                            iNbrIterations ++;
138                            iTotalTime += iSelection.getContext().getTime();
139                            if (iSelection.getContext().isTimeoutReached()) iNbrTimeoutReached ++;
140                            if (n == null) iNbrNoSolution ++;
141                        }
142                        if (n != null && n.value(solution.getAssignment()) <= 0.0)
143                            return n;
144                    }
145                } catch (ConcurrentModificationException e) {
146                    addRequest(request);
147                }
148            }
149        }
150        return null;
151    }
152    
153    class Selection extends BacktrackNeighbourSelection<Request, Enrollment> {
154        private int iMaxValues = 1000;
155        
156        Selection(DataProperties properties) throws Exception {
157            super(properties);
158            setTimeout(properties.getPropertyInt("Neighbour.EnrollmentSwapTimeout", 500));
159            iMaxValues = properties.getPropertyInt("Neighbour.EnrollmentSwapMaxValues", iMaxValues);
160        }
161        
162        @Override
163        protected Iterator<Enrollment> values(BacktrackNeighbourSelection<Request, Enrollment>.BacktrackNeighbourSelectionContext context, Request variable) {
164            if (variable instanceof CourseRequest) {
165                final CourseRequest request = (CourseRequest)variable;
166                final StudentSectioningModel model = (StudentSectioningModel)context.getModel();
167                final Assignment<Request, Enrollment> assignment = context.getAssignment();
168                List<Enrollment> values = null;
169                Enrollment current = request.getAssignment(context.getAssignment());
170                if (!request.getSelectedChoices().isEmpty() && current != null && current.getPriority() == 0) {
171                    values = request.getSelectedEnrollments(assignment, false);
172                } else {
173                    values = (iMaxValues > 0 ? request.computeRandomEnrollments(assignment, iMaxValues) : request.computeEnrollments(assignment));
174                }
175                Collections.sort(values, new Comparator<Enrollment>() {
176                    private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
177                    private Double value(Enrollment e) {
178                        Double value = iValues.get(e);
179                        if (value == null) {
180                            if (model.getStudentQuality() != null)
181                                value = model.getStudentWeights().getWeight(assignment, e, model.getStudentQuality().conflicts(e));
182                            else
183                                value = model.getStudentWeights().getWeight(assignment, e,
184                                        (model.getDistanceConflict() == null ? null : model.getDistanceConflict().conflicts(e)),
185                                        (model.getTimeOverlaps() == null ? null : model.getTimeOverlaps().conflicts(e)));
186                            iValues.put(e, value);
187                        }
188                        return value;
189                    }
190                    @Override
191                    public int compare(Enrollment e1, Enrollment e2) {
192                        if (e1.equals(assignment.getValue(request))) return -1;
193                        if (e2.equals(assignment.getValue(request))) return 1;
194                        Double v1 = value(e1), v2 = value(e2);
195                        return v1.equals(v2) ? e1.compareTo(assignment, e2) : v2.compareTo(v1);
196                    }
197                });
198                return values.iterator();
199            } else {
200                return variable.computeEnrollments(context.getAssignment()).iterator();
201            }
202        }
203        
204        @Override
205        protected void selectNeighbour(Solution<Request, Enrollment> solution, Request variable, BacktrackNeighbourSelectionContext context) {
206            iContext = context;
207            Lock lock = solution.getLock().writeLock();
208            lock.lock();
209            try {
210                exploreEnrollmentSwaps(context, variable);
211            } finally {
212                lock.unlock();
213            }
214        }
215        
216        protected void exploreEnrollmentSwaps(BacktrackNeighbourSelectionContext context, Request variable) {
217            Enrollment current = context.getAssignment().getValue(variable);
218            double currentValue = (current == null ? 0.0 : current.toDouble(context.getAssignment()));
219            for (Iterator<Enrollment> e = values(context, variable); canContinueEvaluation(context) && e.hasNext();) {
220                Enrollment value = e.next();
221                if (value.equals(current)) continue;
222                if (current != null && currentValue <= value.toDouble(context.getAssignment())) continue;
223                if (context.isTimeoutReached() || context.isMaxItersReached()) break;
224                context.incIteration();
225                if (context.getModel().inConflict(context.getAssignment(), value)) {
226                    for (Enrollment other: new ArrayList<Enrollment>(value.getCourse().getContext(context.getAssignment()).getEnrollments())) {
227                        if (other.getStudent().equals(value.getStudent()) || !other.getSections().equals(value.getSections())) continue;
228                        context.getAssignment().unassign(0, other.variable());
229                        if (!context.getModel().inConflict(context.getAssignment(), value)) {
230                            if (current != null)
231                                context.getAssignment().unassign(0, current.variable());
232                            context.getAssignment().assign(0, value);
233                            for (Iterator<Enrollment> f = values(context, other.variable()); canContinueEvaluation(context) && f.hasNext();) {
234                                Enrollment fix = f.next();
235                                if (!context.getModel().inConflict(context.getAssignment(), fix)) {
236                                    context.getAssignment().assign(0, fix);
237                                    context.saveBest(variable, other.variable());
238                                    context.getAssignment().unassign(0, fix.variable());
239                                }
240                            }
241                            if (current == null)
242                                context.getAssignment().unassign(0, variable);
243                            else
244                                context.getAssignment().assign(0, current);
245                        }
246                        context.getAssignment().assign(0, other);
247                    }
248                } else {
249                    if (current != null)
250                        context.getAssignment().unassign(0, current.variable());
251                    context.getAssignment().assign(0, value);
252                    context.saveBest(variable);
253                    if (current == null)
254                        context.getAssignment().unassign(0, variable);
255                    else
256                        context.getAssignment().assign(0, current);
257                }
258            }
259        }        
260    }
261    
262    @Override
263    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
264        if (iNbrIterations > 0)
265            info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" +
266                    iNbrIterations + " iterations, " +
267                    (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") +
268                    sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iSelection.getTimeout() / 1000.0) + " seconds reached)");
269    }
270
271    @Override
272    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
273    }
274    
275    @Override
276    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
277        return false;
278    }
279    @Override
280    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
281        return false;
282    }
283    @Override
284    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
285        return false;
286    }
287    @Override
288    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
289        if (neighbour instanceof BacktrackNeighbourSelection.BackTrackNeighbour)
290            addRequest(((BacktrackNeighbourSelection<Request, Enrollment>.BackTrackNeighbour)neighbour).getAssignments().get(0).getRequest());
291    }
292}