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