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