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