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