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