    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.Iterator;
    008import java.util.List;
    009import java.util.Set;
    010
    011import net.sf.cpsolver.coursett.Constants;
    012import net.sf.cpsolver.coursett.model.Lecture;
    013import net.sf.cpsolver.coursett.model.Placement;
    014import net.sf.cpsolver.coursett.model.TimeLocation;
    015import net.sf.cpsolver.ifs.model.Constraint;
    016import net.sf.cpsolver.ifs.model.WeakeningConstraint;
    017import net.sf.cpsolver.ifs.util.DataProperties;
    018
    019/**
    020 * Minimize number of used groups of time within a set of classes. <br>
    021 * <br>
    022 *
    023 * This constraint implements the following distribution/group constraints: <br>
    024 * <br>
    025 *
    026 * MIN_GRUSE(10x1h) (Minimize Use Of 1h Groups)<br>
    027 * Minimize number of groups of time that are used by the given classes. The
    028 * time is spread into the following 10 groups of one hour: 7:30a-8:30a,
    029 * 8:30a-9:30a, 9:30a-10:30a, ... 4:30p-5:30p. <br>
    030 * <br>
    031 *
    032 * MIN_GRUSE(5x2h) (Minimize Use Of 2h Groups)<br>
    033 * Minimize number of groups of time that are used by the given classes. The
    034 * time is spread into the following 5 groups of two hours: 7:30a-9:30a,
    035 * 9:30a-11:30a, 11:30a-1:30p, 1:30p-3:30p, 3:30p-5:30p. <br>
    036 * <br>
    037 *
    038 * MIN_GRUSE(3x3h) (Minimize Use Of 3h Groups)<br>
    039 * Minimize number of groups of time that are used by the given classes. The
    040 * time is spread into the following 3 groups: 7:30a-10:30a, 10:30a-2:30p,
    041 * 2:30p-5:30p. <br>
    042 * <br>
    043 *
    044 * MIN_GRUSE(2x5h) (Minimize Use Of 5h Groups)<br>
    045 * Minimize number of groups of time that are used by the given classes. The
    046 * time is spread into the following 2 groups: 7:30a-12:30a, 12:30a-5:30p.
    047 *
    048 * @version CourseTT 1.2 (University Course Timetabling)<br>
    049 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    050 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    051 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    052 * <br>
    053 *          This library is free software; you can redistribute it and/or modify
    054 *          it under the terms of the GNU Lesser General Public License as
    055 *          published by the Free Software Foundation; either version 3 of the
    056 *          License, or (at your option) any later version. <br>
    057 * <br>
    058 *          This library is distributed in the hope that it will be useful, but
    059 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    060 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    061 *          Lesser General Public License for more details. <br>
    062 * <br>
    063 *          You should have received a copy of the GNU Lesser General Public
    064 *          License along with this library; if not see
    065 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    066 */
    067
    068public class MinimizeNumberOfUsedGroupsOfTime extends Constraint<Lecture, Placement> implements WeakeningConstraint<Lecture, Placement> {
    069    private int iUnassignmentsToWeaken = 250;
    070    private long iUnassignment = 0;
    071    private int iLimit = 1;
    072    private GroupOfTime iGroupsOfTime[];
    073    private HashSet<Placement> iUsage[];
    074    private boolean iEnabled = false;
    075
    076    private String iName = null;
    077
    078    public static GroupOfTime[] sGroups2of5h = new GroupOfTime[] {
    079            new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(12, 30), Constants.DAY_CODE_ALL),
    080            new GroupOfTime(Constants.time2slot(12, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL), };
    081    public static GroupOfTime[] sGroups3of3h = new GroupOfTime[] {
    082            new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(10, 30), Constants.DAY_CODE_ALL),
    083            new GroupOfTime(Constants.time2slot(10, 30), Constants.time2slot(14, 30), Constants.DAY_CODE_ALL),
    084            new GroupOfTime(Constants.time2slot(14, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) };
    085    public static GroupOfTime[] sGroups5of2h = new GroupOfTime[] {
    086            new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(9, 30), Constants.DAY_CODE_ALL),
    087            new GroupOfTime(Constants.time2slot(9, 30), Constants.time2slot(11, 30), Constants.DAY_CODE_ALL),
    088            new GroupOfTime(Constants.time2slot(11, 30), Constants.time2slot(13, 30), Constants.DAY_CODE_ALL),
    089            new GroupOfTime(Constants.time2slot(13, 30), Constants.time2slot(15, 30), Constants.DAY_CODE_ALL),
    090            new GroupOfTime(Constants.time2slot(15, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) };
    091    public static GroupOfTime[] sGroups10of1h = new GroupOfTime[] {
    092            new GroupOfTime(Constants.time2slot(7, 30), Constants.time2slot(8, 30), Constants.DAY_CODE_ALL),
    093            new GroupOfTime(Constants.time2slot(8, 30), Constants.time2slot(9, 30), Constants.DAY_CODE_ALL),
    094            new GroupOfTime(Constants.time2slot(9, 30), Constants.time2slot(10, 30), Constants.DAY_CODE_ALL),
    095            new GroupOfTime(Constants.time2slot(10, 30), Constants.time2slot(11, 30), Constants.DAY_CODE_ALL),
    096            new GroupOfTime(Constants.time2slot(11, 30), Constants.time2slot(12, 30), Constants.DAY_CODE_ALL),
    097            new GroupOfTime(Constants.time2slot(12, 30), Constants.time2slot(13, 30), Constants.DAY_CODE_ALL),
    098            new GroupOfTime(Constants.time2slot(13, 30), Constants.time2slot(14, 30), Constants.DAY_CODE_ALL),
    099            new GroupOfTime(Constants.time2slot(14, 30), Constants.time2slot(15, 30), Constants.DAY_CODE_ALL),
    100            new GroupOfTime(Constants.time2slot(15, 30), Constants.time2slot(16, 30), Constants.DAY_CODE_ALL),
    101            new GroupOfTime(Constants.time2slot(16, 30), Constants.time2slot(17, 30), Constants.DAY_CODE_ALL) };
    102
    103    @SuppressWarnings("unchecked")
    104    public MinimizeNumberOfUsedGroupsOfTime(DataProperties config, String name, GroupOfTime[] groupsOfTime) {
    105        iGroupsOfTime = groupsOfTime;
    106        iUnassignmentsToWeaken = config.getPropertyInt("MinimizeNumberOfUsedGroupsOfTime.Unassignments2Weaken",
    107                iUnassignmentsToWeaken);
    108        iName = name;
    109        iUsage = new HashSet[iGroupsOfTime.length];
    110        for (int i = 0; i < iUsage.length; i++)
    111            iUsage[i] = new HashSet<Placement>();
    112    }
    113
    114    public int currentUsage() {
    115        int ret = 0;
    116        for (int i = 0; i < iUsage.length; i++)
    117            if (!iUsage[i].isEmpty())
    118                ret++;
    119        return ret;
    120    }
    121
    122    @Override
    123    public void weaken() {
    124        iUnassignment++;
    125        if (iUnassignmentsToWeaken > 0 && iUnassignment % iUnassignmentsToWeaken == 0)
    126            iLimit++;
    127    }
    128
    129    public boolean isOverLimit(Placement placement) {
    130        return getOverLimit(placement) > 0;
    131    }
    132
    133    public int getOverLimit(Placement placement) {
    134        if (!iEnabled)
    135            return 0; // not enabled
    136        if (iUnassignmentsToWeaken == 0)
    137            return 0; // not working
    138
    139        Lecture lecture = placement.variable();
    140        TimeLocation time = placement.getTimeLocation();
    141
    142        if (lecture.isCommitted())
    143            return 0; // commited class
    144
    145        int usage = 0;
    146        for (int i = 0; i < iGroupsOfTime.length; i++) {
    147            GroupOfTime groupOfTime = iGroupsOfTime[i];
    148            if (!iUsage[i].isEmpty() || groupOfTime.overlap(time))
    149                usage++;
    150        }
    151
    152        return usage - iLimit;
    153    }
    154
    155    public int estimateLimit() {
    156        int nrSlotsUsed = 0;
    157        int minSlotsUsed = 0;
    158        boolean firstLecture = true;
    159        for (Lecture lecture : variables()) {
    160            boolean first = true;
    161            int minSlotsUsedThisLecture = 0;
    162            for (TimeLocation time : lecture.timeLocations()) {
    163                int min = 0;
    164                for (int i = 0; i < iGroupsOfTime.length; i++) {
    165                    if (iGroupsOfTime[i].overlap(time))
    166                        min++;
    167                }
    168                if (first) {
    169                    nrSlotsUsed += time.getLength() * time.getNrMeetings();
    170                    minSlotsUsedThisLecture = min;
    171                    first = false;
    172                } else {
    173                    minSlotsUsedThisLecture = Math.min(minSlotsUsedThisLecture, min);
    174                }
    175            }
    176            if (firstLecture) {
    177                minSlotsUsed = minSlotsUsedThisLecture;
    178                firstLecture = false;
    179            } else {
    180                minSlotsUsed = Math.min(minSlotsUsed, minSlotsUsedThisLecture);
    181            }
    182        }
    183        return Math.max(Math.max(1, (int) Math.ceil(((double) nrSlotsUsed) / iGroupsOfTime[0].size())), minSlotsUsed);
    184    }
    185
    186    @Override
    187    public void computeConflicts(Placement placement, Set<Placement> conflicts) {
    188        int overLimit = getOverLimit(placement);
    189        if (overLimit > 0) {
    190            TimeLocation time = placement.getTimeLocation();
    191
    192            List<List<Placement>> adepts = new ArrayList<List<Placement>>();
    193            for (int i = 0; i < iGroupsOfTime.length; i++) {
    194                GroupOfTime groupOfTime = iGroupsOfTime[i];
    195                HashSet<Placement> usage = iUsage[i];
    196                if (groupOfTime.overlap(time) || usage.isEmpty())
    197                    continue;
    198                boolean canUnassign = true;
    199                List<Placement> placementsToUnassign = new ArrayList<Placement>(usage.size());
    200                for (Placement p : usage) {
    201                    Lecture l = p.variable();
    202                    if (l.isCommitted()) {
    203                        canUnassign = false;
    204                        break;
    205                    }
    206                    if (!conflicts.contains(p))
    207                        placementsToUnassign.add(p);
    208                }
    209                if (!canUnassign)
    210                    continue;
    211                adepts.add(placementsToUnassign);
    212            }
    213            if (adepts.size() < overLimit) {
    214                conflicts.add(placement);
    215            } else {
    216                Collections.sort(adepts, new Comparator<List<Placement>>() {
    217                    @Override
    218                    public int compare(List<Placement> c1, List<Placement> c2) {
    219                        return Double.compare(c1.size(), c2.size());
    220                    }
    221                });
    222                for (int i = 0; i < overLimit; i++) {
    223                    conflicts.addAll(adepts.get(i));
    224                }
    225            }
    226        }
    227    }
    228
    229    @Override
    230    public boolean inConflict(Placement placement) {
    231        return isOverLimit(placement);
    232    }
    233
    234    @Override
    235    public boolean isConsistent(Placement value1, Placement value2) {
    236        return (isOverLimit(value1) || isOverLimit(value2));
    237    }
    238
    239    @Override
    240    public void assigned(long iteration, Placement placement) {
    241        super.assigned(iteration, placement);
    242        TimeLocation time = placement.getTimeLocation();
    243        for (int i = 0; i < iGroupsOfTime.length; i++) {
    244            GroupOfTime groupOfTime = iGroupsOfTime[i];
    245            HashSet<Placement> usage = iUsage[i];
    246            if (groupOfTime.overlap(time))
    247                usage.add(placement);
    248        }
    249    }
    250
    251    @Override
    252    public void unassigned(long iteration, Placement placement) {
    253        super.unassigned(iteration, placement);
    254        TimeLocation time = placement.getTimeLocation();
    255        for (int i = 0; i < iGroupsOfTime.length; i++) {
    256            GroupOfTime groupOfTime = iGroupsOfTime[i];
    257            HashSet<Placement> usage = iUsage[i];
    258            if (groupOfTime.overlap(time))
    259                usage.remove(placement);
    260        }
    261    }
    262
    263    public String getConstraintName() {
    264        return "MIN_GRUSE(" + iName + ")";
    265    }
    266
    267    @Override
    268    public String getName() {
    269        return "Minimize number of used groups of time (" + iName + ")";
    270    }
    271
    272    public void setEnabled(boolean enabled) {
    273        iEnabled = enabled;
    274        iLimit = Math.max(currentUsage(), estimateLimit());
    275    }
    276
    277    public boolean isEnabled() {
    278        return iEnabled;
    279    }
    280
    281    private static class GroupOfTime {
    282        private int iStartSlot = 0;
    283        private int iEndSlot = 0;
    284        private int iDays = 0;
    285
    286        public GroupOfTime(int startSlot, int endSlot, int days) {
    287            iStartSlot = startSlot;
    288            iEndSlot = endSlot;
    289            iDays = days;
    290        }
    291
    292        public int getStartSlot() {
    293            return iStartSlot;
    294        }
    295
    296        public int getEndSlot() {
    297            return iEndSlot;
    298        }
    299
    300        public int getDays() {
    301            return iDays;
    302        }
    303
    304        public int nrDays() {
    305            int ret = 0;
    306            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    307                if ((getDays() & Constants.DAY_CODES[i]) != 0)
    308                    ret++;
    309            }
    310            return ret;
    311        }
    312
    313        public int size() {
    314            return (getEndSlot() - getStartSlot()) * nrDays();
    315        }
    316
    317        public boolean overlap(TimeLocation timeLocation) {
    318            if ((timeLocation.getDayCode() & iDays) == 0)
    319                return false;
    320            int end = Math.min(iEndSlot, timeLocation.getStartSlot() + timeLocation.getLength());
    321            int start = Math.max(iStartSlot, timeLocation.getStartSlot());
    322            int nrSharedSlots = (end < start ? 0 : end - start);
    323            return (nrSharedSlots > 0);
    324        }
    325    }
    326
    327    @Override
    328    public String toString() {
    329        StringBuffer sb = new StringBuffer();
    330        sb.append("Minimize Use Of "
    331                + (Constants.SLOT_LENGTH_MIN * (iGroupsOfTime[0].getEndSlot() - iGroupsOfTime[0].getStartSlot()))
    332                + "min Groups between ");
    333        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
    334            Lecture v = e.next();
    335            sb.append(v.getName());
    336            if (e.hasNext())
    337                sb.append(", ");
    338        }
    339        return sb.toString();
    340    }
    341
    342    @Override
    343    public void weaken(Placement value) {
    344        if (isOverLimit(value))
    345            iLimit += getOverLimit(value);
    346    }
    347
    348}