    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.Course;
    012import org.cpsolver.studentsct.model.Enrollment;
    013import org.cpsolver.studentsct.model.Request;
    014
    015
    016/**
    017 * Course limit constraint. This global constraint ensures that a limit of each
    018 * course is not exceeded. This means that the total sum of weights of course
    019 * requests (see {@link Request#getWeight()}) enrolled into a course is below
    020 * the course's limit (see {@link Course#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 * Parameters:
    030 * <table border='1' summary='Related Solver Parameters'>
    031 * <tr>
    032 * <th>Parameter</th>
    033 * <th>Type</th>
    034 * <th>Comment</th>
    035 * </tr>
    036 * <tr>
    037 * <td>CourseLimit.PreferDummyStudents</td>
    038 * <td>{@link Boolean}</td>
    039 * <td>If true, requests of dummy (last-like) students are preferred to be
    040 * selected as conflicting.</td>
    041 * </tr>
    042 * </table>
    043 * <br>
    044 * <br>
    045 *
    046 * @version StudentSct 1.3 (Student Sectioning)<br>
    047 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    048 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    049 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    050 * <br>
    051 *          This library is free software; you can redistribute it and/or modify
    052 *          it under the terms of the GNU Lesser General Public License as
    053 *          published by the Free Software Foundation; either version 3 of the
    054 *          License, or (at your option) any later version. <br>
    055 * <br>
    056 *          This library is distributed in the hope that it will be useful, but
    057 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    058 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    059 *          Lesser General Public License for more details. <br>
    060 * <br>
    061 *          You should have received a copy of the GNU Lesser General Public
    062 *          License along with this library; if not see
    063 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    064 */
    065public class CourseLimit extends GlobalConstraint<Request, Enrollment> {
    066    private static double sNominalWeight = 0.00001;
    067    private boolean iPreferDummyStudents = false;
    068    private boolean iPreferPriorityStudents = true;
    069
    070    /**
    071     * Constructor
    072     *
    073     * @param cfg
    074     *            solver configuration
    075     */
    076    public CourseLimit(DataProperties cfg) {
    077        super();
    078        iPreferDummyStudents = cfg.getPropertyBoolean("CourseLimit.PreferDummyStudents", false);
    079        iPreferPriorityStudents = cfg.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true);
    080    }
    081
    082
    083    /**
    084     * Enrollment weight of a course if the given request is assigned. In order
    085     * to overcome rounding problems with last-like students ( e.g., 5 students
    086     * are projected to two sections of limit 2 -- each section can have up to 3
    087     * of these last-like students), the weight of the request with the highest
    088     * weight in the section is changed to a small nominal weight.
    089     *
    090     * @param assignment current assignment
    091     * @param course
    092     *            a course 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(Assignment<Request, Enrollment> assignment, Course course, Request request) {
    099        return course.getEnrollmentWeight(assignment, request) + request.getWeight() - Math.max(course.getMaxEnrollmentWeight(assignment), request.getWeight()) + sNominalWeight;
    100    }
    101
    102    /**
    103     * A given enrollment is conflicting, if the course's enrollment
    104     * (computed by {@link CourseLimit#getEnrollmentWeight(Assignment, Course, Request)})
    105     * exceeds the limit. <br>
    106     * If the limit is breached, one or more existing enrollments are
    107     * (randomly) selected as conflicting until the overall weight is under the
    108     * limit.
    109     *
    110     * @param enrollment
    111     *            {@link Enrollment} that is being considered
    112     * @param conflicts
    113     *            all computed conflicting requests are added into this set
    114     */
    115    @Override
    116    public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) {
    117        // check reservation can assign over the limit
    118        if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit())
    119            return;
    120
    121        // enrollment's course
    122        Course course = enrollment.getCourse();
    123
    124        // exclude free time requests
    125        if (course == null)
    126            return;
    127
    128        // exclude empty enrollmens
    129        if (enrollment.getSections() == null || enrollment.getSections().isEmpty())
    130            return;
    131
    132        // unlimited course
    133        if (course.getLimit() < 0)
    134            return;
    135
    136        // new enrollment weight
    137        double enrlWeight = getEnrollmentWeight(assignment, course, enrollment.getRequest());
    138
    139        // below limit -> ok
    140        if (enrlWeight <= course.getLimit())
    141            return;
    142
    143        // above limit -> compute adepts (current assignments that are not
    144        // yet conflicting)
    145        // exclude all conflicts as well
    146        List<Enrollment> adepts = new ArrayList<Enrollment>(course.getEnrollments(assignment).size());
    147        for (Enrollment e : course.getEnrollments(assignment)) {
    148            if (e.getRequest().equals(enrollment.getRequest()))
    149                continue;
    150            if (e.getReservation() != null && e.getReservation().canBatchAssignOverLimit())
    151                continue;
    152            if (conflicts.contains(e))
    153                enrlWeight -= e.getRequest().getWeight();
    154            else
    155                adepts.add(e);
    156        }
    157
    158        // while above limit -> pick an adept and make it conflicting
    159        while (enrlWeight > course.getLimit()) {
    160            if (adepts.isEmpty()) {
    161                // no adepts -> enrollment cannot be assigned
    162                conflicts.add(enrollment);
    163                break;
    164            }
    165
    166            // pick adept (prefer dummy students), decrease unreserved space,
    167            // make conflict
    168            Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get();
    169            adepts.remove(conflict);
    170            enrlWeight -= conflict.getRequest().getWeight();
    171            conflicts.add(conflict);
    172        }
    173    }
    174
    175    /**
    176     * A given enrollment is conflicting, if the course's enrollment (computed by
    177     * {@link CourseLimit#getEnrollmentWeight(Assignment, Course, Request)}) exceeds the
    178     * limit.
    179     *
    180     * @param enrollment
    181     *            {@link Enrollment} that is being considered
    182     * @return true, if the enrollment cannot be assigned without exceeding the limit
    183     */
    184    @Override
    185    public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
    186        // check reservation can assign over the limit
    187        if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit())
    188            return false;
    189
    190        // enrollment's course
    191        Course course = enrollment.getCourse();
    192
    193        // exclude free time requests
    194        if (course == null)
    195            return false;
    196
    197        // exclude empty enrollmens
    198        if (enrollment.getSections() == null || enrollment.getSections().isEmpty())
    199            return false;
    200
    201        // unlimited course
    202        if (course.getLimit() < 0)
    203            return false;
    204
    205
    206        // new enrollment weight
    207        double enrlWeight = getEnrollmentWeight(assignment, course, enrollment.getRequest());
    208
    209        // above limit -> conflict
    210        return (enrlWeight > course.getLimit());
    211    }
    212
    213    @Override
    214    public String toString() {
    215        return "CourseLimit";
    216    }
    217
    218}