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