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;
014
015/**
016 * This selection is very much like {@link BranchBoundSelection}, but only critical
017 * course requests are assigned (see {@link CourseRequest#isCritical()}.
018 * Students that do not have any unassigned critical courses are skipped.
019 * 
020 * <br>
021 * <br>
022 * Parameters: <br>
023 * <table border='1' summary='Related Solver Parameters'>
024 * <tr>
025 * <th>Parameter</th>
026 * <th>Type</th>
027 * <th>Comment</th>
028 * </tr>
029 * <tr>
030 * <td>Neighbour.CriticalCoursesBranchAndBoundTimeout</td>
031 * <td>{@link Integer}</td>
032 * <td>Timeout for each neighbour selection (in milliseconds).</td>
033 * </tr>
034 * <tr>
035 * <td>Neighbour.BranchAndBoundMinimizePenalty</td>
036 * <td>{@link Boolean}</td>
037 * <td>If true, section penalties (instead of section values) are minimized:
038 * overall penalty is minimized together with the maximization of the number of
039 * assigned requests and minimization of distance conflicts -- this variant is
040 * to better mimic the case when students can choose their sections (section
041 * times).</td>
042 * </tr>
043 * </table>
044 * <br>
045 * <br>
046 * 
047 * @version StudentSct 1.3 (Student Sectioning)<br>
048 *          Copyright (C) 2007 - 2014 Tomas Muller<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 CriticalCoursesBranchAndBoundSelection extends BranchBoundSelection {
067    protected boolean iMPP = false;
068    
069    public CriticalCoursesBranchAndBoundSelection(DataProperties properties) {
070        super(properties);
071        iMPP = properties.getPropertyBoolean("General.MPP", false);
072        iTimeout = properties.getPropertyInt("Neighbour.CriticalCoursesBranchAndBoundTimeout", 10000);
073        if (iOrder instanceof StudentChoiceOrder)
074            ((StudentChoiceOrder)iOrder).setCriticalOnly(true);
075    }
076    
077    @Override
078    public void init(Solver<Request, Enrollment> solver) {
079        init(solver, "Critical Courses B&B...");
080    }
081    
082    @Override
083    public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
084        Student student = null;
085        while ((student = nextStudent()) != null) {
086            Progress.getInstance(solution.getModel()).incProgress();
087            if (student.hasUnassignedCritical(solution.getAssignment())) {
088                // only consider students that have some unassigned critical course requests
089                Neighbour<Request, Enrollment> neighbour = getSelection(solution.getAssignment(), student).select();
090                if (neighbour != null) return neighbour;
091            }
092        }
093        return null;
094    }
095    
096    @Override
097    public Selection getSelection(Assignment<Request, Enrollment> assignment, Student student) {
098        return new CriticalCoursesSelection(student, assignment);
099    }
100    
101    public class CriticalCoursesSelection extends Selection {
102        
103        public CriticalCoursesSelection(Student student, Assignment<Request, Enrollment> assignment) {
104            super(student, assignment);
105        }
106        
107        public boolean isCritical(int idx) {
108            for (int i = idx; i < iStudent.getRequests().size(); i++) {
109                Request r = iStudent.getRequests().get(i);
110                if (!r.isAlternative() && r.isCritical()) return true;
111            }
112            return false;
113        }
114        
115        @Override
116        public void backTrack(int idx) {
117            if (!isCritical(idx)) {
118                if (iMinimizePenalty) {
119                    if (getBestAssignment() == null || (getNrAssigned() > getBestNrAssigned() || (getNrAssigned() == getBestNrAssigned() && getPenalty() < getBestValue())))
120                        saveBest();
121                } else {
122                    if (getBestAssignment() == null || getValue() < getBestValue())
123                        saveBest();
124                }
125                return;
126            }
127            if (idx < iAssignment.length && !iStudent.getRequests().get(idx).isCritical() && (!iMPP || iStudent.getRequests().get(idx).getInitialAssignment() == null)) {
128                // not done yet && not critical && not initial >> leave unassigned
129                backTrack(idx + 1);
130            } else {
131                super.backTrack(idx);
132            }
133        }
134    }
135}