    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'><caption>Related Solver Parameters</caption>
    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 * @author  Tomáš Müller
    052 * @version StudentSct 1.3 (Student Sectioning)<br>
    053 *          Copyright (C) 2007 - 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 */
    071public class SectionLimit extends GlobalConstraint<Request, Enrollment> {
    072    private static double sNominalWeight = 0.00001;
    073    private boolean iPreferDummyStudents = false;
    074    private boolean iPreferPriorityStudents = true;
    075
    076    /**
    077     * Constructor
    078     *
    079     * @param cfg
    080     *            solver configuration
    081     */
    082    public SectionLimit(DataProperties cfg) {
    083        super();
    084        iPreferDummyStudents = cfg.getPropertyBoolean("SectionLimit.PreferDummyStudents", false);
    085        iPreferPriorityStudents = cfg.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true);
    086    }
    087
    088    /**
    089     * Enrollment weight of a section if the given request is assigned. In order
    090     * to overcome rounding problems with last-like students ( e.g., 5 students
    091     * are projected to two sections of limit 2 -- each section can have up to 3
    092     * of these last-like students), the weight of the request with the highest
    093     * weight in the section is changed to a small nominal weight.
    094     *
    095     * @param assignment current assignment
    096     * @param section
    097     *            a section that is of concern
    098     * @param request
    099     *            a request of a student to be assigned containing the given
    100     *            section
    101     * @return section's new weight
    102     */
    103    public static double getEnrollmentWeight(Assignment<Request, Enrollment> assignment, Section section, Request request) {
    104        return section.getEnrollmentWeight(assignment, request) + request.getWeight() - Math.max(section.getMaxEnrollmentWeight(assignment), request.getWeight()) + sNominalWeight;
    105    }
    106
    107    /**
    108     * Remaining unreserved space in a section if the given request is assigned. In order
    109     * to overcome rounding problems with last-like students ( e.g., 5 students
    110     * are projected to two sections of limit 2 -- each section can have up to 3
    111     * of these last-like students), the weight of the request with the highest
    112     * weight in the section is changed to a small nominal weight.
    113     *
    114     * @param assignment current assignment
    115     * @param section
    116     *            a section that is of concern
    117     * @param request
    118     *            a request of a student to be assigned containing the given
    119     *            section
    120     * @return section's new unreserved space
    121     */
    122    public static double getUnreservedSpace(Assignment<Request, Enrollment> assignment, Section section, Request request) {
    123        return section.getUnreservedSpace(assignment, request) - request.getWeight() + Math.max(section.getMaxEnrollmentWeight(assignment), request.getWeight()) - sNominalWeight;
    124    }
    125
    126
    127    /**
    128     * True if the enrollment has reservation for this section.
    129     * Everything else is checked in the {@link ReservationLimit} constraint.
    130     **/
    131    private boolean hasSectionReservation(Enrollment enrollment, Section section) {
    132        Reservation reservation = enrollment.getReservation();
    133        if (reservation == null) return false;
    134        Set<Section> sections = reservation.getSections(section.getSubpart());
    135        return sections != null && sections.contains(section);
    136    }
    137
    138    /**
    139     * A given enrollment is conflicting, if there is a section which limit
    140     * (computed by {@link SectionLimit#getEnrollmentWeight(Assignment, Section, Request)})
    141     * exceeds the section limit. <br>
    142     * For each of such sections, one or more existing enrollments are
    143     * (randomly) selected as conflicting until the overall weight is under the
    144     * limit.
    145     *
    146     * @param enrollment
    147     *            {@link Enrollment} that is being considered
    148     * @param conflicts
    149     *            all computed conflicting requests are added into this set
    150     */
    151    @Override
    152    public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) {
    153        // check reservation can assign over the limit
    154        if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit())
    155            return;
    156
    157        // exclude free time requests
    158        if (!enrollment.isCourseRequest())
    159            return;
    160
    161        // for each section
    162        for (Section section : enrollment.getSections()) {
    163
    164            // no reservation -- check the space in the unreserved space in the section
    165            if (enrollment.getConfig().getOffering().hasReservations() && !hasSectionReservation(enrollment, section)) {
    166                // section is fully reserved by section reservations
    167                if (section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) {
    168                    conflicts.add(enrollment);
    169                    return;
    170                }
    171
    172                double unreserved = getUnreservedSpace(assignment, section, enrollment.getRequest());
    173
    174                if (unreserved < 0.0) {
    175                    // no unreserved space available -> cannot be assigned
    176                    // try to unassign some other enrollments that also do not have reservation
    177
    178                    List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments(assignment).size());
    179                    for (Enrollment e : section.getEnrollments(assignment)) {
    180                        if (e.getRequest().equals(enrollment.getRequest()))
    181                            continue;
    182                        if (e.getReservation() != null && e.getReservation().canBatchAssignOverLimit())
    183                            continue;
    184                        if (hasSectionReservation(e, section))
    185                            continue;
    186                        if (conflicts.contains(e))
    187                            unreserved += e.getRequest().getWeight();
    188                        else
    189                            adepts.add(e);
    190                    }
    191
    192                    while (unreserved < 0.0) {
    193                        if (adepts.isEmpty()) {
    194                            // no adepts -> enrollment cannot be assigned
    195                            conflicts.add(enrollment);
    196                            return;
    197                        }
    198
    199                        // pick adept (prefer dummy students), decrease unreserved space,
    200                        // make conflict
    201                        Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get();
    202                        adepts.remove(conflict);
    203                        unreserved += conflict.getRequest().getWeight();
    204                        conflicts.add(conflict);
    205                    }
    206                }
    207            }
    208
    209            // unlimited section
    210            if (section.getLimit() < 0)
    211                continue;
    212
    213            // new enrollment weight
    214            double enrlWeight = getEnrollmentWeight(assignment, section, enrollment.getRequest());
    215
    216            // below limit -> ok
    217            if (enrlWeight <= section.getLimit())
    218                continue;
    219
    220            // above limit -> compute adepts (current assignments that are not
    221            // yet conflicting) exclude all conflicts as well
    222            List<Enrollment> adepts = new ArrayList<Enrollment>(section.getEnrollments(assignment).size());
    223            for (Enrollment e : section.getEnrollments(assignment)) {
    224                if (e.getRequest().equals(enrollment.getRequest()))
    225                    continue;
    226                if (conflicts.contains(e))
    227                    enrlWeight -= e.getRequest().getWeight();
    228                else
    229                    adepts.add(e);
    230            }
    231
    232            // while above limit -> pick an adept and make it conflicting
    233            while (enrlWeight > section.getLimit()) {
    234                if (adepts.isEmpty()) {
    235                    // no adepts -> enrollment cannot be assigned
    236                    conflicts.add(enrollment);
    237                    return;
    238                }
    239
    240                // pick adept (prefer dummy students & students w/o reservation), decrease enrollment
    241                // weight, make conflict
    242                Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get();
    243                adepts.remove(conflict);
    244                enrlWeight -= conflict.getRequest().getWeight();
    245                conflicts.add(conflict);
    246            }
    247        }
    248    }
    249
    250    /**
    251     * A given enrollment is conflicting, if there is a section which
    252     * limit(computed by
    253     * {@link SectionLimit#getEnrollmentWeight(Assignment, Section, Request)}) exceeds the
    254     * section limit.
    255     *
    256     * @param enrollment
    257     *            {@link Enrollment} that is being considered
    258     * @return true, if there is a section which will exceed its limit when the
    259     *         given enrollment is assigned
    260     */
    261    @Override
    262    public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
    263        // check reservation can assign over the limit
    264        if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit())
    265            return false;
    266
    267        // exclude free time requests
    268        if (!enrollment.isCourseRequest())
    269            return false;
    270
    271        // for each section
    272        for (Section section : enrollment.getSections()) {
    273
    274            // not have reservation -> check unreserved space
    275            if (enrollment.getConfig().getOffering().hasReservations() &&
    276                !hasSectionReservation(enrollment, section) && (
    277                section.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() ||
    278                getUnreservedSpace(assignment, section, enrollment.getRequest()) < 0.0))
    279                return true;
    280
    281            // unlimited section
    282            if (section.getLimit() < 0)
    283                continue;
    284
    285            // new enrollment weight
    286            double enrlWeight = getEnrollmentWeight(assignment, section, enrollment.getRequest());
    287
    288            // above limit -> conflict
    289            if (enrlWeight > section.getLimit())
    290                return true;
    291        }
    292
    293        // no conflicting section -> no conflict
    294        return false;
    295    }
    296
    297    @Override
    298    public String toString() {
    299        return "SectionLimit";
    300    }
    301}