    001package net.sf.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.Collections;
    005import java.util.Comparator;
    006import java.util.HashSet;
    007import java.util.HashMap;
    008import java.util.Iterator;
    009import java.util.List;
    010import java.util.Set;
    011
    012import net.sf.cpsolver.coursett.Constants;
    013import net.sf.cpsolver.coursett.model.Lecture;
    014import net.sf.cpsolver.coursett.model.Placement;
    015import net.sf.cpsolver.coursett.model.RoomLocation;
    016import net.sf.cpsolver.ifs.model.Constraint;
    017import net.sf.cpsolver.ifs.model.WeakeningConstraint;
    018import net.sf.cpsolver.ifs.util.DataProperties;
    019
    020/**
    021 * Minimize number of used rooms within the set of classes. <br>
    022 * <br>
    023 * This constraint implements the following distribution/group constraint: <br>
    024 * <br>
    025 * MIN_ROOM_USE (Minimize Number Of Rooms Used)<br>
    026 * Minimize number of rooms used by the given set of classes.
    027 *
    028 * @version CourseTT 1.2 (University Course Timetabling)<br>
    029 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    030 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    031 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    032 * <br>
    033 *          This library is free software; you can redistribute it and/or modify
    034 *          it under the terms of the GNU Lesser General Public License as
    035 *          published by the Free Software Foundation; either version 3 of the
    036 *          License, or (at your option) any later version. <br>
    037 * <br>
    038 *          This library is distributed in the hope that it will be useful, but
    039 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    040 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    041 *          Lesser General Public License for more details. <br>
    042 * <br>
    043 *          You should have received a copy of the GNU Lesser General Public
    044 *          License along with this library; if not see
    045 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    046 */
    047
    048public class MinimizeNumberOfUsedRoomsConstraint extends Constraint<Lecture, Placement> implements WeakeningConstraint<Lecture, Placement> {
    049    private int iUnassignmentsToWeaken = 250;
    050    private long iUnassignment = 0;
    051    private int iLimit = 1;
    052    private HashMap<RoomLocation, Set<Lecture>> iUsedRooms = new HashMap<RoomLocation, Set<Lecture>>();
    053    boolean iEnabled = false;
    054
    055    public MinimizeNumberOfUsedRoomsConstraint(DataProperties config) {
    056        iUnassignmentsToWeaken = config.getPropertyInt("MinimizeNumberOfUsedRooms.Unassignments2Weaken",
    057                iUnassignmentsToWeaken);
    058    }
    059
    060    public boolean isOverLimit(Placement placement) {
    061        return getOverLimit(placement) > 0;
    062    }
    063
    064    public int getOverLimit(Placement placement) {
    065        if (!iEnabled)
    066            return 0; // not enabled
    067        if (iUnassignmentsToWeaken == 0)
    068            return 0; // not working
    069
    070        Lecture lecture = placement.variable();
    071
    072        if (lecture.getNrRooms() <= 0)
    073            return 0; // no room
    074        if (lecture.roomLocations().size() == lecture.getNrRooms())
    075            return 0; // required room
    076        if (lecture.isCommitted())
    077            return 0; // commited class
    078
    079        int usage = iUsedRooms.size();
    080        if (usage + lecture.getNrRooms() <= iLimit)
    081            return 0; // under the limit, quick check
    082
    083        if (placement.isMultiRoom()) {
    084            HashSet<RoomLocation> assignedRooms = new HashSet<RoomLocation>();
    085            if (lecture.getAssignment() != null)
    086                assignedRooms.addAll(lecture.getAssignment().getRoomLocations());
    087            for (RoomLocation r : placement.getRoomLocations()) {
    088                if (assignedRooms.remove(r))
    089                    continue;
    090                if (!iUsedRooms.containsKey(r))
    091                    usage++;
    092            }
    093            for (RoomLocation r : assignedRooms) {
    094                Set<Lecture> lects = iUsedRooms.get(r);
    095                if (lects != null && lects.size() == 1)
    096                    usage--;
    097            }
    098        } else {
    099            RoomLocation assignedRoom = (lecture.getAssignment() != null && !lecture.getAssignment().equals(placement) ? lecture
    100                    .getAssignment().getRoomLocation()
    101                    : null);
    102            RoomLocation room = placement.getRoomLocation();
    103            if (!room.equals(assignedRoom)) {
    104                if (!iUsedRooms.containsKey(room))
    105                    usage++;
    106                if (assignedRoom != null) {
    107                    Set<Lecture> lects = iUsedRooms.get(assignedRoom);
    108                    if (lects != null && lects.size() == 1)
    109                        usage--;
    110                }
    111            }
    112        }
    113        if (usage <= iUsedRooms.size())
    114            return 0; // number of used rooms not changed
    115        if (usage <= iLimit)
    116            return 0; // under the limit
    117        return usage - iLimit;
    118    }
    119
    120    @Override
    121    public void computeConflicts(Placement placement, Set<Placement> conflicts) {
    122        int overLimit = getOverLimit(placement);
    123        if (overLimit > 0) {
    124            List<List<Placement>> adepts = new ArrayList<List<Placement>>();
    125            for (Set<Lecture> lects: iUsedRooms.values()) {
    126                List<Placement> placementsToUnassign = new ArrayList<Placement>();
    127                boolean canUnassign = true;
    128                for (Lecture l : lects) {
    129                    if (l.isCommitted()) {
    130                        canUnassign = false;
    131                        break;
    132                    }
    133                    if (!conflicts.contains(l.getAssignment()))
    134                        placementsToUnassign.add(l.getAssignment());
    135                }
    136                if (!canUnassign)
    137                    continue;
    138                adepts.add(placementsToUnassign);
    139            }
    140            if (adepts.size() < overLimit) {
    141                conflicts.add(placement);
    142            } else {
    143                Collections.sort(adepts, new Comparator<List<Placement>>() {
    144                    @Override
    145                    public int compare(List<Placement> c1, List<Placement> c2) {
    146                        return Double.compare(c1.size(), c2.size());
    147                    }
    148                });
    149                for (int i = 0; i < overLimit; i++) {
    150                    conflicts.addAll(adepts.get(i));
    151                }
    152            }
    153        }
    154    }
    155
    156    @Override
    157    public boolean inConflict(Placement placeement) {
    158        return isOverLimit(placeement);
    159    }
    160
    161    @Override
    162    public boolean isConsistent(Placement value1, Placement value2) {
    163        return (isOverLimit(value1) || isOverLimit(value2));
    164    }
    165
    166    @Override
    167    public void assigned(long iteration, Placement placement) {
    168        super.assigned(iteration, placement);
    169        Lecture lecture = placement.variable();
    170        if (lecture.getNrRooms() <= 0)
    171            return;
    172        if (placement.isMultiRoom()) {
    173            for (RoomLocation r : placement.getRoomLocations()) {
    174                Set<Lecture> lects = iUsedRooms.get(r);
    175                if (lects == null) {
    176                    lects = new HashSet<Lecture>();
    177                    iUsedRooms.put(r, lects);
    178                }
    179                lects.add(lecture);
    180            }
    181        } else {
    182            RoomLocation r = placement.getRoomLocation();
    183            Set<Lecture> lects = iUsedRooms.get(r);
    184            if (lects == null) {
    185                lects = new HashSet<Lecture>();
    186                iUsedRooms.put(r, lects);
    187            }
    188            lects.add(lecture);
    189        }
    190    }
    191
    192    @Override
    193    public void unassigned(long iteration, Placement placement) {
    194        super.unassigned(iteration, placement);
    195        Lecture lecture = placement.variable();
    196        if (lecture.getNrRooms() <= 0)
    197            return;
    198        if (placement.isMultiRoom()) {
    199            for (RoomLocation r : placement.getRoomLocations()) {
    200                Set<Lecture> lects = iUsedRooms.get(r);
    201                if (lects != null) {
    202                    lects.remove(lecture);
    203                    if (lects.isEmpty())
    204                        iUsedRooms.remove(r);
    205                }
    206            }
    207        } else {
    208            RoomLocation r = placement.getRoomLocation();
    209            Set<Lecture> lects = iUsedRooms.get(r);
    210            if (lects != null) {
    211                lects.remove(lecture);
    212                if (lects.isEmpty())
    213                    iUsedRooms.remove(r);
    214            }
    215        }
    216    }
    217
    218    @Override
    219    public void weaken() {
    220        iUnassignment++;
    221        if (iUnassignmentsToWeaken > 0 && iUnassignment % iUnassignmentsToWeaken == 0)
    222            iLimit++;
    223    }
    224
    225    @Override
    226    public String getName() {
    227        return "Minimize number of used rooms";
    228    }
    229
    230    public int estimateLimit() {
    231        HashSet<RoomLocation> mandatoryRooms = new HashSet<RoomLocation>();
    232        for (Lecture lecture : variables()) {
    233            if (lecture.getNrRooms() == 0)
    234                continue;
    235            if (lecture.isCommitted() || lecture.roomLocations().size() == 1)
    236                mandatoryRooms.addAll(lecture.roomLocations());
    237        }
    238        double histogram[][] = new double[Constants.SLOTS_PER_DAY][Constants.NR_DAYS_WEEK];
    239        for (int i = 0; i < Constants.SLOTS_PER_DAY_NO_EVENINGS; i++)
    240            for (int j = 0; j < Constants.NR_DAYS_WEEK; j++)
    241                histogram[i][j] = 0.0;
    242        for (Lecture lecture : variables()) {
    243            if (lecture.getNrRooms() == 0)
    244                continue;
    245            List<Placement> values = lecture.values();
    246            for (Placement p : lecture.values()) {
    247                int firstSlot = p.getTimeLocation().getStartSlot();
    248                if (firstSlot > Constants.DAY_SLOTS_LAST)
    249                    continue;
    250                int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1;
    251                if (endSlot < Constants.DAY_SLOTS_FIRST)
    252                    continue;
    253                for (int i = firstSlot; i <= endSlot; i++) {
    254                    int dayCode = p.getTimeLocation().getDayCode();
    255                    for (int j = 0; j < Constants.NR_DAYS_WEEK; j++) {
    256                        if ((dayCode & Constants.DAY_CODES[j]) != 0) {
    257                            histogram[i][j] += ((double) lecture.getNrRooms()) / values.size();
    258                        }
    259                    }
    260                }
    261            }
    262        }
    263        int maxAverageRooms = 0;
    264        for (int i = 0; i < Constants.SLOTS_PER_DAY_NO_EVENINGS; i++)
    265            for (int j = 0; j < Constants.NR_DAYS_WEEK; j++)
    266                maxAverageRooms = Math.max(maxAverageRooms, (int) Math.ceil(histogram[i][j]));
    267        return Math.max(1, Math.max(mandatoryRooms.size(), maxAverageRooms));
    268    }
    269
    270    public void setEnabled(boolean enabled) {
    271        iEnabled = enabled;
    272        iLimit = Math.max(iUsedRooms.size(), estimateLimit());
    273    }
    274
    275    public boolean isEnabled() {
    276        return iEnabled;
    277    }
    278
    279    @Override
    280    public String toString() {
    281        StringBuffer sb = new StringBuffer();
    282        sb.append("Minimize Number Of Rooms Used between ");
    283        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
    284            Lecture v = e.next();
    285            sb.append(v.getName());
    286            if (e.hasNext())
    287                sb.append(", ");
    288        }
    289        return sb.toString();
    290    }
    291
    292    @Override
    293    public void weaken(Placement value) {
    294        if (isOverLimit(value))
    295            iLimit += getOverLimit(value);
    296    }
    297}