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