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 Tomas Muller<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()))
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());
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     * @return true if there is a student conflict between the two placements
103     */
104    public static boolean isInConflict(Placement p1, Placement p2, DistanceMetric m) {
105        return p1 != null && p2 != null && !StudentConflict.ignore(p1.variable(), p2.variable()) && (StudentConflict.distance(m, p1, p2) || StudentConflict.overlaps(p1, p2));
106    }
107
108    /**
109     * Number of joined enrollments if the given value is assigned to the given
110     * variable
111     * @param assignment current assignment
112     * @param variable a class
113     * @param value class placement under consideration
114     * @return number of student conflicts caused by this constraint if assigned
115     */
116    public long jenrl(Assignment<Lecture, Placement> assignment, Lecture variable, Placement value) {
117        Lecture other = (first().equals(variable) ? second() : first());
118        Placement otherPlacement = (other == null ? null : assignment.getValue(other));
119        return (otherPlacement != null && isInConflict(value, otherPlacement, getDistanceMetric()) ? Math.round(iJenrl) : 0);
120    }
121    
122    private DistanceMetric getDistanceMetric() {
123        return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric());
124    }
125
126    /** True if the given two lectures overlap in time 
127     * @param assignment current assignment
128     * @return true if this constraint is conflicting
129     **/
130    public boolean isInConflict(Assignment<Lecture, Placement> assignment) {
131        return getContext(assignment).isConflicting();
132    }
133
134    /**
135     * Increment the number of joined enrollments (during student final
136     * sectioning)
137     * @param assignment current assignment
138     * @param student student added in between the two classes of this constraint
139     */
140    public void incJenrl(Assignment<Lecture, Placement> assignment, Student student) {
141        JenrlConstraintContext context = getContext(assignment);
142        boolean hard = context.isOverLimit();
143        double jenrlWeight = student.getJenrlWeight(first(), second());
144        iJenrl += jenrlWeight;
145        Double conflictPriority = student.getConflictingPriorty(first(), second());
146        if (conflictPriority != null) iPriority += conflictPriority * jenrlWeight;
147        iStudents.add(student);
148        if (student.getInstructor() != null && (student.getInstructor().variables().contains(first()) ||
149                student.getInstructor().variables().contains(second())))
150            iInstructors.add(student);
151        for (Criterion<Lecture, Placement> criterion: getModel().getCriteria())
152            if (criterion instanceof StudentConflict)
153                ((StudentConflict)criterion).incJenrl(assignment, this, jenrlWeight, conflictPriority, student);
154        if (!hard && context.isOverLimit() && isInConflict(assignment)) {
155            context.incLimit(jenrlWeight);
156        }
157    }
158
159    public double getJenrlWeight(Student student) {
160        return student.getJenrlWeight(first(), second());
161    }
162
163    /**
164     * Decrement the number of joined enrollments (during student final
165     * sectioning)
166     * @param assignment current assignment
167     * @param student student removed from between the two classes of this constraint
168     */
169    public void decJenrl(Assignment<Lecture, Placement> assignment, Student student) {
170        JenrlConstraintContext context = getContext(assignment);
171        boolean hard = context.isOverLimit();
172        double jenrlWeight = student.getJenrlWeight(first(), second());
173        iJenrl -= jenrlWeight;
174        Double conflictPriority = student.getConflictingPriorty(first(), second());
175        if (conflictPriority != null) iPriority -= conflictPriority * jenrlWeight;
176        iStudents.remove(student);
177        iInstructors.remove(student);
178        for (Criterion<Lecture, Placement> criterion: getModel().getCriteria())
179            if (criterion instanceof StudentConflict)
180                ((StudentConflict)criterion).incJenrl(assignment, this, -jenrlWeight, conflictPriority, student);
181        if (hard && !context.isOverLimit())
182            context.decLimit(jenrlWeight);
183    }
184
185    /** Number of joined enrollments (during student final sectioning) 
186     * @return number of joined enrollments
187     **/
188    public long getJenrl() {
189        return Math.round(iJenrl);
190    }
191
192    public double jenrl() {
193        return iJenrl;
194    }
195
196    public double priority() {
197        return iPriority;
198    }
199
200    public int getNrStudents() {
201        return iStudents.size();
202    }
203    
204    public Set<Student> getStudents() {
205        return iStudents;
206    }
207    
208    public int getNrInstructors() {
209        return iInstructors.size();
210    }
211    
212    public Set<Student> getInstructors() {
213        return iInstructors;
214    }
215
216    @Override
217    public boolean isHard() {
218        return true;
219    }
220    
221    @Override
222    public String getName() {
223        return "Join Enrollment";
224    }
225
226    @Override
227    public String toString() {
228        return "Join Enrollment between " + first().getName() + " and " + second().getName();
229    }
230
231    public boolean areStudentConflictsHard() {
232        return StudentConflict.hard(first(), second());
233    }
234
235    public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment) {
236        return StudentConflict.distance(getDistanceMetric(), assignment.getValue(first()), assignment.getValue(second()));
237    }
238
239    public boolean areStudentConflictsCommitted() {
240        return StudentConflict.committed(first(), second());
241    }
242
243    public boolean areStudentConflictsDistance(Assignment<Lecture, Placement> assignment, Placement value) {
244        return StudentConflict.distance(getDistanceMetric(), value, assignment.getValue(another(value.variable())));
245    }
246
247    public boolean isOfTheSameProblem() {
248        return ToolBox.equals(first().getSolverGroupId(), second().getSolverGroupId());
249    }
250
251    @Override
252    public void weaken(Assignment<Lecture, Placement> assignment) {
253        getContext(assignment).weaken();
254    }
255
256    @Override
257    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
258        getContext(assignment).weaken(assignment, value);
259    }
260    
261    /**
262     * Returns true if there is {@link IgnoreStudentConflictsConstraint} between the two lectures.
263     * @return true if this constraint is to be ignored
264     */
265    public boolean isToBeIgnored() {
266        return first().isToIgnoreStudentConflictsWith(second());
267    }
268    
269    @Override
270    public JenrlConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
271        return new JenrlConstraintContext(assignment);
272    }
273
274    public class JenrlConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
275        private boolean iAdded = false;
276        private Double iJenrlLimit = null;
277        private double iTwiggle = 0.0;
278
279        public JenrlConstraintContext(Assignment<Lecture, Placement> assignment) {
280            Placement p1 = assignment.getValue(first());
281            Placement p2 = assignment.getValue(second());
282            if (p1 != null && p2 != null && isInConflict(p1, p2, getDistanceMetric())) {
283                iAdded = true;
284                first().addActiveJenrl(assignment, JenrlConstraint.this);
285                second().addActiveJenrl(assignment, JenrlConstraint.this);
286            }
287            if (iJenrlMaxConflicts >= 0.0 && iJenrlMaxConflicts < 1.0)
288                iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * iJenrlMaxConflicts;
289        }
290
291        @Override
292        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
293            Lecture other = another(value.variable());
294            if (other == null) return;
295            Placement otherValue = assignment.getValue(other);
296            if (!iAdded && otherValue != null && isInConflict(value, otherValue, getDistanceMetric())) {
297                iAdded = true;
298                first().addActiveJenrl(assignment, JenrlConstraint.this);
299                second().addActiveJenrl(assignment, JenrlConstraint.this);
300            }
301        }
302
303        @Override
304        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
305            if (iAdded) {
306                iAdded = false;
307                first().removeActiveJenrl(assignment, JenrlConstraint.this);
308                second().removeActiveJenrl(assignment, JenrlConstraint.this);
309            }
310        }
311        
312        public boolean isConflicting() {
313            return iAdded;
314        }
315        
316        public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
317            if (inConflict(assignment, value)) {
318                double maxConflicts = iJenrlMaxConflicts + iTwiggle;
319                iTwiggle = (iJenrl + 0.00001) / Math.min(first().maxClassLimit(), second().maxClassLimit()) - maxConflicts;
320                if (maxConflicts + iTwiggle >= 0.0 && maxConflicts + iTwiggle < 1.0) {
321                    iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * (maxConflicts + iTwiggle);
322                } else {
323                    iJenrlLimit = null;
324                }
325            }
326        }
327        
328        public void weaken() {
329            iTwiggle += iJenrlMaxConflictsWeaken;
330            double maxConflicts = iJenrlMaxConflicts + iTwiggle;
331            if (maxConflicts >= 0.0 && maxConflicts < 1.0) {
332                iJenrlLimit = Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts;
333            } else {
334                iJenrlLimit = null;
335            }
336        }
337        
338        public boolean isOverLimit() {
339            return iJenrlLimit != null && iJenrl > iJenrlLimit;
340        }
341        
342        public void incLimit(double weight) {
343            if (iJenrlLimit != null) iJenrlLimit += weight;
344        }
345        
346        public void decLimit(double weight) {
347            double maxConflicts = iJenrlMaxConflicts + iTwiggle;
348            if (maxConflicts >= 0.0 && maxConflicts < 1.0) {
349                iJenrlLimit = Math.max(Math.min(first().maxClassLimit(), second().maxClassLimit()) * maxConflicts, iJenrlLimit - weight);
350            } else {
351                iJenrlLimit = null;
352            }
353        }
354    }
355}