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