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}