    001package org.cpsolver.studentsct.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    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.ifs.util.ToolBox;
    011import org.cpsolver.studentsct.model.Config;
    012import org.cpsolver.studentsct.model.Enrollment;
    013import org.cpsolver.studentsct.model.Request;
    014import org.cpsolver.studentsct.model.Request.RequestPriority;
    015import org.cpsolver.studentsct.model.Student.StudentPriority;
    016
    017
    018/**
    019 * Configuration limit constraint. This global constraint ensures that a limit of each
    020 * configuration is not exceeded. This means that the total sum of weights of course
    021 * requests (see {@link Request#getWeight()}) enrolled into a configuration is below
    022 * the configuration's limit (see {@link Config#getLimit()}).
    023 *
    024 * <br>
    025 * <br>
    026 * Configurations with negative limit are considered unlimited, and therefore
    027 * completely ignored by this constraint.
    028 *
    029 * <br>
    030 * <br>
    031 * Parameters:
    032 * <table border='1' summary='Related Solver Parameters'>
    033 * <tr>
    034 * <th>Parameter</th>
    035 * <th>Type</th>
    036 * <th>Comment</th>
    037 * </tr>
    038 * <tr>
    039 * <td>ConfigLimit.PreferDummyStudents</td>
    040 * <td>{@link Boolean}</td>
    041 * <td>If true, requests of dummy (last-like) students are preferred to be
    042 * selected as conflicting.</td>
    043 * </tr>
    044 * </table>
    045 * <br>
    046 * <br>
    047 *
    048 * @version StudentSct 1.3 (Student Sectioning)<br>
    049 *          Copyright (C) 2007 - 2014 Tomáš Müller<br>
    050 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    051 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    052 * <br>
    053 *          This library is free software; you can redistribute it and/or modify
    054 *          it under the terms of the GNU Lesser General Public License as
    055 *          published by the Free Software Foundation; either version 3 of the
    056 *          License, or (at your option) any later version. <br>
    057 * <br>
    058 *          This library is distributed in the hope that it will be useful, but
    059 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    060 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    061 *          Lesser General Public License for more details. <br>
    062 * <br>
    063 *          You should have received a copy of the GNU Lesser General Public
    064 *          License along with this library; if not see
    065 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    066 */
    067public class ConfigLimit extends GlobalConstraint<Request, Enrollment> {
    068
    069    private static double sNominalWeight = 0.00001;
    070    private boolean iPreferDummyStudents = false;
    071    private boolean iPreferPriorityStudents = true;
    072
    073    /**
    074     * Constructor
    075     *
    076     * @param cfg
    077     *            solver configuration
    078     */
    079    public ConfigLimit(DataProperties cfg) {
    080        super();
    081        iPreferDummyStudents = cfg.getPropertyBoolean("ConfigLimit.PreferDummyStudents", false);
    082        iPreferPriorityStudents = cfg.getPropertyBoolean("Sectioning.PriorityStudentsFirstSelection.AllIn", true);
    083    }
    084
    085
    086    /**
    087     * Enrollment weight of a config if the given request is assigned. In order
    088     * to overcome rounding problems with last-like students ( e.g., 5 students
    089     * are projected to two configs of limit 2 -- each section can have up to 3
    090     * of these last-like students), the weight of the request with the highest
    091     * weight in the config is changed to a small nominal weight.
    092     *
    093     * @param assignment current assignment
    094     * @param config
    095     *            a config that is of concern
    096     * @param request
    097     *            a request of a student to be assigned containing the given
    098     *            section
    099     * @return section's new weight
    100     */
    101    public static double getEnrollmentWeight(Assignment<Request, Enrollment> assignment, Config config, Request request) {
    102        return config.getEnrollmentWeight(assignment, request) + request.getWeight() - Math.max(config.getMaxEnrollmentWeight(assignment), request.getWeight()) + sNominalWeight;
    103    }
    104
    105    /**
    106     * A given enrollment is conflicting, if the config's enrollment
    107     * (computed by {@link ConfigLimit#getEnrollmentWeight(Assignment, Config, Request)})
    108     * exceeds the limit. <br>
    109     * If the limit is breached, one or more existing enrollments are
    110     * (randomly) selected as conflicting until the overall weight is under the
    111     * limit.
    112     *
    113     * @param enrollment
    114     *            {@link Enrollment} that is being considered
    115     * @param conflicts
    116     *            all computed conflicting requests are added into this set
    117     */
    118    @Override
    119    public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<Enrollment> conflicts) {
    120        // check reservation can assign over the limit
    121        if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit())
    122            return;
    123
    124        // enrollment's config
    125        Config config = enrollment.getConfig();
    126
    127        // exclude free time requests
    128        if (config == null)
    129            return;
    130
    131        // exclude empty enrollmens
    132        if (enrollment.getSections() == null || enrollment.getSections().isEmpty())
    133            return;
    134
    135        // unlimited config
    136        if (config.getLimit() < 0)
    137            return;
    138
    139        // new enrollment weight
    140        double enrlWeight = getEnrollmentWeight(assignment, config, enrollment.getRequest());
    141
    142        // below limit -> ok
    143        if (enrlWeight <= config.getLimit())
    144            return;
    145
    146        // above limit -> compute adepts (current assignments that are not
    147        // yet conflicting)
    148        // exclude all conflicts as well
    149        ArrayList<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size());
    150        for (Enrollment e : config.getEnrollments(assignment)) {
    151            if (e.getRequest().equals(enrollment.getRequest()))
    152                continue;
    153            if (e.getReservation() != null && e.getReservation().canBatchAssignOverLimit())
    154                continue;
    155            if (conflicts.contains(e))
    156                enrlWeight -= e.getRequest().getWeight();
    157            else
    158                adepts.add(e);
    159        }
    160
    161        // while above limit -> pick an adept and make it conflicting
    162        while (enrlWeight > config.getLimit()) {
    163            if (adepts.isEmpty()) {
    164                // no adepts -> enrollment cannot be assigned
    165                conflicts.add(enrollment);
    166                return;
    167            }
    168
    169            // pick adept (prefer dummy students & students w/o reservation), decrease enrollment
    170            // weight, make conflict
    171            Enrollment conflict = new Adepts(iPreferDummyStudents, iPreferPriorityStudents, adepts, assignment).get();
    172            adepts.remove(conflict);
    173            enrlWeight -= conflict.getRequest().getWeight();
    174            conflicts.add(conflict);
    175        }
    176    }
    177
    178    /**
    179     * A given enrollment is conflicting, if the config's enrollment (computed by
    180     * {@link ConfigLimit#getEnrollmentWeight(Assignment, Config, Request)}) exceeds the
    181     * limit.
    182     *
    183     * @param enrollment
    184     *            {@link Enrollment} that is being considered
    185     * @return true, if the enrollment cannot be assigned without exceeding the limit
    186     */
    187    @Override
    188    public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
    189        // check reservation can assign over the limit
    190        if (enrollment.getReservation() != null && enrollment.getReservation().canBatchAssignOverLimit())
    191            return false;
    192
    193        // enrollment's config
    194        Config config = enrollment.getConfig();
    195
    196        // exclude free time requests
    197        if (config == null)
    198            return false;
    199
    200        // exclude empty enrollmens
    201        if (enrollment.getSections() == null || enrollment.getSections().isEmpty())
    202            return false;
    203
    204        // unlimited config
    205        if (config.getLimit() < 0)
    206            return false;
    207
    208        // new enrollment weight
    209        double enrlWeight = getEnrollmentWeight(assignment, config, enrollment.getRequest());
    210
    211        // above limit -> conflict
    212        return (enrlWeight > config.getLimit());
    213    }
    214
    215    @Override
    216    public String toString() {
    217        return "ConfigLimit";
    218    }
    219
    220    /**
    221     * Support class to pick an adept (prefer dummy students & students w/o reservation)
    222     */
    223    static class Adepts {
    224        private ArrayList<Enrollment> iEnrollments;
    225        private double iValue;
    226        private boolean iDummy;
    227        private StudentPriority iPriority;
    228        private RequestPriority iRequestPriority;
    229        private boolean iReservation;
    230        private boolean iConsiderDummy;
    231        private boolean iPriorityFirst;
    232
    233        public Adepts(boolean preferDummy, boolean priorityFirst) {
    234            iConsiderDummy = preferDummy;
    235            iPriorityFirst = priorityFirst;
    236            iEnrollments = new ArrayList<Enrollment>();
    237        }
    238
    239        public Adepts(boolean preferDummy, boolean priorityFirst, int size) {
    240            iConsiderDummy = preferDummy;
    241            iPriorityFirst = priorityFirst;
    242            iEnrollments = new ArrayList<Enrollment>(size);
    243        }
    244
    245        public Adepts(boolean preferDummy, boolean priorityFirst, Collection<Enrollment> adepts, Assignment<Request, Enrollment> assignment) {
    246            iConsiderDummy = preferDummy;
    247            iPriorityFirst = priorityFirst;
    248            iEnrollments = new ArrayList<Enrollment>(adepts.size());
    249            for (Enrollment adept: adepts)
    250                add(adept, assignment);
    251        }
    252
    253        public void add(Enrollment enrollment, Assignment<Request, Enrollment> assignment) {
    254            double value = enrollment.toDouble(assignment, false);
    255            boolean dummy = enrollment.getStudent().isDummy();
    256            StudentPriority priority = enrollment.getStudent().getPriority();
    257            boolean reservation = (enrollment.getReservation() != null);
    258            RequestPriority rp = enrollment.getRequest().getRequestPriority();
    259            if (iEnrollments.isEmpty()) { // no adepts yet
    260                iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    261                iEnrollments.add(enrollment);
    262                return;
    263            }
    264            if (iConsiderDummy && iDummy != dummy) { // different dummy
    265                if (!dummy) return; // ignore not-dummy students
    266                iEnrollments.clear();
    267                iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    268                iEnrollments.add(enrollment);
    269                return;
    270            }
    271            if (iPriorityFirst) {
    272                if (iPriority != priority) { // different priority
    273                    if (priority.ordinal() < iPriority.ordinal()) return; // ignore more priority students
    274                    iEnrollments.clear();
    275                    iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    276                    iEnrollments.add(enrollment);
    277                    return;
    278                }
    279                if (iRequestPriority != rp) { // different request priority
    280                    if (rp.ordinal() < iRequestPriority.ordinal()) return; // ignore more critical courses
    281                    iEnrollments.clear();
    282                    iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    283                    iEnrollments.add(enrollment);
    284                    return;
    285                }
    286            } else {
    287                if (iRequestPriority != rp) { // different request priority
    288                    if (rp.ordinal() < iRequestPriority.ordinal()) return; // ignore more critical courses
    289                    iEnrollments.clear();
    290                    iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    291                    iEnrollments.add(enrollment);
    292                    return;
    293                }
    294                if (iPriority != priority) { // different priority
    295                    if (priority.ordinal() < iPriority.ordinal()) return; // ignore more priority students
    296                    iEnrollments.clear();
    297                    iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    298                    iEnrollments.add(enrollment);
    299                    return;
    300                }
    301            }
    302            if (iReservation != reservation) { // different reservation
    303                if (reservation) return; // ignore students with reservation
    304                iEnrollments.clear();
    305                iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    306                iEnrollments.add(enrollment);
    307                return;
    308            }
    309            // prefer requests with higher value (lower priority)
    310            if (value > iValue) {
    311                iEnrollments.clear();
    312                iValue = value; iDummy = dummy; iPriority = priority; iRequestPriority = rp; iReservation = reservation;
    313                iEnrollments.add(enrollment);
    314            } else if (value == iValue) {
    315                iEnrollments.add(enrollment);
    316            }
    317        }
    318
    319        public Enrollment get() {
    320            if (iEnrollments.isEmpty()) return null;
    321            return ToolBox.random(iEnrollments);
    322        }
    323
    324        public boolean isEmpty() {
    325            return iEnrollments.isEmpty();
    326        }
    327    }
    328}