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