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