    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.Config;
    012import net.sf.cpsolver.studentsct.model.Enrollment;
    013import net.sf.cpsolver.studentsct.model.Request;
    014
    015/**
    016 * Configuration limit constraint. This global constraint ensures that a limit of each
    017 * configuration is not exceeded. This means that the total sum of weights of course
    018 * requests (see {@link Request#getWeight()}) enrolled into a configuration is below
    019 * the configuration's limit (see {@link Config#getLimit()}).
    020 *
    021 * <br>
    022 * <br>
    023 * Configurations 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>ConfigLimit.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 ConfigLimit extends GlobalConstraint<Request, Enrollment> {
    065
    066    private static double sNominalWeight = 0.00001;
    067    private boolean iPreferDummyStudents = false;
    068
    069    /**
    070     * Constructor
    071     *
    072     * @param cfg
    073     *            solver configuration
    074     */
    075    public ConfigLimit(DataProperties cfg) {
    076        super();
    077        iPreferDummyStudents = cfg.getPropertyBoolean("ConfigLimit.PreferDummyStudents", false);
    078    }
    079
    080
    081    /**
    082     * Enrollment weight of a config if the given request is assigned. In order
    083     * to overcome rounding problems with last-like students ( e.g., 5 students
    084     * are projected to two configs of limit 2 -- each section can have up to 3
    085     * of these last-like students), the weight of the request with the highest
    086     * weight in the config is changed to a small nominal weight.
    087     *
    088     * @param config
    089     *            a config that is of concern
    090     * @param request
    091     *            a request of a student to be assigned containing the given
    092     *            section
    093     * @return section's new weight
    094     */
    095    public static double getEnrollmentWeight(Config config, Request request) {
    096        return config.getEnrollmentWeight(request) + request.getWeight()
    097                - Math.max(config.getMaxEnrollmentWeight(), request.getWeight()) + sNominalWeight;
    098    }
    099
    100    /**
    101     * A given enrollment is conflicting, if the config's enrollment
    102     * (computed by {@link ConfigLimit#getEnrollmentWeight(Config, Request)})
    103     * exceeds the limit. <br>
    104     * If the limit is breached, one or more existing enrollments are
    105     * (randomly) selected as conflicting until the overall weight is under the
    106     * limit.
    107     *
    108     * @param enrollment
    109     *            {@link Enrollment} that is being considered
    110     * @param conflicts
    111     *            all computed conflicting requests are added into this set
    112     */
    113    @Override
    114    public void computeConflicts(Enrollment enrollment, Set<Enrollment> conflicts) {
    115        // check reservation can assign over the limit
    116        if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
    117            enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
    118            return;
    119
    120        // enrollment's config
    121        Config config = enrollment.getConfig();
    122
    123        // exclude free time requests
    124        if (config == null)
    125            return;
    126
    127
    128        // unlimited config
    129        if (config.getLimit() < 0)
    130            return;
    131
    132        // new enrollment weight
    133        double enrlWeight = getEnrollmentWeight(config, enrollment.getRequest());
    134
    135        // below limit -> ok
    136        if (enrlWeight <= config.getLimit())
    137            return;
    138
    139        // above limit -> compute adepts (current assignments that are not
    140        // yet conflicting)
    141        // exclude all conflicts as well
    142        List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments().size());
    143        for (Enrollment e : config.getEnrollments()) {
    144            if (e.getRequest().equals(enrollment.getRequest()))
    145                continue;
    146            if (conflicts.contains(e))
    147                enrlWeight -= e.getRequest().getWeight();
    148            else
    149                adepts.add(e);
    150        }
    151
    152        // while above limit -> pick an adept and make it conflicting
    153        while (enrlWeight > config.getLimit()) {
    154            if (adepts.isEmpty()) {
    155                // no adepts -> enrollment cannot be assigned
    156                conflicts.add(enrollment);
    157                return;
    158            }
    159
    160            // pick adept (prefer dummy students & students w/o reservation), decrease enrollment
    161            // weight, make conflict
    162            List<Enrollment> best = new ArrayList<Enrollment>();
    163            boolean bestDummy = false;
    164            double bestValue = 0;
    165            boolean bestRes = true;
    166            for (Enrollment adept: adepts) {
    167                boolean dummy = adept.getStudent().isDummy();
    168                double value = adept.toDouble(false);
    169                boolean res = (adept.getReservation() != null);
    170
    171                if (iPreferDummyStudents && dummy != bestDummy) {
    172                    if (dummy) {
    173                        best.clear();
    174                        best.add(adept);
    175                        bestDummy = dummy;
    176                        bestValue = value;
    177                        bestRes = res;
    178                    }
    179                    continue;
    180                }
    181
    182                if (bestRes != res) {
    183                    if (!res) {
    184                        best.clear();
    185                        best.add(adept);
    186                        bestDummy = dummy;
    187                        bestValue = value;
    188                        bestRes = res;
    189                    }
    190                    continue;
    191                }
    192
    193                if (best.isEmpty() || value > bestValue) {
    194                    if (best.isEmpty()) best.clear();
    195                    best.add(adept);
    196                    bestDummy = dummy;
    197                    bestValue = value;
    198                    bestRes = res;
    199                } else if (bestValue == value) {
    200                    best.add(adept);
    201                }
    202            }
    203
    204            Enrollment conflict = ToolBox.random(best);
    205            adepts.remove(conflict);
    206            enrlWeight -= conflict.getRequest().getWeight();
    207            conflicts.add(conflict);
    208        }
    209    }
    210
    211    /**
    212     * A given enrollment is conflicting, if the config's enrollment (computed by
    213     * {@link ConfigLimit#getEnrollmentWeight(Config, Request)}) exceeds the
    214     * limit.
    215     *
    216     * @param enrollment
    217     *            {@link Enrollment} that is being considered
    218     * @return true, if the enrollment cannot be assigned without exceeding the limit
    219     */
    220    @Override
    221    public boolean inConflict(Enrollment enrollment) {
    222        // check reservation can assign over the limit
    223        if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
    224            enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
    225            return false;
    226
    227        // enrollment's config
    228        Config config = enrollment.getConfig();
    229
    230        // exclude free time requests
    231        if (config == null)
    232            return false;
    233
    234        // unlimited config
    235        if (config.getLimit() < 0)
    236            return false;
    237
    238
    239        // new enrollment weight
    240        double enrlWeight = getEnrollmentWeight(config, enrollment.getRequest());
    241
    242        // above limit -> conflict
    243        return (enrlWeight > config.getLimit());
    244    }
    245
    246    @Override
    247    public String toString() {
    248        return "ConfigLimit";
    249    }
    250
    251}