    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.LinkedList;
    011import java.util.List;
    012import java.util.ListIterator;
    013import java.util.Map;
    014
    015import org.cpsolver.ifs.assignment.Assignment;
    016import org.cpsolver.ifs.heuristics.BacktrackNeighbourSelection;
    017import org.cpsolver.ifs.heuristics.NeighbourSelection;
    018import org.cpsolver.ifs.model.InfoProvider;
    019import org.cpsolver.ifs.model.Neighbour;
    020import org.cpsolver.ifs.solution.Solution;
    021import org.cpsolver.ifs.solver.Solver;
    022import org.cpsolver.ifs.solver.SolverListener;
    023import org.cpsolver.ifs.util.DataProperties;
    024import org.cpsolver.ifs.util.Progress;
    025import org.cpsolver.studentsct.filter.StudentFilter;
    026import org.cpsolver.studentsct.heuristics.RandomizedBacktrackNeighbourSelection;
    027import org.cpsolver.studentsct.model.CourseRequest;
    028import org.cpsolver.studentsct.model.Enrollment;
    029import org.cpsolver.studentsct.model.FreeTimeRequest;
    030import org.cpsolver.studentsct.model.Request;
    031import org.cpsolver.studentsct.model.Request.RequestPriority;
    032import org.cpsolver.studentsct.model.Student.StudentPriority;
    033
    034
    035/**
    036 * Use backtrack neighbour selection. For all unassigned variables (in a random
    037 * order), {@link RandomizedBacktrackNeighbourSelection} is being used.
    038 *
    039 * <br>
    040 * <br>
    041 *
    042 * @author  Tomáš Müller
    043 * @version StudentSct 1.3 (Student Sectioning)<br>
    044 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    045 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    046 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    047 * <br>
    048 *          This library is free software; you can redistribute it and/or modify
    049 *          it under the terms of the GNU Lesser General Public License as
    050 *          published by the Free Software Foundation; either version 3 of the
    051 *          License, or (at your option) any later version. <br>
    052 * <br>
    053 *          This library is distributed in the hope that it will be useful, but
    054 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    055 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    056 *          Lesser General Public License for more details. <br>
    057 * <br>
    058 *          You should have received a copy of the GNU Lesser General Public
    059 *          License along with this library; if not see
    060 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    061 */
    062
    063public class BacktrackSelection implements NeighbourSelection<Request, Enrollment>, InfoProvider<Request, Enrollment>, SolverListener<Request, Enrollment> {
    064    private static DecimalFormat sDF = new DecimalFormat("0.00");
    065    protected RandomizedBacktrackNeighbourSelection iRBtNSel = null;
    066    protected LinkedList<Request> iRequests = null;
    067    protected boolean iIncludeAssignedRequests = false;
    068
    069    protected long iNbrIterations = 0;
    070    protected long iMaxIterations = 0;
    071    protected long iTotalTime = 0;
    072    protected long iNbrTimeoutReached = 0;
    073    protected long iNbrNoSolution = 0;
    074    protected StudentFilter iFilter = null;
    075    protected RequestComparator iRequestComparator = null;
    076    protected Map<Request, Integer> iFailedCounter = new HashMap<Request, Integer>();
    077    protected long iNbrRequests = 0;
    078
    079    public BacktrackSelection(DataProperties properties) {
    080        iIncludeAssignedRequests = properties.getPropertyBoolean("Neighbour.IncludeAssignedRequests", iIncludeAssignedRequests);
    081        iRequestComparator = new RequestComparator(properties);
    082    }
    083
    084    public void init(Solver<Request, Enrollment> solver, String name) {
    085        List<Request> variables = new ArrayList<Request>(iIncludeAssignedRequests ? solver.currentSolution().getModel().variables() : solver.currentSolution().getModel().unassignedVariables(solver.currentSolution().getAssignment()));
    086        Collections.shuffle(variables);
    087        Collections.sort(variables, iRequestComparator);
    088        iRequests = new LinkedList<Request>(variables);
    089        iFailedCounter.clear();
    090        if (iRBtNSel == null) {
    091            try {
    092                iRBtNSel = new RandomizedBacktrackNeighbourSelection(solver.getProperties());
    093                iRBtNSel.init(solver);
    094            } catch (Exception e) {
    095                throw new RuntimeException(e.getMessage(), e);
    096            }
    097        }
    098        Progress.getInstance(solver.currentSolution().getModel()).setPhase(name, variables.size());
    099    }
    100
    101    @Override
    102    public void init(Solver<Request, Enrollment> solver) {
    103        init(solver, "Backtracking" + (iFilter == null ? "" : " (" + iFilter.getName().toLowerCase() + " students)") + "...");
    104
    105        iNbrIterations = 0;
    106        iNbrTimeoutReached = 0;
    107        iNbrNoSolution = 0;
    108        iTotalTime = 0;
    109        iMaxIterations = Math.max(10,  2 * iRequests.size());
    110        iNbrRequests = iRequests.size();
    111    }
    112
    113    protected synchronized Request nextRequest() {
    114        while (true) {
    115            Request request = iRequests.poll();
    116            if (request == null) return null;
    117            if (iFilter == null || iFilter.accept(request.getStudent())) return request;
    118        }
    119    }
    120
    121    public synchronized void addRequest(Request request) {
    122        if (iRequests != null && request != null && !request.getStudent().isDummy()) {
    123            Integer failed = iFailedCounter.getOrDefault(request, 0);
    124            iFailedCounter.put(request, 1 + failed);
    125            if (failed >= 5) return;
    126            if (request.getStudent().getPriority().ordinal() < StudentPriority.Normal.ordinal() || request.getRequestPriority().ordinal() < RequestPriority.Normal.ordinal()) {
    127                for (ListIterator<Request> i = iRequests.listIterator(); i.hasNext();) {
    128                    Request r = i.next();
    129                    if (iRequestComparator.compare(r, request) > 0) {
    130                        i.previous(); // go one back
    131                        i.add(request);
    132                        return;
    133                    }
    134                }
    135            }
    136            iRequests.add(request);
    137        }
    138    }
    139
    140    @Override
    141    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    142        Request request = null;
    143        if (iNbrIterations > iMaxIterations) return null;
    144        while ((request = nextRequest()) != null) {
    145            Progress.getInstance(solution.getModel()).setProgress(iNbrRequests - iRequests.size());
    146            Enrollment e = request.getAssignment(solution.getAssignment());
    147            if (e != null && request instanceof FreeTimeRequest) continue;
    148            if (e != null && e.getPriority() == 0 && ((CourseRequest)request).getSelectedChoices().isEmpty()) continue;
    149            for (int i = 0; i < 5; i++) {
    150                try {
    151                    Neighbour<Request, Enrollment> n = iRBtNSel.selectNeighbour(solution, request);
    152                    if (iRBtNSel.getContext() != null) {
    153                        iNbrIterations ++;
    154                        iTotalTime += iRBtNSel.getContext().getTime();
    155                        if (iRBtNSel.getContext().isTimeoutReached()) iNbrTimeoutReached ++;
    156                        if (n == null) iNbrNoSolution ++;
    157                    }
    158                    if (n != null && n.value(solution.getAssignment()) <= 0.0)
    159                        return n;
    160                    break;
    161                } catch (ConcurrentModificationException ex) {}
    162            }
    163        }
    164        return null;
    165    }
    166
    167    @Override
    168    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
    169        if (iNbrIterations > 0)
    170            info.put("Timing of " + getClass().getSimpleName(), sDF.format(((double)iTotalTime) / iNbrIterations) + " ms/it (" +
    171                    iNbrIterations + " iterations, " +
    172                    (iNbrNoSolution == 0 ? "" : sDF.format(100.0 * iNbrNoSolution / iNbrIterations) + "% no solution, ") +
    173                    sDF.format(100.0 * iNbrTimeoutReached / iNbrIterations) + "% time limit of " + sDF.format(iRBtNSel.getTimeout() / 1000.0) + " seconds reached" +
    174                    (iNbrIterations > iMaxIterations ? ", stopped after " + iNbrIterations + " iterations" : "") +
    175                    ")");
    176    }
    177
    178    @Override
    179    public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
    180    }
    181
    182    /**
    183     * Only consider students meeting the given filter.
    184     */
    185    public StudentFilter getFilter() { return iFilter; }
    186
    187    /**
    188     * Only consider students meeting the given filter.
    189     */
    190    public BacktrackSelection withFilter(StudentFilter filter) { iFilter = filter; return this; }
    191
    192    @Override
    193    public boolean variableSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable) {
    194        return false;
    195    }
    196    @Override
    197    public boolean valueSelected(Assignment<Request, Enrollment> assignment, long iteration, Request variable, Enrollment value) {
    198        return false;
    199    }
    200    @Override
    201    public boolean neighbourSelected(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    202        return false;
    203    }
    204    @Override
    205    public void neighbourFailed(Assignment<Request, Enrollment> assignment, long iteration, Neighbour<Request, Enrollment> neighbour) {
    206        if (neighbour instanceof BacktrackNeighbourSelection.BackTrackNeighbour)
    207            addRequest(((BacktrackNeighbourSelection<Request, Enrollment>.BackTrackNeighbour)neighbour).getAssignments().get(0).getRequest());
    208    }
    209
    210    public static class RequestComparator implements Comparator<Request> {
    211        protected boolean iPreferPriorityStudents = true;
    212        protected RequestComparator(DataProperties properties) {
    213            iPreferPriorityStudents = properties.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true);
    214        }
    215
    216        @Override
    217        public int compare(Request r1, Request r2) {
    218            if (iPreferPriorityStudents) {
    219                if (r1.getStudent().getPriority() != r2.getStudent().getPriority())
    220                    return r1.getStudent().getPriority().compareTo(r2.getStudent().getPriority());
    221                if (r1.getRequestPriority() != r2.getRequestPriority())
    222                    return r1.getRequestPriority().compareTo(r2.getRequestPriority());
    223            } else {
    224                if (r1.getRequestPriority() != r2.getRequestPriority())
    225                    return r1.getRequestPriority().compareTo(r2.getRequestPriority());
    226                if (r1.getRequestPriority() != r2.getRequestPriority())
    227                    return r1.getStudent().getPriority().compareTo(r2.getStudent().getPriority());
    228            }
    229            if (r1.isAlternative() != r2.isAlternative())
    230                return r2.isAlternative() ? -1 : 1;
    231            if (r1.getPriority() != r2.getPriority())
    232                return r1.getPriority() < r2.getPriority() ? -1 : 1;
    233            return 0;
    234        }
    235    }
    236}