001package org.cpsolver.coursett.sectioning;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.Comparator;
006import java.util.HashSet;
007import java.util.List;
008import java.util.Set;
009import java.util.TreeSet;
010
011import org.cpsolver.coursett.constraint.JenrlConstraint;
012import org.cpsolver.coursett.criteria.StudentConflict;
013import org.cpsolver.coursett.custom.DeterministicStudentSectioning.DeterministicInitialSectioning;
014import org.cpsolver.coursett.model.Configuration;
015import org.cpsolver.coursett.model.DefaultStudentSectioning;
016import org.cpsolver.coursett.model.InitialSectioning.Group;
017import org.cpsolver.coursett.model.Lecture;
018import org.cpsolver.coursett.model.Placement;
019import org.cpsolver.coursett.model.Student;
020import org.cpsolver.coursett.model.TimetableModel;
021import org.cpsolver.coursett.sectioning.SctModel.SctSolution;
022import org.cpsolver.ifs.assignment.Assignment;
023import org.cpsolver.ifs.criteria.Criterion;
024import org.cpsolver.ifs.model.InfoProvider;
025import org.cpsolver.ifs.solution.Solution;
026import org.cpsolver.ifs.termination.TerminationCondition;
027import org.cpsolver.ifs.util.Progress;
028
029/**
030 * 
031 * Student sectioning implementation based on branch & bound. This sectioning takes
032 * each offering one by one and it is using a branch & bound algorithm to find
033 * the best possible enrollment of all students into the given course. The sectioning
034 * considers both student conflict weights and student groups.
035 * 
036 * @author  Tomáš Müller
037 * @version CourseTT 1.3 (University Course Timetabling)<br>
038 *          Copyright (C) 2017 Tomáš Müller<br>
039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 *          This library is free software; you can redistribute it and/or modify
043 *          it under the terms of the GNU Lesser General Public License as
044 *          published by the Free Software Foundation; either version 3 of the
045 *          License, or (at your option) any later version. <br>
046 * <br>
047 *          This library is distributed in the hope that it will be useful, but
048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
050 *          Lesser General Public License for more details. <br>
051 * <br>
052 *          You should have received a copy of the GNU Lesser General Public
053 *          License along with this library; if not see
054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
055 */
056public class SctSectioning extends DefaultStudentSectioning implements InfoProvider<Lecture, Placement> {
057    private boolean iUseCriteria = true;
058    private int iNrRounds = 3;
059    private List<StudentConflict> iStudentConflictCriteria = null;
060
061    public SctSectioning(TimetableModel model) {
062        super(model);
063        iUseCriteria = model.getProperties().getPropertyBoolean("SctSectioning.UseCriteria", true);
064        iNrRounds = model.getProperties().getPropertyInt("SctSectioning.NrRounds", 3);
065    }
066    
067    @Override
068    public boolean hasFinalSectioning() {
069        return true;
070    }
071    
072    /**
073     * List of student conflict criteria
074     */
075    protected List<StudentConflict> getStudentConflictCriteria() {
076        if (!iUseCriteria) return null;
077        if (iStudentConflictCriteria == null && iModel != null) {
078            iStudentConflictCriteria = new ArrayList<StudentConflict>();
079            for (Criterion<Lecture, Placement> criterion: iModel.getCriteria())
080                if (criterion instanceof StudentConflict)
081                    iStudentConflictCriteria.add((StudentConflict)criterion);
082        }
083        return iStudentConflictCriteria;
084    }
085    
086    /**
087     * Student conflict weight for the given solution
088     */
089    protected double value(Solution<Lecture, Placement> solution) {
090        List<StudentConflict> criteria = getStudentConflictCriteria();
091        
092        if (criteria == null) {
093            double value = 0.0;
094            for (JenrlConstraint constraint: ((TimetableModel)solution.getModel()).getJenrlConstraints()) {
095                if (constraint.isInConflict(solution.getAssignment())) value += constraint.jenrl();
096            }
097            return value;
098        }
099        
100        double value = 0.0;
101        for (StudentConflict criterion: criteria)
102            value += criterion.getWeightedValue(solution.getAssignment());
103        return value;
104    }
105    
106    @Override
107    public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) {
108        getProgress().setStatus("Student Sectioning...");
109        getProgress().info("Student Conflicts: " + sDF2.format(value(solution)) + " (group: " + sDF2.format(StudentSwapSectioning.gp(solution)) + "%)");
110
111        for (int i = 1; i <= iNrRounds; i++) {
112            getProgress().setPhase("Swapping students [" + i + "]...", iModel.variables().size());
113            Set<Long> offeringIds = new HashSet<Long>();
114            for (Lecture lecture: iModel.variables()) {
115                getProgress().incProgress();
116                if (lecture.students().isEmpty() || lecture.isSingleSection()) continue;
117                if (termination != null && !termination.canContinue(solution)) return;
118                if (offeringIds.add(lecture.getConfiguration().getOfferingId())) {
119                    SctModel model = new SctModel(iModel, solution.getAssignment());
120                    model.setConfiguration(lecture.getConfiguration());
121                    SctSolution s1 = model.currentSolution();
122                    SctSolution s2 = model.computeSolution();
123                    if (model.isTimeOutReached())
124                        getProgress().info("Timeout reached for " + lecture.getName());
125                    if (s2.isBetter(s1)) {
126                        model.unassign();
127                        model.assign(s2);
128                        getProgress().info("Student Conflicts: " + sDF2.format(value(solution)) + " (group: " + sDF2.format(StudentSwapSectioning.gp(solution)) + "%)");
129                    }
130                }
131            }
132            getProgress().info("Student Conflicts: " + sDF2.format(value(solution)) + " (group: " + sDF2.format(StudentSwapSectioning.gp(solution)) + "%)");
133        }
134    }
135
136    @Override
137    public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) {
138        SctModel model = new SctModel(iModel, assignment);
139        model.setConfiguration(lecture.getConfiguration());
140        SctSolution s1 = model.currentSolution();
141        SctSolution s2 = model.computeSolution();
142        if (s2.isBetter(s1)) {
143            model.unassign();
144            model.assign(s2);
145        }
146    }
147    
148    protected boolean hasStudentGroups(Collection<Student> students) {
149        for (Student student: students)
150            if (!student.getGroups().isEmpty()) return true;
151        return false;
152    }
153    
154    @Override
155    protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) {
156        if (hasStudentGroups(students)) {
157            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, configurations, students);
158            return sect.getGroups();
159        } else {
160            return super.studentsToConfigurations(offeringId, students, configurations);
161        }
162    }
163    
164    @Override
165    protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) {
166        if (hasStudentGroups(students)) {
167            Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() {
168                @Override
169                public int compare(Lecture l1, Lecture l2) {
170                    return l1.getClassId().compareTo(l2.getClassId());
171                }
172            });
173            sortedLectures.addAll(lectures);
174            GroupBasedInitialSectioning sect = new GroupBasedInitialSectioning(getProgress(), offeringId, sortedLectures, students);
175            return sect.getGroups();
176        } else {
177            return super.studentsToLectures(offeringId, students, lectures);
178        }
179    }
180    
181    protected static class GroupBasedInitialSectioning extends DeterministicInitialSectioning {
182        public GroupBasedInitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations, Collection<Student> students) {
183            super(progress, offeringId, lectureOrConfigurations, students);
184        }
185        
186        @Override
187        public int compare(Student s1, Student s2) {
188            int cmp = s1.getGroupNames().compareToIgnoreCase(s2.getGroupNames());
189            if (cmp != 0) return cmp;
190            return super.compare(s1, s2);
191        }
192    }
193}