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