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