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        // exclude empty enrollmens
128        if (enrollment.getSections() == null || enrollment.getSections().isEmpty())
129            return;
130        
131        // no reservations
132        if (!config.getOffering().hasReservations())
133            return;
134        
135        // enrollment's reservation
136        Reservation reservation = enrollment.getReservation();
137        
138        // check space in the reservation reservation
139        if (reservation != null) {
140            // check reservation too
141            double reserved = reservation.getReservedAvailableSpace(assignment, enrollment.getRequest());
142            
143            if (reservation.getLimit() >= 0 && reserved < enrollment.getRequest().getWeight()) {
144                // reservation is not unlimited and there is not enough space in it
145                
146                // try to free some space in the reservation
147                List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size());
148                for (Enrollment e : config.getEnrollments(assignment)) {
149                    if (e.getRequest().equals(enrollment.getRequest()))
150                        continue;
151                    if (!reservation.equals(e.getReservation()))
152                        continue;
153                    if (conflicts.contains(e))
154                        reserved += e.getRequest().getWeight();
155                    else
156                        adepts.add(e);
157                }
158                
159                while (reserved < enrollment.getRequest().getWeight()) {
160                    if (adepts.isEmpty()) {
161                        // no adepts -> enrollment cannot be assigned
162                        conflicts.add(enrollment);
163                        return;
164                    }
165                    
166                    // pick adept (prefer dummy students), decrease unreserved space,
167                    // make conflict
168                    List<Enrollment> best = new ArrayList<Enrollment>();
169                    boolean bestDummy = false;
170                    double bestValue = 0;
171                    for (Enrollment adept: adepts) {
172                        boolean dummy = adept.getStudent().isDummy();
173                        double value = adept.toDouble(assignment, false);
174                        
175                        if (iPreferDummyStudents && dummy != bestDummy) {
176                            if (dummy) {
177                                best.clear();
178                                best.add(adept);
179                                bestDummy = dummy;
180                                bestValue = value;
181                            }
182                            continue;
183                        }
184                        
185                        if (best.isEmpty() || value > bestValue) {
186                            if (best.isEmpty()) best.clear();
187                            best.add(adept);
188                            bestDummy = dummy;
189                            bestValue = value;
190                        } else if (bestValue == value) {
191                            best.add(adept);
192                        }
193                    }
194                    
195                    Enrollment conflict = ToolBox.random(best);
196                    adepts.remove(conflict);
197                    reserved += conflict.getRequest().getWeight();
198                    conflicts.add(conflict);
199                }
200            }
201
202            // if not configuration reservation -> check configuration unavailable space
203            if (!hasConfigReservation(enrollment)) {
204                // check reservation can assign over the limit
205                if (reservation.canBatchAssignOverLimit())
206                    return;
207
208                // check the total first (basically meaning that there will never be enough space in 
209                // the section for an enrollment w/o configuration reservation
210                if (config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) {
211                    conflicts.add(enrollment);
212                    return;
213                }
214
215                double unreserved = getUnreservedSpace(assignment, config, enrollment.getRequest(), true);
216
217                if (unreserved < 0.0) {
218                    // no unreserved space available -> cannot be assigned
219                    // try to unassign some other enrollments that also do not have config reservation
220                    
221                    List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size());
222                    for (Enrollment e : config.getEnrollments(assignment)) {
223                        if (e.getRequest().equals(enrollment.getRequest()))
224                            continue;
225                        if (hasConfigReservation(e))
226                            continue;
227                        if (conflicts.contains(e))
228                            unreserved += e.getRequest().getWeight();
229                        else
230                            adepts.add(e);
231                    }
232                    
233                    while (unreserved < 0.0) {
234                        if (adepts.isEmpty()) {
235                            // no adepts -> enrollment cannot be assigned
236                            conflicts.add(enrollment);
237                            return;
238                        }
239                        
240                        // pick adept (prefer dummy students), decrease unreserved space,
241                        // make conflict
242                        List<Enrollment> best = new ArrayList<Enrollment>();
243                        boolean bestDummy = false;
244                        double bestValue = 0;
245                        for (Enrollment adept: adepts) {
246                            boolean dummy = adept.getStudent().isDummy();
247                            double value = adept.toDouble(assignment, false);
248                            
249                            if (iPreferDummyStudents && dummy != bestDummy) {
250                                if (dummy) {
251                                    best.clear();
252                                    best.add(adept);
253                                    bestDummy = dummy;
254                                    bestValue = value;
255                                }
256                                continue;
257                            }
258                            
259                            if (best.isEmpty() || value > bestValue) {
260                                if (best.isEmpty()) best.clear();
261                                best.add(adept);
262                                bestDummy = dummy;
263                                bestValue = value;
264                            } else if (bestValue == value) {
265                                best.add(adept);
266                            }
267                        }
268                        
269                        Enrollment conflict = ToolBox.random(best);
270                        adepts.remove(conflict);
271                        unreserved += conflict.getRequest().getWeight();
272                        conflicts.add(conflict);
273                    }
274                }
275            }
276        } else { // no reservation at all
277            // check the total first (basically meaning that there will never be enough space in
278            // the section for an enrollment w/o reservation
279            if (config.getOffering().getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 
280                config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight()) {
281                conflicts.add(enrollment);
282                return;
283            }
284                
285            // check configuration unavailable space too
286            double unreserved = getUnreservedSpace(assignment, config, enrollment.getRequest(), false);
287                
288            if (unreserved < 0.0) {
289                // no unreserved space available -> cannot be assigned
290                // try to unassign some other enrollments that also do not have reservation
291                
292                List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments(assignment).size());
293                for (Enrollment e : config.getEnrollments(assignment)) {
294                    if (e.getRequest().equals(enrollment.getRequest()))
295                        continue;
296                    if (e.getReservation() != null)
297                        continue;
298                    if (conflicts.contains(e))
299                        unreserved += e.getRequest().getWeight();
300                    else
301                        adepts.add(e);
302                }
303                
304                while (unreserved < 0.0) {
305                    if (adepts.isEmpty()) {
306                        // no adepts -> enrollment cannot be assigned
307                        conflicts.add(enrollment);
308                        return;
309                    }
310                    
311                    // pick adept (prefer dummy students), decrease unreserved space,
312                    // make conflict
313                    List<Enrollment> best = new ArrayList<Enrollment>();
314                    boolean bestDummy = false;
315                    double bestValue = 0;
316                    for (Enrollment adept: adepts) {
317                        boolean dummy = adept.getStudent().isDummy();
318                        double value = adept.toDouble(assignment, false);
319                        
320                        if (iPreferDummyStudents && dummy != bestDummy) {
321                            if (dummy) {
322                                best.clear();
323                                best.add(adept);
324                                bestDummy = dummy;
325                                bestValue = value;
326                            }
327                            continue;
328                        }
329                        
330                        if (best.isEmpty() || value > bestValue) {
331                            if (best.isEmpty()) best.clear();
332                            best.add(adept);
333                            bestDummy = dummy;
334                            bestValue = value;
335                        } else if (bestValue == value) {
336                            best.add(adept);
337                        }
338                    }
339                    
340                    Enrollment conflict = ToolBox.random(best);
341                    adepts.remove(conflict);
342                    unreserved += conflict.getRequest().getWeight();
343                    conflicts.add(conflict);
344                }
345            }
346        }
347    }
348
349    /**
350     * True if the enrollment has reservation for this configuration.
351     **/
352    private boolean hasConfigReservation(Enrollment enrollment) {
353        if (enrollment.getConfig() == null) return false;
354        Reservation reservation = enrollment.getReservation();
355        if (reservation == null) return false;
356        return reservation.getConfigs().contains(enrollment.getConfig());
357    }
358
359    
360    /**
361     * A given enrollment is conflicting, if the config's enrollment (computed by
362     * {@link ConfigLimit#getEnrollmentWeight(Assignment, Config, Request)}) exceeds the
363     * limit.
364     * 
365     * @param enrollment
366     *            {@link Enrollment} that is being considered
367     * @return true, if the enrollment cannot be assigned without exceeding the limit
368     */
369    @Override
370    public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
371        // enrollment's config
372        Config config = enrollment.getConfig();
373
374        // exclude free time requests
375        if (config == null)
376            return false;
377        
378        // exclude empty enrollmens
379        if (enrollment.getSections() == null || enrollment.getSections().isEmpty())
380            return false;
381        
382        // enrollment's reservation
383        Reservation reservation = enrollment.getReservation();
384        
385        // check reservation
386        if (reservation != null) {
387            // unlimited reservation
388            if (reservation.getLimit() < 0)
389                return false;
390            
391            // check remaning space
392            if (reservation.getReservedAvailableSpace(assignment, enrollment.getRequest()) < enrollment.getRequest().getWeight())
393                return true;
394            
395            // check reservation can assign over the limit
396            if (reservation.canBatchAssignOverLimit())
397                return false;
398            
399            // if not configuration reservation, check configuration unreserved space too
400            return (!hasConfigReservation(enrollment) &&
401                    getUnreservedSpace(assignment, config, enrollment.getRequest(), true) < 0.0);
402        } else {
403            // check unreserved space;
404            return config.getOffering().getTotalUnreservedSpace() < enrollment.getRequest().getWeight() || 
405                   config.getTotalUnreservedSpace() < enrollment.getRequest().getWeight() ||
406                   getUnreservedSpace(assignment, config, enrollment.getRequest(), false) < 0.0;
407        }
408    }
409    
410    @Override
411    public String toString() {
412        return "ReservationLimit";
413    }
414
415}