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