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