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}