    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                boolean hasChildren = (value.getCourse() != null && value.getCourse().hasChildren());
    223                if (current != null && currentValue <= value.toDouble(context.getAssignment())) continue;
    224                if (context.isTimeoutReached() || context.isMaxItersReached()) break;
    225                context.incIteration();
    226                if (context.getModel().inConflict(context.getAssignment(), value)) {
    227                    other: for (Enrollment other: new ArrayList<Enrollment>(value.getCourse().getContext(context.getAssignment()).getEnrollments())) {
    228                        if (other.getStudent().equals(value.getStudent()) || !other.getSections().equals(value.getSections())) continue;
    229                        if (hasChildren) {
    230                            for (Request r: other.getStudent().getRequests()) {
    231                                if (r.equals(other.getRequest())) continue;
    232                                Enrollment f = context.getAssignment().getValue(r);
    233                                if (f != null && f.getCourse() != null && value.getCourse().equals(f.getCourse().getParent())) {
    234                                    continue other;
    235                                }
    236                            }
    237                        }
    238                        context.getAssignment().unassign(0, other.variable());
    239                        if (!context.getModel().inConflict(context.getAssignment(), value)) {
    240                            if (current != null)
    241                                context.getAssignment().unassign(0, current.variable());
    242                            context.getAssignment().assign(0, value);
    243                            for (Iterator<Enrollment> f = values(context, other.variable()); canContinueEvaluation(context) && f.hasNext();) {
    244                                Enrollment fix = f.next();
    245                                if (!context.getModel().inConflict(context.getAssignment(), fix)) {
    246                                    context.getAssignment().assign(0, fix);
    247                                    context.saveBest(variable, other.variable());
    248                                    context.getAssignment().unassign(0, fix.variable());
    249                                }
    250                            }
    251                            if (current == null)
    252                                context.getAssignment().unassign(0, variable);
    253                            else
    254                                context.getAssignment().assign(0, current);
    255                        }
    256                        context.getAssignment().assign(0, other);
    257                    }
    258                } else {
    259                    if (current != null)
    260                        context.getAssignment().unassign(0, current.variable());
    261                    context.getAssignment().assign(0, value);
    262                    context.saveBest(variable);
    263                    if (current == null)
    264                        context.getAssignment().unassign(0, variable);
    265                    else
    266                        context.getAssignment().assign(0, current);
    267                }
    268            }
    269        }
    270    }
    271
    272    @Override
    273    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
    274        if (iNbrIterations > 0)
    275            info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" +
    276                    iNbrIterations + " iterations, " +
    277                    (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") +
    278                    sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iSelection.getTimeout() / 1000.0) + " seconds reached)");
    279    }
    280
    281    @Override
    282    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
    283    }
    284
    285    @Override
    286    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
    287        return false;
    288    }
    289    @Override
    290    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
    291        return false;
    292    }
    293    @Override
    294    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    295        return false;
    296    }
    297    @Override
    298    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    299        if (neighbour instanceof BacktrackNeighbourSelection.BackTrackNeighbour)
    300            addRequest(((BacktrackNeighbourSelection<Request, Enrollment>.BackTrackNeighbour)neighbour).getAssignments().get(0).getRequest());
    301    }
    302}