    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.HashSet;
    004import java.util.Set;
    005
    006import org.cpsolver.coursett.criteria.StudentConflict;
    007import org.cpsolver.coursett.model.Lecture;
    008import org.cpsolver.coursett.model.Placement;
    009import org.cpsolver.coursett.model.Student;
    010import org.cpsolver.coursett.model.TimetableModel;
    011import org.cpsolver.ifs.assignment.Assignment;
    012import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
    013import org.cpsolver.ifs.assignment.context.BinaryConstraintWithContext;
    014import org.cpsolver.ifs.criteria.Criterion;
    015import org.cpsolver.ifs.model.Model;
    016import org.cpsolver.ifs.model.WeakeningConstraint;
    017import org.cpsolver.ifs.util.DataProperties;
    018import org.cpsolver.ifs.util.DistanceMetric;
    019import org.cpsolver.ifs.util.ToolBox;
    020
    021
    022/**
    023 * Join student enrollment constraint. <br>
    024 * This constraint is placed between all pairs of classes where there is at
    025 * least one student attending both classes. It represents a number of student
    026 * conflicts (number of joined enrollments), if the given two classes overlap in
    027 * time. <br>
    028 * Also, it dynamically maintains the counter of all student conflicts. It is a
    029 * soft constraint.
    030 *
    031 *
    032 * @version CourseTT 1.3 (University Course Timetabling)<br>
    033 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
    034 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    035 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    036 * <br>
    037 *          This library is free software; you can redistribute it and/or modify
    038 *          it under the terms of the GNU Lesser General Public License as
    039 *          published by the Free Software Foundation; either version 3 of the
    040 *          License, or (at your option) any later version. <br>
    041 * <br>
    042 *          This library is distributed in the hope that it will be useful, but
    043 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    044 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    045 *          Lesser General Public License for more details. <br>
    046 * <br>
    047 *          You should have received a copy of the GNU Lesser General Public
    048 *          License along with this library; if not see
    049 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    050 */
    051
    052public class JenrlConstraint extends BinaryConstraintWithContext<Lecture, Placement, JenrlConstraint.JenrlConstraintContext> implements WeakeningConstraint<Lecture, Placement> {
    053    private double iJenrl = 0.0;
    054    private double iPriority = 0.0;
    055    private Set<Student> iStudents = new HashSet<Student>();
    056    private Set<Student> iInstructors = new HashSet<Student>();
    057    private double iJenrlMaxConflicts = 1.0;
    058    private double iJenrlMaxConflictsWeaken = 0.001;
    059
    060    /**
    061     * Constructor
    062     */
    063    public JenrlConstraint() {
    064        super();
    065    }
    066
    067    @Override
    068    public void setModel(Model<Lecture, Placement> model) {
    069        super.setModel(model);
    070        if (model != null && model instanceof TimetableModel) {
    071            DataProperties config = ((TimetableModel)model).getProperties();
    072            iJenrlMaxConflicts = config.getPropertyDouble("General.JenrlMaxConflicts", 1.0);
    073            iJenrlMaxConflictsWeaken = config.getPropertyDouble("General.JenrlMaxConflictsWeaken", 0.001);
    074        }
    075    }
    076
    077    @Override
    078    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    079        if (!getContext(assignment).isOverLimit() || value.variable().isCommitted()) return;
    080        Lecture other = another(value.variable());
    081        if (other == null) return;
    082        Placement otherPlacement = assignment.getValue(other);
    083        if (otherPlacement != null && !other.isCommitted() && isInConflict(value, otherPlacement, getDistanceMetric(), getWorkDayLimit()))
    084            conflicts.add(otherPlacement);
    085    }
    086
    087    @Override
    088    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
    089        if (!getContext(assignment).isOverLimit() || value.variable().isCommitted()) return false;
    090        Lecture other = another(value.variable());
    091        if (other == null) return false;
    092        Placement otherPlacement = assignment.getValue(other);
    093        return otherPlacement != null && !other.isCommitted() && isInConflict(value, otherPlacement, getDistanceMetric(), getWorkDayLimit());
    094    }
    095
    096    /**
    097     * Returns true if the given placements are overlapping or they are
    098     * back-to-back and too far for students.
    099     * @param p1 first placement
    100     * @param p2 second placement
    101     * @param m distance metrics
    102     * @param workDayLimit limit on the work-day
    103     * @return true if there is a student conflict between the two placements
    104     */
    105    public static boolean isInConflict(Placement p1, Placement p2, DistanceMetric m, int workDayLimit) {
    106        return p1 != null && p2 != null && !StudentConflict.ignore(p1.variable(), p2.variable()) && (StudentConflict.distance(m, p1, p2) || StudentConflict.overlaps(p1, p2) || StudentConflict.workday(workDayLimit, p1, p2));
    107    }
    108
    109    /**
    110     * Number of joined enrollments if the given value is assigned to the given
    111     * variable
    112     * @param assignment current assignment
    113     * @param variable a class
    114     * @param value class placement under consideration
    115     * @return number of student conflicts caused by this constraint if assigned
    116     */
    117    public long jenrl(Assignment<Lecture, Placement> assignment, Lecture variable, Placement value) {
    118        Lecture other = (first().equals(variable) ? second() : first());
    119        Placement otherPlacement = (other == null ? null : assignment.getValue(other));
    120        return (otherPlacement != null && isInConflict(value, otherPlacement, getDistanceMetric(), getWorkDayLimit()) ? Math.round(iJenrl) : 0);
    121    }
    122
    123    private DistanceMetric getDistanceMetric() {
    124        return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric());
    125    }
    126
    127    private int getWorkDayLimit() {
    128        return (getModel() == null ? -1 : ((TimetableModel)getModel()).getStudentWorkDayLimit());
    129    }
    130
    131    /** True if the given two lectures overlap in time
    132     * @param assignment current assignment
    133     * @return true if this constraint is conflicting
    134     **/
    135    public boolean isInConflict(Assignment<Lecture, Placement> assignment) {
    136        return getContext(assignment).isConflicting();
    137    }
    138
    139    /**
    140     * Increment the number of joined enrollments (during student final
    141     * sectioning)
    142     * @param assignment current assignment
    143     * @param student student added in between the two classes of this constraint
    144     */
    145    public void incJenrl(Assignment<Lecture, Placement> assignment, Student student) {
    146        JenrlConstraintContext context = getContext(assignment);
    147        boolean hard = context.isOverLimit();
    148        double jenrlWeight = student.getJenrlWeight(first(), second());
    149        iJenrl += jenrlWeight;
    150        Double conflictPriority = student.getConflictingPriorty(first(), second());
    151        if (conflictPriority != null) iPriority += conflictPriority * jenrlWeight;
    152        iStudents.add(student);
    153        if (student.getInstructor() != null && (student.getInstructor().variables().contains(first()) ||
    154                student.getInstructor().variables().contains(second())))
    155            iInstructors.add(student);
    156        for (Criterion<Lecture, Placement> criterion: getModel().getCriteria())
    157            if (criterion instanceof StudentConflict)
    158                ((StudentConflict)criterion).incJenrl(assignment, this, jenrlWeight, conflictPriority, student);
    159        if (!hard && context.isOverLimit() && isInConflict(assignment)) {
    160            context.incLimit(jenrlWeight);
    161        }
    162    }
    163
    164    public double getJenrlWeight(Student student) {
    165        return student.getJenrlWeight(first(), second());
    166    }
    167
    168    /**
    169     * Decrement the number of joined enrollments (during student final
    170     * sectioning)
    171     * @param assignment current assignment
    172     * @param student student removed from between the two classes of this constraint
    173     */
    174    public void decJenrl(Assignment<Lecture, Placement> assignment, Student student) {
    175        JenrlConstraintContext context = getContext(assignment);
    176        boolean hard = context.isOverLimit();
    177        double jenrlWeight = student.getJenrlWeight(first(), second());
    178        iJenrl -= jenrlWeight;
    179        Double conflictPriority = student.getConflictingPriorty(first(), second());
    180        if (conflictPriority != null) iPriority -= conflictPriority * jenrlWeight;
    181        iStudents.remove(student);
    182        iInstructors.remove(student);
    183        for (Criterion<Lecture, Placement> criterion: getModel().getCriteria())
    184            if (criterion instanceof StudentConflict)
    185                ((StudentConflict)criterion).incJenrl(assignment, this, -jenrlWeight, conflictPriority, student);
    186        if (hard && !context.isOverLimit())
    187            context.decLimit(jenrlWeight);
    188    }
    189
    190    /** Number of joined enrollments (during student final sectioning)
    191     * @return number of joined enrollments
    192     **/
    193    public long getJenrl() {
    194        return Math.round(iJenrl);
    195    }
    196
    197    public double jenrl() {
    198        return iJenrl;
    199    }
    200
    201    public double priority() {
    202        return iPriority;
    203    }
    204
    205    public int getNrStudents() {
    206        return iStudents.size();
    207    }
    208
    209    public Set<Student> getStudents() {
    210        return iStudents;
    211    }
    212
    213    public int getNrInstructors() {
    214        return iInstructors.size();
    215    }
    216
    217    public Set<Student> getInstructors() {
    218        return iInstructors;
    219    }
    220
    221    @Override
    222    public boolean isHard() {
    223        return true;
    224    }
    225
    226    @Override
    227    public String getName() {
    228        return "Join Enrollment";
    229    }
    230
    231    @Override
    232    public String toString() {
    233        return "Join Enrollment between " + first().getName() + " and " + second().getName();
    234    }
    235
    236    public boolean areStudentConflictsHard() {
    237        return StudentConflict.hard(first(), second());
    238    }
    239
    240    public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment) {
    241        return StudentConflict.distance(getDistanceMetric(), assignment.getValue(first()), assignment.getValue(second()));
    242    }
    243
    244    public boolean areStudentConflictsCommitted() {
    245        return StudentConflict.committed(first(), second());
    246    }
    247
    248    public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment, Placement value) {
    249        return StudentConflict.distance(getDistanceMetric(), value, assignment.getValue(another(value.variable())));
    250    }
    251
    252    public boolean areStudentConflictsWorkday(Assignment<Lecture, Placement> assignment, Placement value) {
    253        return StudentConflict.workday(getWorkDayLimit(), value, assignment.getValue(another(value.variable())));
    254    }
    255
    256    public boolean isOfTheSameProblem() {
    257        return ToolBox.equals(first().getSolverGroupId(), second().getSolverGroupId());
    258    }
    259
    260    @Override
    261    public void weaken(Assignment<Lecture, Placement> assignment) {
    262        getContext(assignment).weaken();
    263    }
    264
    265    @Override
    266    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
    267        getContext(assignment).weaken(assignment, value);
    268    }
    269
    270    /**
    271     * Returns true if there is {@link IgnoreStudentConflictsConstraint} between the two lectures.
    272     * @return true if this constraint is to be ignored
    273     */
    274    public boolean isToBeIgnored() {
    275        return first().isToIgnoreStudentConflictsWith(second());
    276    }
    277
    278    @Override
    279    public JenrlConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    280        return new JenrlConstraintContext(assignment);
    281    }
    282
    283    public class JenrlConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
    284        private boolean iAdded = false;
    285        private Double iJenrlLimit = null;
    286        private double iTwiggle = 0.0;
    287
    288        public JenrlConstraintContext(Assignment<Lecture, Placement> assignment) {
    289            Placement p1 = assignment.getValue(first());
    290            Placement p2 = assignment.getValue(second());
    291            if (p1 != null && p2 != null && isInConflict(p1, p2, getDistanceMetric(), getWorkDayLimit())) {
    292                iAdded = true;
    293                first().addActiveJenrl(assignment, JenrlConstraint.this);
    294                second().addActiveJenrl(assignment, JenrlConstraint.this);
    295            }
    296            if (iJenrlMaxConflicts >= 0.0 && iJenrlMaxConflicts < 1.0)
    297                iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * iJenrlMaxConflicts;
    298        }
    299
    300        @Override
    301        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    302            Lecture other = another(value.variable());
    303            if (other == null) return;
    304            Placement otherValue = assignment.getValue(other);
    305            if (!iAdded && otherValue != null && isInConflict(value, otherValue, getDistanceMetric(), getWorkDayLimit())) {
    306                iAdded = true;
    307                first().addActiveJenrl(assignment, JenrlConstraint.this);
    308                second().addActiveJenrl(assignment, JenrlConstraint.this);
    309            }
    310        }
    311
    312        @Override
    313        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    314            if (iAdded) {
    315                iAdded = false;
    316                first().removeActiveJenrl(assignment, JenrlConstraint.this);
    317                second().removeActiveJenrl(assignment, JenrlConstraint.this);
    318            }
    319        }
    320
    321        public boolean isConflicting() {
    322            return iAdded;
    323        }
    324
    325        public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
    326            if (inConflict(assignment, value)) {
    327                double maxConflicts = iJenrlMaxConflicts + iTwiggle;
    328                iTwiggle = (iJenrl + 0.00001) / Math.min(first().maxClassLimit(), second().maxClassLimit()) - maxConflicts;
    329                if (maxConflicts + iTwiggle >= 0.0 && maxConflicts + iTwiggle < 1.0) {
    330                    iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * (maxConflicts + iTwiggle);
    331                } else {
    332                    iJenrlLimit = null;
    333                }
    334            }
    335        }
    336
    337        public void weaken() {
    338            iTwiggle += iJenrlMaxConflictsWeaken;
    339            double maxConflicts = iJenrlMaxConflicts + iTwiggle;
    340            if (maxConflicts >= 0.0 && maxConflicts < 1.0) {
    341                iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts;
    342            } else {
    343                iJenrlLimit = null;
    344            }
    345        }
    346
    347        public boolean isOverLimit() {
    348            return iJenrlLimit != null && iJenrl > iJenrlLimit;
    349        }
    350
    351        public void incLimit(double weight) {
    352            if (iJenrlLimit != null) iJenrlLimit += weight;
    353        }
    354
    355        public void decLimit(double weight) {
    356            double maxConflicts = iJenrlMaxConflicts + iTwiggle;
    357            if (maxConflicts >= 0.0 && maxConflicts < 1.0) {
    358                iJenrlLimit = Math.max(Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts, iJenrlLimit - weight);
    359            } else {
    360                iJenrlLimit = null;
    361            }
    362        }
    363    }
    364}