001package org.cpsolver.coursett.constraint;
002
003import java.util.Enumeration;
004import java.util.HashSet;
005import java.util.Iterator;
006import java.util.List;
007import java.util.Set;
008
009import org.cpsolver.coursett.Constants;
010import org.cpsolver.coursett.criteria.SameSubpartBalancingPenalty;
011import org.cpsolver.coursett.model.Lecture;
012import org.cpsolver.coursett.model.Placement;
013import org.cpsolver.ifs.assignment.Assignment;
014import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
015import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
016import org.cpsolver.ifs.criteria.Criterion;
017import org.cpsolver.ifs.model.WeakeningConstraint;
018import org.cpsolver.ifs.util.DataProperties;
019import org.cpsolver.ifs.util.ToolBox;
020
021
022/**
023 * Spread given set of classes in time as much as possible. See
024 * {@link DepartmentSpreadConstraint} for more details.
025 * 
026 * @version CourseTT 1.3 (University Course Timetabling)<br>
027 *          Copyright (C) 2006 - 2014 Tomáš Müller<br>
028 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
029 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
030 * <br>
031 *          This library is free software; you can redistribute it and/or modify
032 *          it under the terms of the GNU Lesser General Public License as
033 *          published by the Free Software Foundation; either version 3 of the
034 *          License, or (at your option) any later version. <br>
035 * <br>
036 *          This library is distributed in the hope that it will be useful, but
037 *          WITHOUT ANY WARRANTY; without even the implied warranty of
038 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
039 *          Lesser General Public License for more details. <br>
040 * <br>
041 *          You should have received a copy of the GNU Lesser General Public
042 *          License along with this library; if not see
043 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
044 */
045
046public class SpreadConstraint extends ConstraintWithContext<Lecture, Placement, SpreadConstraint.SpreadConstraintContext> implements WeakeningConstraint<Lecture, Placement> {
047    private boolean iInteractive = false;
048    private double iSpreadFactor = 1.20;
049    private int iUnassignmentsToWeaken = 250;
050    private String iName = null;
051    private int iFirstDaySlot, iLastDaySlot, iFirstWorkDay, iLastWorkDay;
052
053    public static boolean USE_MOST_IMPROVEMENT_ADEPTS = false;
054
055    public SpreadConstraint(String name, double spreadFactor, int unassignmentsToWeaken, boolean interactiveMode, int firstDaySlot, int lastDaySlot, int firstWorkDay, int lastWorkDay) {
056        iName = name;
057        iSpreadFactor = spreadFactor;
058        iUnassignmentsToWeaken = unassignmentsToWeaken;
059        iInteractive = interactiveMode;
060        iFirstDaySlot = firstDaySlot;
061        iLastDaySlot = lastDaySlot;
062        iFirstWorkDay = firstWorkDay;
063        iLastWorkDay = lastWorkDay;
064        if (iLastWorkDay < iFirstWorkDay) iLastWorkDay += 7;
065    }
066
067    public SpreadConstraint(DataProperties config, String name) {
068        this(name,
069                config.getPropertyDouble("Spread.SpreadFactor", 1.20),
070                config.getPropertyInt("Spread.Unassignments2Weaken", 250),
071                config.getPropertyBoolean("General.InteractiveMode", false),
072                config.getPropertyInt("General.FirstDaySlot", Constants.DAY_SLOTS_FIRST),
073                config.getPropertyInt("General.LastDaySlot", Constants.DAY_SLOTS_LAST),
074                config.getPropertyInt("General.FirstWorkDay", 0),
075                config.getPropertyInt("General.LastWorkDay", Constants.NR_DAYS_WEEK - 1)
076                );
077    }
078    
079    
080    protected Criterion<Lecture, Placement> getCriterion() {
081        return getModel().getCriterion(SameSubpartBalancingPenalty.class);
082    }
083
084    public Placement getAdept(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses, Set<Placement> conflicts) {
085        Placement adept = null;
086        int improvement = 0;
087
088        // take uncommitted placements first
089        for (Lecture lect : variables()) {
090            if (lect.isCommitted())
091                continue;
092            Placement plac = assignment.getValue(lect);
093            if (plac == null || plac.equals(placement) || placement.variable().equals(plac.variable())
094                    || conflicts.contains(plac))
095                continue;
096            int imp = getPenaltyIfUnassigned(assignment, plac, nrCourses);
097            if (imp == 0)
098                continue;
099            if (adept == null || imp > improvement) {
100                adept = plac;
101                improvement = imp;
102            }
103        }
104        if (adept != null)
105            return adept;
106
107        // no uncommitted placement found -- take committed one
108        for (Lecture lect : variables()) {
109            if (!lect.isCommitted())
110                continue;
111            Placement plac = assignment.getValue(lect);
112            if (plac == null || plac.equals(placement) || conflicts.contains(plac))
113                continue;
114            int imp = getPenaltyIfUnassigned(assignment, plac, nrCourses);
115            if (imp == 0)
116                continue;
117            if (adept == null || imp > improvement) {
118                adept = plac;
119                improvement = imp;
120            }
121        }
122
123        return adept;
124    }
125
126    @SuppressWarnings("unchecked")
127    private Set<Placement>[] getAdepts(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses, Set<Placement> conflicts) {
128        SpreadConstraintContext context = getContext(assignment);
129        int firstSlot = placement.getTimeLocation().getStartSlot();
130        if (firstSlot > iLastDaySlot)
131            return null;
132        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
133        if (endSlot < iFirstDaySlot)
134            return null;
135        HashSet<Placement> adepts[] = new HashSet[] { new HashSet<Placement>(), new HashSet<Placement>() };
136        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
137            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
138                int dayCode = Constants.DAY_CODES[j % 7];
139                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 && nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] >= context.getMaxCourses(i, j)) {
140                    for (Placement p : context.getCourses(i, j)) {
141                        if (conflicts.contains(p))
142                            continue;
143                        if (p.equals(placement))
144                            continue;
145                        if (p.variable().equals(placement.variable()))
146                            continue;
147                        adepts[(p.variable()).isCommitted() ? 1 : 0].add(p);
148                    }
149                }
150            }
151        }
152        return adepts;
153        // sLogger.debug("  -- adept "+adept+" selected, penalty will be decreased by "+improvement);
154    }
155
156    private int getPenaltyIfUnassigned(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) {
157        SpreadConstraintContext context = getContext(assignment);
158        int firstSlot = placement.getTimeLocation().getStartSlot();
159        if (firstSlot > iLastDaySlot)
160            return 0;
161        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
162        if (endSlot < iFirstDaySlot)
163            return 0;
164        int penalty = 0;
165        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
166            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
167                int dayCode = Constants.DAY_CODES[j % 7];
168                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 && nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j))
169                    penalty++;
170            }
171        }
172        return penalty;
173    }
174
175    private int tryUnassign(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) {
176        SpreadConstraintContext context = getContext(assignment);
177        // sLogger.debug("  -- trying to unassign "+placement);
178        int firstSlot = placement.getTimeLocation().getStartSlot();
179        if (firstSlot > iLastDaySlot)
180            return 0;
181        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
182        if (endSlot < iFirstDaySlot)
183            return 0;
184        int improvement = 0;
185        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
186            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
187                int dayCode = Constants.DAY_CODES[j % 7];
188                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
189                    if (nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j))
190                        improvement++;
191                    nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]--;
192                }
193            }
194        }
195        // sLogger.debug("  -- penalty is decreased by "+improvement);
196        return improvement;
197    }
198
199    private int tryAssign(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) {
200        SpreadConstraintContext context = getContext(assignment);
201        // sLogger.debug("  -- trying to assign "+placement);
202        int firstSlot = placement.getTimeLocation().getStartSlot();
203        if (firstSlot > iLastDaySlot)
204            return 0;
205        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
206        if (endSlot < iFirstDaySlot)
207            return 0;
208        int penalty = 0;
209        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
210            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
211                int dayCode = Constants.DAY_CODES[j % 7];
212                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
213                    nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]++;
214                    if (nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j))
215                        penalty++;
216                }
217            }
218        }
219        // sLogger.debug("  -- penalty is incremented by "+penalty);
220        return penalty;
221    }
222
223    @Override
224    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) {
225        SpreadConstraintContext context = getContext(assignment);
226        if (context.getUnassignmentsToWeaken() == 0)
227            return;
228        int penalty = context.getCurrentPenalty() + getPenalty(assignment, placement);
229        if (penalty <= context.getMaxAllowedPenalty())
230            return;
231        int firstSlot = placement.getTimeLocation().getStartSlot();
232        if (firstSlot > iLastDaySlot)
233            return;
234        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
235        if (endSlot < iFirstDaySlot)
236            return;
237        // sLogger.debug("-- computing conflict for value "+value+" ... (penalty="+iCurrentPenalty+", penalty with the value="+penalty+", max="+iMaxAllowedPenalty+")");
238        int[][] nrCourses = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
239        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++)
240            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++)
241                nrCourses[i][j] = context.getNrCourses(i + iFirstDaySlot, j + iFirstWorkDay, placement);
242        tryAssign(assignment, placement, nrCourses);
243        // sLogger.debug("  -- nrCurses="+fmt(nrCourses));
244        for (Lecture lect : variables()) {
245            if (lect.equals(placement.variable())) continue;
246            Placement p = assignment.getValue(lect);
247            if (p != null && conflicts.contains(p)) {
248                penalty -= tryUnassign(assignment, p, nrCourses);
249            }
250            if (penalty <= context.getMaxAllowedPenalty())
251                return;
252        }
253        if (USE_MOST_IMPROVEMENT_ADEPTS) {
254            while (penalty > context.getMaxAllowedPenalty()) {
255                Placement plac = getAdept(assignment, placement, nrCourses, conflicts);
256                if (plac == null)
257                    break;
258                conflicts.add(plac);
259                penalty -= tryUnassign(assignment, plac, nrCourses);
260            }
261        } else {
262            if (penalty > context.getMaxAllowedPenalty()) {
263                Set<Placement> adepts[] = getAdepts(assignment, placement, nrCourses, conflicts);
264                for (int i = 0; penalty > context.getMaxAllowedPenalty() && i < adepts.length; i++) {
265                    while (!adepts[i].isEmpty() && penalty > context.getMaxAllowedPenalty()) {
266                        Placement plac = ToolBox.random(adepts[i]);
267                        adepts[i].remove(plac);
268                        conflicts.add(plac);
269                        // sLogger.debug("  -- conflict "+lect.getAssignment()+" added");
270                        penalty -= tryUnassign(assignment, plac, nrCourses);
271                    }
272                }
273            }
274        }
275    }
276
277    @Override
278    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) {
279        SpreadConstraintContext context = getContext(assignment);
280        if (context.getUnassignmentsToWeaken() == 0) return false;
281        return getPenalty(assignment, placement) + context.getCurrentPenalty() > context.getMaxAllowedPenalty();
282    }
283
284    @Override
285    public void weaken(Assignment<Lecture, Placement> assignment) {
286        getContext(assignment).weaken();
287    }
288
289    @Override
290    public String getName() {
291        return iName;
292    }
293
294    @Override
295    public String toString() {
296        StringBuffer sb = new StringBuffer();
297        sb.append("Time Spread between ");
298        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
299            Lecture v = e.next();
300            sb.append(v.getName());
301            if (e.hasNext())
302                sb.append(", ");
303        }
304        return sb.toString();
305    }
306
307    /** Department balancing penalty for this department 
308     * @param assignment current assignment
309     * @return current penalty
310     **/
311    public int getPenalty(Assignment<Lecture, Placement> assignment) {
312        return getContext(assignment).getCurrentPenalty();
313    }
314
315    public int getPenaltyEstimate(Assignment<Lecture, Placement> assignment) {
316        double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
317        int maxCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
318        int nrCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
319        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++)
320            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++)
321                histogramPerDay[i][j] = 0.0;
322        int totalUsedSlots = 0;
323        for (Lecture lecture : variables()) {
324            List<Placement>  values = lecture.values(assignment);
325            Placement firstPlacement = (values.isEmpty() ? null : values.get(0));
326            if (firstPlacement != null) {
327                totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting()
328                        * firstPlacement.getTimeLocation().getNrMeetings();
329            }
330            for (Placement p : values) {
331                int firstSlot = p.getTimeLocation().getStartSlot();
332                if (firstSlot > iLastDaySlot)
333                    continue;
334                int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1;
335                if (endSlot < iFirstDaySlot)
336                    continue;
337                for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
338                    int dayCode = p.getTimeLocation().getDayCode();
339                    for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
340                        if ((dayCode & Constants.DAY_CODES[j % 7]) != 0) {
341                            histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size();
342                        }
343                    }
344                }
345            }
346        }
347        double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1)));
348        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
349            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
350                nrCourses[i][j] = 0;
351                maxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j]));
352            }
353        }
354        int currentPenalty = 0;
355        for (Lecture lecture : variables()) {
356            Placement placement = assignment.getValue(lecture);
357            if (placement == null)
358                continue;
359            int firstSlot = placement.getTimeLocation().getStartSlot();
360            if (firstSlot > iLastDaySlot)
361                continue;
362            int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
363            if (endSlot < iFirstDaySlot)
364                continue;
365            for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
366                for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
367                    int dayCode = Constants.DAY_CODES[j % 7];
368                    if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
369                        nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]++;
370                    }
371                }
372            }
373        }
374        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
375            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
376                currentPenalty += Math.max(0, nrCourses[i][j] - maxCourses[i][j]);
377            }
378        }
379        return currentPenalty;
380    }
381
382    public int getMaxPenalty(Assignment<Lecture, Placement> assignment, Placement placement) {
383        SpreadConstraintContext context = getContext(assignment);
384        int penalty = 0;
385        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
386            int slot = e.nextElement();
387            int day = slot / Constants.SLOTS_PER_DAY;
388            int time = slot % Constants.SLOTS_PER_DAY;
389            if (time < iFirstDaySlot || time > iLastDaySlot)
390                continue;
391            if (iLastWorkDay < 7) {
392                if (day < iFirstWorkDay || day > iLastWorkDay)
393                    continue;
394            } else {
395                if (day < iFirstWorkDay && day > iLastWorkDay - 7)
396                    continue;
397                if (day < iFirstWorkDay) day += 7;
398            }
399            int dif = 1 + context.getNrCourses(time, day, placement) - context.getMaxCourses(time, day);
400            if (dif > penalty)
401                penalty = dif;
402        }
403        return penalty;
404    }
405
406    /** Department balancing penalty of the given placement 
407     * @param assignment current assignment
408     * @param placement a placement that is being considered
409     * @return change in the penalty if assigned
410     **/
411    public int getPenalty(Assignment<Lecture, Placement> assignment, Placement placement) {
412        SpreadConstraintContext context = getContext(assignment);
413        int firstSlot = placement.getTimeLocation().getStartSlot();
414        if (firstSlot > iLastDaySlot)
415            return 0;
416        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
417        if (endSlot < iFirstDaySlot)
418            return 0;
419        int penalty = 0;
420        int min = Math.max(firstSlot, iFirstDaySlot);
421        int max = Math.min(endSlot, iLastDaySlot);
422        for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
423            int dayCode = Constants.DAY_CODES[j % 7];
424            if ((dayCode & placement.getTimeLocation().getDayCode()) == 0)
425                continue;
426            for (int i = min; i <= max; i++) {
427                if (context.getNrCourses(i, j, placement) >= context.getMaxCourses(i, j))
428                    penalty++;
429            }
430        }
431        return penalty;
432    }
433
434    @Override
435    public void addVariable(Lecture lecture) {
436        if (lecture.canShareRoom()) {
437            for (GroupConstraint gc : lecture.groupConstraints()) {
438                if (gc.getType() == GroupConstraint.ConstraintType.MEET_WITH) {
439                    if (gc.variables().indexOf(lecture) > 0)
440                        return;
441                }
442            }
443        }
444        super.addVariable(lecture);
445    }
446
447    @Override
448    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
449        while (inConflict(assignment, value))
450            getContext(assignment).weaken(getContext(assignment).getCurrentPenalty() + getPenalty(assignment, value));
451    }
452    
453    @Override
454    public SpreadConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
455        return new SpreadConstraintContext(assignment);
456    }
457
458    public class SpreadConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
459        private int iMaxAllowedPenalty = 0;
460        private long iUnassignment = 0;
461        private Set<Placement>[][] iCourses = null;
462        private int iMaxCourses[][] = null;
463        private int iCurrentPenalty = 0;
464
465        @SuppressWarnings("unchecked")
466        public SpreadConstraintContext(Assignment<Lecture, Placement> assignment) {
467            iCourses = new Set[iLastDaySlot - iFirstDaySlot + 1][(iLastWorkDay - iFirstWorkDay + 1) % 7];
468            if (iInteractive)
469                iUnassignmentsToWeaken = 0;
470            for (int i = 0; i < iCourses.length; i++) {
471                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
472                    iCourses[i][j] = new HashSet<Placement>(10);
473                }
474            }
475            double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
476            iMaxCourses = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
477            for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++)
478                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++)
479                    histogramPerDay[i][j] = 0.0;
480            int totalUsedSlots = 0;
481            for (Lecture lecture : variables()) {
482                List<Placement>  values = lecture.values(assignment);
483                Placement firstPlacement = (values.isEmpty() ? null : values.get(0));
484                if (firstPlacement != null) {
485                    totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting() * firstPlacement.getTimeLocation().getNrMeetings();
486                }
487                for (Placement p : values) {
488                    int firstSlot = p.getTimeLocation().getStartSlot();
489                    if (firstSlot > iLastDaySlot)
490                        continue;
491                    int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1;
492                    if (endSlot < iFirstDaySlot)
493                        continue;
494                    for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
495                        int dayCode = p.getTimeLocation().getDayCode();
496                        for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
497                            if ((dayCode & Constants.DAY_CODES[j % 7]) != 0) {
498                                histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size();
499                            }
500                        }
501                    }
502                }
503            }
504            // System.out.println("Histogram for department "+iDepartment+":");
505            double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1)));
506            // System.out.println("Threshold["+iDepartment+"] = "+threshold);
507            for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
508                // System.out.println("  "+fmt(i+1)+": "+fmt(histogramPerDay[i]));
509                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
510                    iMaxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j]));
511                }
512            }
513            for (Lecture lecture : variables()) {
514                Placement placement = assignment.getValue(lecture);
515                if (placement == null)
516                    continue;
517                int firstSlot = placement.getTimeLocation().getStartSlot();
518                if (firstSlot > iLastDaySlot)
519                    continue;
520                int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
521                if (endSlot < iFirstDaySlot)
522                    continue;
523                for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
524                    for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
525                        int dayCode = Constants.DAY_CODES[j % 7];
526                        if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
527                            iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement);
528                        }
529                    }
530                }
531            }
532            iCurrentPenalty = 0;
533            for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
534                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
535                    iCurrentPenalty += Math.max(0, iCourses[i][j].size() - iMaxCourses[i][j]);
536                }
537            }
538            iMaxAllowedPenalty = iCurrentPenalty;
539            getCriterion().inc(assignment, iCurrentPenalty);
540        }
541        
542
543        @Override
544        public void assigned(Assignment<Lecture, Placement> assignment, Placement placement) {
545            int firstSlot = placement.getTimeLocation().getStartSlot();
546            if (firstSlot > iLastDaySlot)
547                return;
548            int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
549            if (endSlot < iFirstDaySlot)
550                return;
551            getCriterion().inc(assignment, -iCurrentPenalty);
552            for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
553                for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
554                    int dayCode = Constants.DAY_CODES[j % 7];
555                    if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
556                        iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement);
557                        if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay])
558                            iCurrentPenalty++;
559                    }
560                }
561            }
562            getCriterion().inc(assignment, iCurrentPenalty);
563        }
564
565        @Override
566        public void unassigned(Assignment<Lecture, Placement> assignment, Placement placement) {
567            int firstSlot = placement.getTimeLocation().getStartSlot();
568            if (firstSlot > iLastDaySlot)
569                return;
570            int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
571            if (endSlot < iFirstDaySlot)
572                return;
573            getCriterion().inc(assignment, -iCurrentPenalty);
574            for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
575                for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
576                    int dayCode = Constants.DAY_CODES[j % 7];
577                    if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
578                        if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay])
579                            iCurrentPenalty--;
580                        iCourses[i - iFirstDaySlot][j - iFirstWorkDay].remove(placement);
581                    }
582                }
583            }
584            getCriterion().inc(assignment, iCurrentPenalty);
585        }
586        
587        public int[][] getMaxCourses() {
588            return iMaxCourses;
589        }
590
591        public int getMaxCourses(int time, int day) {
592            return iMaxCourses[time - iFirstDaySlot][day - iFirstWorkDay];
593        }
594
595        public int getNrCourses(int time, int day, Placement placement) {
596            if (placement == null) return getCourses(time, day).size();
597            int nrCourses = 0;
598            for (Placement p: getCourses(time, day))
599                if (!p.variable().equals(placement.variable())) 
600                    nrCourses ++;
601            return nrCourses;
602        }
603        
604        public Set<Placement> getCourses(int time, int day) {
605            return iCourses[time - iFirstDaySlot][day - iFirstWorkDay];
606        }
607        
608        public int getUnassignmentsToWeaken() {
609            return iUnassignmentsToWeaken;
610        }
611        
612        public int getCurrentPenalty() {
613            return iCurrentPenalty;
614        }
615        
616        public int getMaxAllowedPenalty() {
617            return iMaxAllowedPenalty;
618        }
619        
620        public void weaken() {
621            if (iUnassignmentsToWeaken == 0) return;
622            iUnassignment++;
623            if (iUnassignment % iUnassignmentsToWeaken == 0)
624                iMaxAllowedPenalty++;
625        }
626        
627        public void weaken(int penalty) {
628            if (penalty > iMaxAllowedPenalty)
629                iMaxAllowedPenalty = penalty; 
630        }
631
632    }
633}