    001package net.sf.cpsolver.studentsct.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.List;
    005import java.util.Set;
    006
    007import net.sf.cpsolver.ifs.model.GlobalConstraint;
    008import net.sf.cpsolver.ifs.util.DataProperties;
    009import net.sf.cpsolver.ifs.util.ToolBox;
    010import net.sf.cpsolver.studentsct.StudentSectioningModel;
    011import net.sf.cpsolver.studentsct.model.Enrollment;
    012import net.sf.cpsolver.studentsct.model.Request;
    013import net.sf.cpsolver.studentsct.model.Section;
    014import net.sf.cpsolver.studentsct.reservation.Reservation;
    015
    016/**
    017 * Section limit constraint. This global constraint ensures that a limit of each
    018 * section is not exceeded. This means that the total sum of weights of course
    019 * requests (see {@link Request#getWeight()}) enrolled into a section is below
    020 * the section's limit (see {@link Section#getLimit()}).
    021 *
    022 * <br>
    023 * <br>
    024 * Sections with negative limit are considered unlimited, and therefore
    025 * completely ignored by this constraint.
    026 *
    027 * <br>
    028 * <br>
    029 * This constraint also check section reservations.
    030 *
    031 * <br>
    032 * <br>
    033 * Parameters:
    034 * <table border='1'>
    035 * <tr>
    036 * <th>Parameter</th>
    037 * <th>Type</th>
    038 * <th>Comment</th>
    039 * </tr>
    040 * <tr>
    041 * <td>SectionLimit.PreferDummyStudents</td>
    042 * <td>{@link Boolean}</td>
    043 * <td>If true, requests of dummy (last-like) students are preferred to be
    044 * selected as conflicting.</td>
    045 * </tr>
    046 * </table>
    047 * <br>
    048 * <br>
    049 *
    050 * @version StudentSct 1.2 (Student Sectioning)<br>
    051 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    052 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    053 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    054 * <br>
    055 *          This library is free software; you can redistribute it and/or modify
    056 *          it under the terms of the GNU Lesser General Public License as
    057 *          published by the Free Software Foundation; either version 3 of the
    058 *          License, or (at your option) any later version. <br>
    059 * <br>
    060 *          This library is distributed in the hope that it will be useful, but
    061 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    062 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    063 *          Lesser General Public License for more details. <br>
    064 * <br>
    065 *          You should have received a copy of the GNU Lesser General Public
    066 *          License along with this library; if not see
    067 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    068 */
    069public class SectionLimit extends GlobalConstraint<Request, Enrollment> {
    070    private static double sNominalWeight = 0.00001;
    071    private boolean iPreferDummyStudents = false;
    072
    073    /**
    074     * Constructor
    075     *
    076     * @param cfg
    077     *            solver configuration
    078     */
    079    public SectionLimit(DataProperties cfg) {
    080        super();
    081        iPreferDummyStudents = cfg.getPropertyBoolean("SectionLimit.PreferDummyStudents", false);
    082    }
    083
    084    /**
    085     * Enrollment weight of a section if the given request is assigned. In order
    086     * to overcome rounding problems with last-like students ( e.g., 5 students
    087     * are projected to two sections of limit 2 -- each section can have up to 3
    088     * of these last-like students), the weight of the request with the highest
    089     * weight in the section is changed to a small nominal weight.
    090     *
    091     * @param section
    092     *            a section that is of concern
    093     * @param request
    094     *            a request of a student to be assigned containing the given
    095     *            section
    096     * @return section's new weight
    097     */
    098    public static double getEnrollmentWeight(Section section, Request request) {
    099        return section.getEnrollmentWeight(request) + request.getWeight()
    100                - Math.max(section.getMaxEnrollmentWeight(), request.getWeight()) + sNominalWeight;
    101    }
    102
    103    /**
    104     * Remaining unreserved space in a section if the given request is assigned. In order
    105     * to overcome rounding problems with last-like students ( e.g., 5 students
    106     * are projected to two sections of limit 2 -- each section can have up to 3
    107     * of these last-like students), the weight of the request with the highest
    108     * weight in the section is changed to a small nominal weight.
    109     *
    110     * @param section
    111     *            a section that is of concern
    112     * @param request
    113     *            a request of a student to be assigned containing the given
    114     *            section
    115     * @return section's new unreserved space
    116     */
    117    public static double getUnreservedSpace(Section section, Request request) {
    118        return section.getUnreservedSpace(request) - request.getWeight()
    119                + Math.max(section.getMaxEnrollmentWeight(), request.getWeight()) - sNominalWeight;
    120    }
    121
    122
    123    /**
    124     * True if the enrollment has reservation for this section.
    125     * Everything else is checked in the {@link ReservationLimit} constraint.
    126     **/
    127    private boolean hasSectionReservation(Enrollment enrollment, Section section) {
    128        Reservation reservation = enrollment.getReservation();
    129        if (reservation == null) return false;
    130        Set<Section> sections = reservation.getSections(section.getSubpart());
    131        return sections != null && sections.contains(section);
    132    }
    133
    134    /**
    135     * A given enrollment is conflicting, if there is a section which limit
    136     * (computed by {@link SectionLimit#getEnrollmentWeight(Section, Request)})
    137     * exceeds the section limit. <br>
    138     * For each of such sections, one or more existing enrollments are
    139     * (randomly) selected as conflicting until the overall weight is under the
    140     * limit.
    141     *
    142     * @param enrollment
    143     *            {@link Enrollment} that is being considered
    144     * @param conflicts
    145     *            all computed conflicting requests are added into this set
    146     */
    147    @Override
    148    public void computeConflicts(Enrollment enrollment, Set<Enrollment> conflicts) {
    149        // check reservation can assign over the limit
    150        if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
    151            enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
    152            return;
    153
    154        // exclude free time requests
    155        if (!enrollment.isCourseRequest())
    156            return;
    157
    158        // for each section
    159        for (Section section : enrollment.getSections()) {
    160
    161            // no reservation -- check the space in the unreserved space in the section
    162            if (enrollment.getConfig().getOffering().hasReservations() && !hasSectionReservation(enrollment, section)) {
    163                // section is fully reserved by section reservations
    164                if (section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) {
    165                    conflicts.add(enrollment);
    166                    return;
    167                }
    168
    169                double unreserved = getUnreservedSpace(section, enrollment.getRequest());
    170
    171                if (unreserved < 0.0) {
    172                    // no unreserved space available -> cannot be assigned
    173                    // try to unassign some other enrollments that also do not have reservation
    174
    175                    List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments().size());
    176                    for (Enrollment e : section.getEnrollments()) {
    177                        if (e.getRequest().equals(enrollment.getRequest()))
    178                            continue;
    179                        if (hasSectionReservation(e, section))
    180                            continue;
    181                        if (conflicts.contains(e))
    182                            unreserved += e.getRequest().getWeight();
    183                        else
    184                            adepts.add(e);
    185                    }
    186
    187                    while (unreserved < 0.0) {
    188                        if (adepts.isEmpty()) {
    189                            // no adepts -> enrollment cannot be assigned
    190                            conflicts.add(enrollment);
    191                            return;
    192                        }
    193
    194                        // pick adept (prefer dummy students), decrease unreserved space,
    195                        // make conflict
    196                        List<Enrollment> best = new ArrayList<Enrollment>();
    197                        boolean bestDummy = false;
    198                        double bestValue = 0;
    199                        for (Enrollment adept: adepts) {
    200                            boolean dummy = adept.getStudent().isDummy();
    201                            double value = adept.toDouble(false);
    202
    203                            if (iPreferDummyStudents && dummy != bestDummy) {
    204                                if (dummy) {
    205                                    best.clear();
    206                                    best.add(adept);
    207                                    bestDummy = dummy;
    208                                    bestValue = value;
    209                                }
    210                                continue;
    211                            }
    212
    213                            if (best.isEmpty() || value > bestValue) {
    214                                if (best.isEmpty()) best.clear();
    215                                best.add(adept);
    216                                bestDummy = dummy;
    217                                bestValue = value;
    218                            } else if (bestValue == value) {
    219                                best.add(adept);
    220                            }
    221                        }
    222
    223                        Enrollment conflict = ToolBox.random(best);
    224                        adepts.remove(conflict);
    225                        unreserved += conflict.getRequest().getWeight();
    226                        conflicts.add(conflict);
    227                    }
    228                }
    229            }
    230
    231            // unlimited section
    232            if (section.getLimit() < 0)
    233                continue;
    234
    235            // new enrollment weight
    236            double enrlWeight = getEnrollmentWeight(section, enrollment.getRequest());
    237
    238            // below limit -> ok
    239            if (enrlWeight <= section.getLimit())
    240                continue;
    241
    242            // above limit -> compute adepts (current assignments that are not
    243            // yet conflicting) exclude all conflicts as well
    244            List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments().size());
    245            for (Enrollment e : section.getEnrollments()) {
    246                if (e.getRequest().equals(enrollment.getRequest()))
    247                    continue;
    248                if (conflicts.contains(e))
    249                    enrlWeight -= e.getRequest().getWeight();
    250                else
    251                    adepts.add(e);
    252            }
    253
    254            // while above limit -> pick an adept and make it conflicting
    255            while (enrlWeight > section.getLimit()) {
    256                if (adepts.isEmpty()) {
    257                    // no adepts -> enrollment cannot be assigned
    258                    conflicts.add(enrollment);
    259                    return;
    260                }
    261
    262                // pick adept (prefer dummy students & students w/o reservation), decrease enrollment
    263                // weight, make conflict
    264                List<Enrollment> best = new ArrayList<Enrollment>();
    265                boolean bestDummy = false;
    266                double bestValue = 0;
    267                boolean bestRes = true;
    268                for (Enrollment adept: adepts) {
    269                    boolean dummy = adept.getStudent().isDummy();
    270                    double value = adept.toDouble(false);
    271                    boolean res = hasSectionReservation(adept, section);
    272
    273                    if (iPreferDummyStudents && dummy != bestDummy) {
    274                        if (dummy) {
    275                            best.clear();
    276                            best.add(adept);
    277                            bestDummy = dummy;
    278                            bestValue = value;
    279                            bestRes = res;
    280                        }
    281                        continue;
    282                    }
    283
    284                    if (bestRes != res) {
    285                        if (!res) {
    286                            best.clear();
    287                            best.add(adept);
    288                            bestDummy = dummy;
    289                            bestValue = value;
    290                            bestRes = res;
    291                        }
    292                        continue;
    293                    }
    294
    295                    if (best.isEmpty() || value > bestValue) {
    296                        if (best.isEmpty()) best.clear();
    297                        best.add(adept);
    298                        bestDummy = dummy;
    299                        bestValue = value;
    300                        bestRes = res;
    301                    } else if (bestValue == value) {
    302                        best.add(adept);
    303                    }
    304                }
    305
    306                Enrollment conflict = ToolBox.random(best);
    307                adepts.remove(conflict);
    308                enrlWeight -= conflict.getRequest().getWeight();
    309                conflicts.add(conflict);
    310            }
    311        }
    312    }
    313
    314    /**
    315     * A given enrollment is conflicting, if there is a section which
    316     * limit(computed by
    317     * {@link SectionLimit#getEnrollmentWeight(Section, Request)}) exceeds the
    318     * section limit.
    319     *
    320     * @param enrollment
    321     *            {@link Enrollment} that is being considered
    322     * @return true, if there is a section which will exceed its limit when the
    323     *         given enrollment is assigned
    324     */
    325    @Override
    326    public boolean inConflict(Enrollment enrollment) {
    327        // check reservation can assign over the limit
    328        if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
    329            enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
    330            return false;
    331
    332        // exclude free time requests
    333        if (!enrollment.isCourseRequest())
    334            return false;
    335
    336        // for each section
    337        for (Section section : enrollment.getSections()) {
    338
    339            // not have reservation -> check unreserved space
    340            if (enrollment.getConfig().getOffering().hasReservations() &&
    341                !hasSectionReservation(enrollment, section) && (
    342                section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() ||
    343                getUnreservedSpace(section, enrollment.getRequest()) < 0.0))
    344                return true;
    345
    346            // unlimited section
    347            if (section.getLimit() < 0)
    348                continue;
    349
    350            // new enrollment weight
    351            double enrlWeight = getEnrollmentWeight(section, enrollment.getRequest());
    352
    353            // above limit -> conflict
    354            if (enrlWeight > section.getLimit())
    355                return true;
    356        }
    357
    358        // no conflicting section -> no conflict
    359        return false;
    360    }
    361
    362    @Override
    363    public String toString() {
    364        return "SectionLimit";
    365    }
    366}