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