001package net.sf.cpsolver.studentsct.constraint;
002
003import java.util.ArrayList;
004import java.util.List;
005import java.util.Set;
006
007import net.sf.cpsolver.ifs.model.GlobalConstraint;
008import net.sf.cpsolver.ifs.util.DataProperties;
009import net.sf.cpsolver.ifs.util.ToolBox;
010import net.sf.cpsolver.studentsct.StudentSectioningModel;
011import net.sf.cpsolver.studentsct.model.Config;
012import net.sf.cpsolver.studentsct.model.Enrollment;
013import 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 Tomáš Müller<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 */
064public 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}