    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 * @author  Tomáš Müller
    028 * @version CourseTT 1.3 (University Course Timetabling)<br>
    029 *          Copyright (C) 2013 - 2017 Tomáš Müller<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 */
    045public class MaxHolesFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> {
    046    private int iMaxHolesOnADay = 288;
    047
    048    public MaxHolesFlexibleConstraint(Long id, String owner, String preference, String reference) {
    049        super(id, owner, preference, reference);
    050
    051        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HOLES.getPattern()).matcher(reference);
    052        if (matcher.find()) {
    053            iMaxHolesOnADay = Integer.parseInt(matcher.group(2)) / Constants.SLOT_LENGTH_MIN;
    054            iConstraintType = FlexibleConstraintType.MAX_HOLES;
    055        }
    056    }
    057
    058    /**
    059     * Count number of holes (free slots) between the given classes on given day and week.
    060     * @param assignment current assignment
    061     * @param dayCode representation of days in week combination
    062     * @param conflicts placements to be unassigned
    063     * @param value placement to be assigned
    064     * @param assignments placements of variables
    065     * @param week bitset representing a date pattern
    066     * @return number of holes (free slots) that are over the limit
    067     */
    068    public int countHoles(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
    069        List<Placement> placements = new ArrayList<Placement>(getRelevantPlacements(assignment, dayCode, conflicts, value, assignments, week));
    070        Collections.sort(placements, new PlacementTimeComparator());
    071
    072        int lastSlot = -1;
    073        int holes = 0;
    074        for (Placement placement: placements) {
    075            if (lastSlot >= 0 && placement.getTimeLocation().getStartSlot() > lastSlot) {
    076                holes += (placement.getTimeLocation().getStartSlot() - lastSlot);
    077            }
    078            lastSlot = Math.max(lastSlot, placement.getTimeLocation().getStartSlot() + placement.getTimeLocation().getLength());
    079        }
    080        return holes;
    081    }
    082
    083    /**
    084     * Count violations, that is weekly average free time that is over the limit in hours.
    085     * @param assignment current assignment
    086     * @param conflicts placements to be unassigned
    087     * @param assignments placements of variables
    088     * @return weekly average free time that is over the limit in hours
    089     */
    090    @Override
    091    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
    092        double penalty = 0;
    093        // constraint is checked for every day in week
    094        for (int dayCode : Constants.DAY_CODES) {
    095            // constraint is checked for every week in semester (or for the whole semester)
    096            for (BitSet week : getWeeks()) {
    097                // count holes in the week and day
    098                int holes = countHoles(assignment, dayCode, conflicts, null, assignments, week);
    099                if (holes > iMaxHolesOnADay)
    100                    penalty += (holes - iMaxHolesOnADay);
    101            }
    102        }
    103        // return average holes in a week, in hours
    104        return penalty / (12.0 * getWeeks().size());
    105    }
    106
    107    @Override
    108    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    109        if (!isHard()) return;
    110
    111        MaxHolesFlexibleConstraintContext context = (MaxHolesFlexibleConstraintContext)getContext(assignment);
    112
    113        // constraint is checked for every day in week
    114        for (int dayCode : Constants.DAY_CODES) {
    115            if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
    116            // constraint is checked for every week in semester (or for the whole semester)
    117            for (BitSet week : getWeeks()) {
    118                if (isPreciseDateComputation()) {
    119                    if (!value.getTimeLocation().overlaps(dayCode, week, getDayOfWeekOffset())) continue;
    120                } else {
    121                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
    122                }
    123                // check penalty
    124                int penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
    125                while (penalty > context.getMaxHoles(dayCode, week)) {
    126                    // too many holes -> identify adepts for unassignment
    127                    List<Placement> adepts = new ArrayList<Placement>();
    128                    for (Placement placement: getRelevantPlacements(assignment, dayCode, conflicts, value, null, week)) {
    129                        if (placement.equals(value)) continue; // skip given value
    130                        // check if removing placement would improve the penalty
    131                        HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); assignments.put(placement.variable(), null);
    132                        int newPenalty = countHoles(assignment, dayCode, conflicts, value, assignments, week);
    133                        if (newPenalty <= penalty)
    134                            adepts.add(placement);
    135                    }
    136
    137                    // no adepts -> fail
    138                    if (adepts.isEmpty()) {
    139                        conflicts.add(value); return;
    140                    }
    141
    142                    // pick one randomly
    143                    conflicts.add(ToolBox.random(adepts));
    144                    penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
    145                }
    146            }
    147        }
    148    }
    149
    150    @Override
    151    public void weaken(Assignment<Lecture, Placement> assignment) {
    152    }
    153
    154    @Override
    155    public boolean isConsistent(Placement value1, Placement value2) {
    156        // there is no way to check without trying to put other placements in between
    157        return true;
    158    }
    159
    160    @Override
    161    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
    162        if (isHard())
    163            ((MaxHolesFlexibleConstraintContext)getContext(assignment)).weaken(assignment, value);
    164    }
    165
    166    @Override
    167    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    168        return new MaxHolesFlexibleConstraintContext(assignment);
    169    }
    170
    171    public class MaxHolesFlexibleConstraintContext extends FlexibleConstraintContext {
    172        private Map<Integer, Map<BitSet, Integer>> iMaxHoles = new HashMap<Integer, Map<BitSet, Integer>>();
    173
    174        public MaxHolesFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
    175            super(assignment);
    176        }
    177
    178        public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
    179            if (!isHard()) return;
    180            for (int dayCode : Constants.DAY_CODES) {
    181                if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
    182                for (BitSet week : getWeeks()) {
    183                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
    184                    int penalty = countHoles(assignment, dayCode, null, value, null, week);
    185                    if (penalty > iMaxHolesOnADay) {
    186                        Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
    187                        if (holes == null) {
    188                            holes = new HashMap<BitSet, Integer>();
    189                            iMaxHoles.put(dayCode, holes);
    190                        }
    191                        Integer oldPenalty = holes.get(week);
    192                        if (oldPenalty != null && oldPenalty >= penalty) continue;
    193                        holes.put(week, penalty);
    194                    }
    195                }
    196            }
    197        }
    198
    199        public int getMaxHoles(int dayCode, BitSet week) {
    200            Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
    201            if (holes == null) return iMaxHolesOnADay;
    202            Integer penalty = holes.get(week);
    203            if (penalty == null || penalty < iMaxHolesOnADay) return iMaxHolesOnADay;
    204            return penalty;
    205        }
    206    }
    207
    208}