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