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}