    001package org.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.BitSet;
    005import java.util.Collections;
    006import java.util.HashMap;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010import java.util.regex.Matcher;
    011import java.util.regex.Pattern;
    012
    013import org.cpsolver.coursett.Constants;
    014import org.cpsolver.coursett.model.Lecture;
    015import org.cpsolver.coursett.model.Placement;
    016import org.cpsolver.ifs.assignment.Assignment;
    017import org.cpsolver.ifs.model.WeakeningConstraint;
    018import org.cpsolver.ifs.util.ToolBox;
    019
    020
    021/**
    022 *
    023 * The MaxHoles constraint limits the number of free time (holes) for an instructor on a day.<br>
    024 * It has one parameter: a maximal amount of free time (holes) that an instructor have on a day in minutes.<br>
    025 * Reference _MaxHoles:120_ translates to a maximum number of two hours on a day (between the first and the last class on a day).<br>
    026 *
    027 * @version CourseTT 1.3 (University Course Timetabling)<br>
    028 *          Copyright (C) 2013 - 2017 Tomáš Müller<br>
    029 * <br>
    030 *          This library is free software; you can redistribute it and/or modify
    031 *          it under the terms of the GNU Lesser General Public License as
    032 *          published by the Free Software Foundation; either version 3 of the
    033 *          License, or (at your option) any later version. <br>
    034 * <br>
    035 *          This library is distributed in the hope that it will be useful, but
    036 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    037 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    038 *          Lesser General Public License for more details. <br>
    039 * <br>
    040 *          You should have received a copy of the GNU Lesser General Public
    041 *          License along with this library; if not see
    042 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    043 */
    044public class MaxHolesFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> {
    045    private int iMaxHolesOnADay = 288;
    046
    047    public MaxHolesFlexibleConstraint(Long id, String owner, String preference, String reference) {
    048        super(id, owner, preference, reference);
    049
    050        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HOLES.getPattern()).matcher(reference);
    051        if (matcher.find()) {
    052            iMaxHolesOnADay = Integer.parseInt(matcher.group(2)) / Constants.SLOT_LENGTH_MIN;
    053            iConstraintType = FlexibleConstraintType.MAX_HOLES;
    054        }
    055    }
    056
    057    /**
    058     * Count number of holes (free slots) between the given classes on given day and week.
    059     * @param assignment current assignment
    060     * @param dayCode representation of days in week combination
    061     * @param conflicts placements to be unassigned
    062     * @param value placement to be assigned
    063     * @param assignments placements of variables
    064     * @param week bitset representing a date pattern
    065     * @return number of holes (free slots) that are over the limit
    066     */
    067    public int countHoles(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
    068        List<Placement> placements = new ArrayList<Placement>(getRelevantPlacements(assignment, dayCode, conflicts, value, assignments, week));
    069        Collections.sort(placements, new PlacementTimeComparator());
    070
    071        int lastSlot = -1;
    072        int holes = 0;
    073        for (Placement placement: placements) {
    074            if (lastSlot >= 0 && placement.getTimeLocation().getStartSlot() > lastSlot) {
    075                holes += (placement.getTimeLocation().getStartSlot() - lastSlot);
    076            }
    077            lastSlot = Math.max(lastSlot, placement.getTimeLocation().getStartSlot() + placement.getTimeLocation().getLength());
    078        }
    079        return holes;
    080    }
    081
    082    /**
    083     * Count violations, that is weekly average free time that is over the limit in hours.
    084     * @param assignment current assignment
    085     * @param conflicts placements to be unassigned
    086     * @param assignments placements of variables
    087     * @return weekly average free time that is over the limit in hours
    088     */
    089    @Override
    090    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    091        double penalty = 0;
    092        // constraint is checked for every day in week
    093        for (int dayCode : Constants.DAY_CODES) {
    094            // constraint is checked for every week in semester (or for the whole semester)
    095            for (BitSet week : getWeeks()) {
    096                // count holes in the week and day
    097                int holes = countHoles(assignment, dayCode, conflicts, null, assignments, week);
    098                if (holes > iMaxHolesOnADay)
    099                    penalty += (holes - iMaxHolesOnADay);
    100            }
    101        }
    102        // return average holes in a week, in hours
    103        return penalty / (12.0 * getWeeks().size());
    104    }
    105
    106    @Override
    107    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    108        if (!isHard()) return;
    109
    110        MaxHolesFlexibleConstraintContext context = (MaxHolesFlexibleConstraintContext)getContext(assignment);
    111
    112        // constraint is checked for every day in week
    113        for (int dayCode : Constants.DAY_CODES) {
    114            if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
    115            // constraint is checked for every week in semester (or for the whole semester)
    116            for (BitSet week : getWeeks()) {
    117                if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
    118                // check penalty
    119                int penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
    120                while (penalty > context.getMaxHoles(dayCode, week)) {
    121                    // too many holes -> identify adepts for unassignment
    122                    List<Placement> adepts = new ArrayList<Placement>();
    123                    for (Placement placement: getRelevantPlacements(assignment, dayCode, conflicts, value, null, week)) {
    124                        if (placement.equals(value)) continue; // skip given value
    125                        // check if removing placement would improve the penalty
    126                        HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); assignments.put(placement.variable(), null);
    127                        int newPenalty = countHoles(assignment, dayCode, conflicts, value, assignments, week);
    128                        if (newPenalty <= penalty)
    129                            adepts.add(placement);
    130                    }
    131
    132                    // no adepts -> fail
    133                    if (adepts.isEmpty()) {
    134                        conflicts.add(value); return;
    135                    }
    136
    137                    // pick one randomly
    138                    conflicts.add(ToolBox.random(adepts));
    139                    penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
    140                }
    141            }
    142        }
    143    }
    144
    145    @Override
    146    public void weaken(Assignment<Lecture, Placement> assignment) {
    147    }
    148
    149    @Override
    150    public boolean isConsistent(Placement value1, Placement value2) {
    151        // there is no way to check without trying to put other placements in between
    152        return true;
    153    }
    154
    155    @Override
    156    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
    157        if (isHard())
    158            ((MaxHolesFlexibleConstraintContext)getContext(assignment)).weaken(assignment, value);
    159    }
    160
    161    @Override
    162    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    163        return new MaxHolesFlexibleConstraintContext(assignment);
    164    }
    165
    166    public class MaxHolesFlexibleConstraintContext extends FlexibleConstraintContext {
    167        private Map<Integer, Map<BitSet, Integer>> iMaxHoles = new HashMap<Integer, Map<BitSet, Integer>>();
    168
    169        public MaxHolesFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    170            super(assignment);
    171        }
    172
    173        public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
    174            if (!isHard()) return;
    175            for (int dayCode : Constants.DAY_CODES) {
    176                if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
    177                for (BitSet week : getWeeks()) {
    178                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
    179                    int penalty = countHoles(assignment, dayCode, null, value, null, week);
    180                    if (penalty > iMaxHolesOnADay) {
    181                        Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
    182                        if (holes == null) {
    183                            holes = new HashMap<BitSet, Integer>();
    184                            iMaxHoles.put(dayCode, holes);
    185                        }
    186                        Integer oldPenalty = holes.get(week);
    187                        if (oldPenalty != null && oldPenalty >= penalty) continue;
    188                        holes.put(week, penalty);
    189                    }
    190                }
    191            }
    192        }
    193
    194        public int getMaxHoles(int dayCode, BitSet week) {
    195            Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
    196            if (holes == null) return iMaxHolesOnADay;
    197            Integer penalty = holes.get(week);
    198            if (penalty == null || penalty < iMaxHolesOnADay) return iMaxHolesOnADay;
    199            return penalty;
    200        }
    201    }
    202
    203}