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}