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