001    package net.sf.cpsolver.studentsct.constraint;
002    
003    import java.util.ArrayList;
004    import java.util.List;
005    import java.util.Set;
006    
007    import net.sf.cpsolver.ifs.model.GlobalConstraint;
008    import net.sf.cpsolver.ifs.util.DataProperties;
009    import net.sf.cpsolver.ifs.util.ToolBox;
010    import net.sf.cpsolver.studentsct.StudentSectioningModel;
011    import net.sf.cpsolver.studentsct.model.Config;
012    import net.sf.cpsolver.studentsct.model.Enrollment;
013    import net.sf.cpsolver.studentsct.model.Request;
014    import 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 Tomas Muller<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     */
061    public 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    }