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