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    
015    /**
016     * Configuration limit constraint. This global constraint ensures that a limit of each
017     * configuration is not exceeded. This means that the total sum of weights of course
018     * requests (see {@link Request#getWeight()}) enrolled into a configuration is below
019     * the configuration's limit (see {@link Config#getLimit()}).
020     * 
021     * <br>
022     * <br>
023     * Configurations with negative limit are considered unlimited, and therefore
024     * completely ignored by this constraint.
025     * 
026     * <br>
027     * <br>
028     * Parameters:
029     * <table border='1'>
030     * <tr>
031     * <th>Parameter</th>
032     * <th>Type</th>
033     * <th>Comment</th>
034     * </tr>
035     * <tr>
036     * <td>ConfigLimit.PreferDummyStudents</td>
037     * <td>{@link Boolean}</td>
038     * <td>If true, requests of dummy (last-like) students are preferred to be
039     * selected as conflicting.</td>
040     * </tr>
041     * </table>
042     * <br>
043     * <br>
044     * 
045     * @version StudentSct 1.2 (Student Sectioning)<br>
046     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
047     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
048     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
049     * <br>
050     *          This library is free software; you can redistribute it and/or modify
051     *          it under the terms of the GNU Lesser General Public License as
052     *          published by the Free Software Foundation; either version 3 of the
053     *          License, or (at your option) any later version. <br>
054     * <br>
055     *          This library is distributed in the hope that it will be useful, but
056     *          WITHOUT ANY WARRANTY; without even the implied warranty of
057     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
058     *          Lesser General Public License for more details. <br>
059     * <br>
060     *          You should have received a copy of the GNU Lesser General Public
061     *          License along with this library; if not see
062     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
063     */
064    public class ConfigLimit extends GlobalConstraint<Request, Enrollment> {
065        
066        private static double sNominalWeight = 0.00001;
067        private boolean iPreferDummyStudents = false;
068    
069        /**
070         * Constructor
071         * 
072         * @param cfg
073         *            solver configuration
074         */
075        public ConfigLimit(DataProperties cfg) {
076            super();
077            iPreferDummyStudents = cfg.getPropertyBoolean("ConfigLimit.PreferDummyStudents", false);
078        }
079    
080    
081        /**
082         * Enrollment weight of a config if the given request is assigned. In order
083         * to overcome rounding problems with last-like students ( e.g., 5 students
084         * are projected to two configs of limit 2 -- each section can have up to 3
085         * of these last-like students), the weight of the request with the highest
086         * weight in the config is changed to a small nominal weight.
087         * 
088         * @param config
089         *            a config that is of concern
090         * @param request
091         *            a request of a student to be assigned containing the given
092         *            section
093         * @return section's new weight
094         */
095        public static double getEnrollmentWeight(Config config, Request request) {
096            return config.getEnrollmentWeight(request) + request.getWeight()
097                    - Math.max(config.getMaxEnrollmentWeight(), request.getWeight()) + sNominalWeight;
098        }
099    
100        /**
101         * A given enrollment is conflicting, if the config's enrollment
102         * (computed by {@link ConfigLimit#getEnrollmentWeight(Config, Request)})
103         * exceeds the limit. <br>
104         * If the limit is breached, one or more existing enrollments are
105         * (randomly) selected as conflicting until the overall weight is under the
106         * limit.
107         * 
108         * @param enrollment
109         *            {@link Enrollment} that is being considered
110         * @param conflicts
111         *            all computed conflicting requests are added into this set
112         */
113        @Override
114        public void computeConflicts(Enrollment enrollment, Set<Enrollment> conflicts) {
115            // check reservation can assign over the limit
116            if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
117                enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
118                return;
119            
120            // enrollment's config
121            Config config = enrollment.getConfig();
122    
123            // exclude free time requests
124            if (config == null)
125                return;
126            
127    
128            // unlimited config
129            if (config.getLimit() < 0)
130                return;
131            
132            // new enrollment weight
133            double enrlWeight = getEnrollmentWeight(config, enrollment.getRequest());
134    
135            // below limit -> ok
136            if (enrlWeight <= config.getLimit())
137                return;
138    
139            // above limit -> compute adepts (current assignments that are not
140            // yet conflicting)
141            // exclude all conflicts as well
142            List<Enrollment> adepts = new ArrayList<Enrollment>(config.getEnrollments().size());
143            for (Enrollment e : config.getEnrollments()) {
144                if (e.getRequest().equals(enrollment.getRequest()))
145                    continue;
146                if (conflicts.contains(e))
147                    enrlWeight -= e.getRequest().getWeight();
148                else
149                    adepts.add(e);
150            }
151    
152            // while above limit -> pick an adept and make it conflicting
153            while (enrlWeight > config.getLimit()) {
154                if (adepts.isEmpty()) {
155                    // no adepts -> enrollment cannot be assigned
156                    conflicts.add(enrollment);
157                    return;
158                }
159                
160                // pick adept (prefer dummy students & students w/o reservation), decrease enrollment
161                // weight, make conflict
162                List<Enrollment> best = new ArrayList<Enrollment>();
163                boolean bestDummy = false;
164                double bestValue = 0;
165                boolean bestRes = true;
166                for (Enrollment adept: adepts) {
167                    boolean dummy = adept.getStudent().isDummy();
168                    double value = adept.toDouble(false);
169                    boolean res = (adept.getReservation() != null);
170                    
171                    if (iPreferDummyStudents && dummy != bestDummy) {
172                        if (dummy) {
173                            best.clear();
174                            best.add(adept);
175                            bestDummy = dummy;
176                            bestValue = value;
177                            bestRes = res;
178                        }
179                        continue;
180                    }
181                    
182                    if (bestRes != res) {
183                        if (!res) {
184                            best.clear();
185                            best.add(adept);
186                            bestDummy = dummy;
187                            bestValue = value;
188                            bestRes = res;
189                        }
190                        continue;
191                    }
192    
193                    if (best.isEmpty() || value > bestValue) {
194                        if (best.isEmpty()) best.clear();
195                        best.add(adept);
196                        bestDummy = dummy;
197                        bestValue = value;
198                        bestRes = res;
199                    } else if (bestValue == value) {
200                        best.add(adept);
201                    }
202                }
203                
204                Enrollment conflict = ToolBox.random(best);
205                adepts.remove(conflict);
206                enrlWeight -= conflict.getRequest().getWeight();
207                conflicts.add(conflict);
208            }
209        }
210    
211        /**
212         * A given enrollment is conflicting, if the config's enrollment (computed by
213         * {@link ConfigLimit#getEnrollmentWeight(Config, Request)}) exceeds the
214         * limit.
215         * 
216         * @param enrollment
217         *            {@link Enrollment} that is being considered
218         * @return true, if the enrollment cannot be assigned without exceeding the limit
219         */
220        @Override
221        public boolean inConflict(Enrollment enrollment) {
222            // check reservation can assign over the limit
223            if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
224                enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
225                return false;
226    
227            // enrollment's config
228            Config config = enrollment.getConfig();
229    
230            // exclude free time requests
231            if (config == null)
232                return false;
233    
234            // unlimited config
235            if (config.getLimit() < 0)
236                return false;
237    
238    
239            // new enrollment weight
240            double enrlWeight = getEnrollmentWeight(config, enrollment.getRequest());
241            
242            // above limit -> conflict
243            return (enrlWeight > config.getLimit());
244        }
245        
246        @Override
247        public String toString() {
248            return "ConfigLimit";
249        }
250    
251    }