    001package org.cpsolver.studentsct.heuristics.selection;
    002
    003import org.cpsolver.ifs.assignment.Assignment;
    004import org.cpsolver.ifs.model.Neighbour;
    005import org.cpsolver.ifs.solution.Solution;
    006import org.cpsolver.ifs.solver.Solver;
    007import org.cpsolver.ifs.util.DataProperties;
    008import org.cpsolver.ifs.util.Progress;
    009import org.cpsolver.studentsct.heuristics.studentord.StudentChoiceOrder;
    010import org.cpsolver.studentsct.model.CourseRequest;
    011import org.cpsolver.studentsct.model.Enrollment;
    012import org.cpsolver.studentsct.model.Request;
    013import org.cpsolver.studentsct.model.Student;
    014import org.cpsolver.studentsct.model.Request.RequestPriority;
    015
    016/**
    017 * This selection is very much like {@link BranchBoundSelection}, but only critical
    018 * course requests are assigned (see {@link CourseRequest#isCritical()}.
    019 * Students that do not have any unassigned critical courses are skipped.
    020 *
    021 * <br>
    022 * <br>
    023 * Parameters: <br>
    024 * <table border='1'><caption>Related Solver Parameters</caption>
    025 * <tr>
    026 * <th>Parameter</th>
    027 * <th>Type</th>
    028 * <th>Comment</th>
    029 * </tr>
    030 * <tr>
    031 * <td>Neighbour.CriticalCoursesBranchAndBoundTimeout</td>
    032 * <td>{@link Integer}</td>
    033 * <td>Timeout for each neighbour selection (in milliseconds).</td>
    034 * </tr>
    035 * <tr>
    036 * <td>Neighbour.BranchAndBoundMinimizePenalty</td>
    037 * <td>{@link Boolean}</td>
    038 * <td>If true, section penalties (instead of section values) are minimized:
    039 * overall penalty is minimized together with the maximization of the number of
    040 * assigned requests and minimization of distance conflicts -- this variant is
    041 * to better mimic the case when students can choose their sections (section
    042 * times).</td>
    043 * </tr>
    044 * </table>
    045 * <br>
    046 * <br>
    047 *
    048 * @author  Tomáš Müller
    049 * @version StudentSct 1.3 (Student Sectioning)<br>
    050 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    051 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    052 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    053 * <br>
    054 *          This library is free software; you can redistribute it and/or modify
    055 *          it under the terms of the GNU Lesser General Public License as
    056 *          published by the Free Software Foundation; either version 3 of the
    057 *          License, or (at your option) any later version. <br>
    058 * <br>
    059 *          This library is distributed in the hope that it will be useful, but
    060 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    061 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    062 *          Lesser General Public License for more details. <br>
    063 * <br>
    064 *          You should have received a copy of the GNU Lesser General Public
    065 *          License along with this library; if not see
    066 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    067 */
    068public class CriticalCoursesBranchAndBoundSelection extends BranchBoundSelection {
    069    protected boolean iMPP = false;
    070    private RequestPriority iPriority;
    071
    072    public CriticalCoursesBranchAndBoundSelection(DataProperties properties, RequestPriority priority) {
    073        super(properties);
    074        iMPP = properties.getPropertyBoolean("General.MPP", false);
    075        iTimeout = properties.getPropertyInt("Neighbour.CriticalCoursesBranchAndBoundTimeout", 10000);
    076        iPriority = priority;
    077        if (iOrder instanceof StudentChoiceOrder) {
    078            ((StudentChoiceOrder)iOrder).setCriticalOnly(true);
    079            ((StudentChoiceOrder)iOrder).setRequestPriority(iPriority);
    080        }
    081    }
    082
    083    public CriticalCoursesBranchAndBoundSelection(DataProperties properties) {
    084        this(properties, RequestPriority.Critical);
    085    }
    086
    087    @Override
    088    public void init(Solver<Request, Enrollment> solver) {
    089        init(solver, iPriority.name() + " Courses B&B" + (iFilter == null ? "" : " (" + iFilter.getName().toLowerCase() + " students)") + "...");
    090    }
    091
    092    @Override
    093    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
    094        Student student = null;
    095        while ((student = nextStudent()) != null) {
    096            Progress.getInstance(solution.getModel()).incProgress();
    097            if (student.hasUnassignedCritical(solution.getAssignment(), iPriority)) {
    098                // only consider students that have some unassigned critical course requests
    099                Neighbour<Request, Enrollment> neighbour = getSelection(solution.getAssignment(), student).select();
    100                if (neighbour != null) return neighbour;
    101            }
    102        }
    103        return null;
    104    }
    105
    106    @Override
    107    public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) {
    108        return new CriticalCoursesSelection(student, assignment);
    109    }
    110
    111    public class CriticalCoursesSelection extends Selection {
    112
    113        public CriticalCoursesSelection(Student student, Assignment<Request, Enrollment> assignment) {
    114            super(student, assignment);
    115        }
    116
    117        public boolean isCritical(int idx) {
    118            for (int i = idx; i < iStudent.getRequests().size(); i++) {
    119                Request r = iStudent.getRequests().get(i);
    120                if (!r.isAlternative() && iPriority.isCritical(r)) return true;
    121            }
    122            return false;
    123        }
    124
    125        @Override
    126        public void backTrack(int idx) {
    127            if (!isCritical(idx)) {
    128                if (iMinimizePenalty) {
    129                    if (getBestAssignment() == null || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue())))
    130                        saveBest();
    131                } else {
    132                    if (getBestAssignment() == null || getValue() < getBestValue())
    133                        saveBest();
    134                }
    135                return;
    136            }
    137            if (idx < iAssignment.length && !iPriority.isCritical(iStudent.getRequests().get(idx)) && (!iMPP || iStudent.getRequests().get(idx).getInitialAssignment() == null)) {
    138                // not done yet && not critical && not initial >> leave unassigned
    139                backTrack(idx + 1);
    140            } else {
    141                super.backTrack(idx);
    142            }
    143        }
    144    }
    145}