001package org.cpsolver.studentsct.weights;
002
003import java.text.DecimalFormat;
004import java.util.ArrayList;
005import java.util.BitSet;
006import java.util.HashSet;
007import java.util.Set;
008
009import org.cpsolver.coursett.model.Placement;
010import org.cpsolver.coursett.model.RoomLocation;
011import org.cpsolver.coursett.model.TimeLocation;
012import org.cpsolver.ifs.assignment.Assignment;
013import org.cpsolver.ifs.assignment.DefaultSingleAssignment;
014import org.cpsolver.ifs.solution.Solution;
015import org.cpsolver.ifs.util.DataProperties;
016import org.cpsolver.ifs.util.ToolBox;
017import org.cpsolver.studentsct.StudentSectioningModel;
018import org.cpsolver.studentsct.extension.DistanceConflict;
019import org.cpsolver.studentsct.extension.StudentQuality;
020import org.cpsolver.studentsct.extension.StudentQuality.Conflict;
021import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
022import org.cpsolver.studentsct.model.Choice;
023import org.cpsolver.studentsct.model.Config;
024import org.cpsolver.studentsct.model.Course;
025import org.cpsolver.studentsct.model.CourseRequest;
026import org.cpsolver.studentsct.model.Enrollment;
027import org.cpsolver.studentsct.model.Instructor;
028import org.cpsolver.studentsct.model.Offering;
029import org.cpsolver.studentsct.model.Request;
030import org.cpsolver.studentsct.model.RequestGroup;
031import org.cpsolver.studentsct.model.SctAssignment;
032import org.cpsolver.studentsct.model.Section;
033import org.cpsolver.studentsct.model.Student;
034import org.cpsolver.studentsct.model.Subpart;
035
036
037/**
038 * New weighting model. It tries to obey the following principles:
039 * <ul>
040 *      <li> Total student weight is between zero and one (one means student got the best schedule)
041 *      <li> Weight of the given priority course is higher than sum of the remaining weights the student can get
042 *      <li> First alternative is better than the following course
043 *      <li> Second alternative is better than the second following course
044 *      <li> Distance conflicts are considered secondary (priorities should be maximized first)
045 *      <li> If alternative sections are otherwise equal, use the better balanced one
046 * </ul>
047 * 
048 * @version StudentSct 1.3 (Student Sectioning)<br>
049 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
050 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
051 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
052 * <br>
053 *          This library is free software; you can redistribute it and/or modify
054 *          it under the terms of the GNU Lesser General Public License as
055 *          published by the Free Software Foundation; either version 3 of the
056 *          License, or (at your option) any later version. <br>
057 * <br>
058 *          This library is distributed in the hope that it will be useful, but
059 *          WITHOUT ANY WARRANTY; without even the implied warranty of
060 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
061 *          Lesser General Public License for more details. <br>
062 * <br>
063 *          You should have received a copy of the GNU Lesser General Public
064 *          License along with this library; if not see
065 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
066 */
067
068public class PriorityStudentWeights implements StudentWeights {
069    protected double iPriorityFactor = 0.5010;
070    protected double iFirstAlternativeFactor = 0.5010;
071    protected double iSecondAlternativeFactor = 0.2510;
072    protected double iDistanceConflict = 0.0100;
073    protected double iShortDistanceConflict = 0.1000;
074    protected double iTimeOverlapFactor = 0.5000;
075    protected double iTimeOverlapMaxLimit = 0.5000;
076    protected boolean iLeftoverSpread = false;
077    protected double iBalancingFactor = 0.0050;
078    protected double iNoTimeFactor = 0.0100;
079    protected double iOnlineFactor = 0.0100;
080    protected double iReservationNotFollowedFactor = 0.1000;
081    protected double iAlternativeRequestFactor = 0.1260;
082    protected double iProjectedStudentWeight = 0.0100;
083    protected boolean iMPP = false;
084    protected double iPerturbationFactor = 0.100;
085    protected double iSelectionFactor = 0.100;
086    protected double iSameChoiceWeight = 0.900;
087    protected double iSameTimeWeight = 0.700;
088    protected double iSameConfigWeight = 0.500;
089    protected double iGroupFactor = 0.100;
090    protected double iGroupBestRatio = 0.95;
091    protected double iGroupFillRatio = 0.05;
092    protected boolean iAdditiveWeights = false;
093    protected boolean iMaximizeAssignment = false;
094    protected boolean iPreciseComparison = false;
095    protected double[] iQalityWeights;
096    protected boolean iImprovedBound = true;
097    protected double iCriticalBoost = 1.0;
098    protected double iPriortyBoost = 1.0;
099    
100    public PriorityStudentWeights(DataProperties config) {
101        iPriorityFactor = config.getPropertyDouble("StudentWeights.Priority", iPriorityFactor);
102        iFirstAlternativeFactor = config.getPropertyDouble("StudentWeights.FirstAlternative", iFirstAlternativeFactor);
103        iSecondAlternativeFactor = config.getPropertyDouble("StudentWeights.SecondAlternative", iSecondAlternativeFactor);
104        iDistanceConflict = config.getPropertyDouble("StudentWeights.DistanceConflict", iDistanceConflict);
105        iShortDistanceConflict = config.getPropertyDouble("StudentWeights.ShortDistanceConflict", iShortDistanceConflict);
106        iTimeOverlapFactor = config.getPropertyDouble("StudentWeights.TimeOverlapFactor", iTimeOverlapFactor);
107        iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit);
108        iLeftoverSpread = config.getPropertyBoolean("StudentWeights.LeftoverSpread", iLeftoverSpread);
109        iBalancingFactor = config.getPropertyDouble("StudentWeights.BalancingFactor", iBalancingFactor);
110        iAlternativeRequestFactor = config.getPropertyDouble("StudentWeights.AlternativeRequestFactor", iAlternativeRequestFactor);
111        iProjectedStudentWeight = config.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight);
112        iMPP = config.getPropertyBoolean("General.MPP", false);
113        iPerturbationFactor = config.getPropertyDouble("StudentWeights.Perturbation", iPerturbationFactor);
114        iSelectionFactor = config.getPropertyDouble("StudentWeights.Selection", iSelectionFactor);
115        iSameChoiceWeight = config.getPropertyDouble("StudentWeights.SameChoice", iSameChoiceWeight);
116        iSameTimeWeight = config.getPropertyDouble("StudentWeights.SameTime", iSameTimeWeight);
117        iSameConfigWeight = config.getPropertyDouble("StudentWeights.SameConfig", iSameConfigWeight);
118        iGroupFactor = config.getPropertyDouble("StudentWeights.SameGroup", iGroupFactor);
119        iGroupBestRatio = config.getPropertyDouble("StudentWeights.GroupBestRatio", iGroupBestRatio);
120        iGroupFillRatio = config.getPropertyDouble("StudentWeights.GroupFillRatio", iGroupFillRatio);
121        iNoTimeFactor = config.getPropertyDouble("StudentWeights.NoTimeFactor", iNoTimeFactor);
122        iOnlineFactor = config.getPropertyDouble("StudentWeights.OnlineFactor", iOnlineFactor);
123        iReservationNotFollowedFactor = config.getPropertyDouble("StudentWeights.ReservationNotFollowedFactor", iReservationNotFollowedFactor);
124        iAdditiveWeights = config.getPropertyBoolean("StudentWeights.AdditiveWeights", iAdditiveWeights);
125        iMaximizeAssignment = config.getPropertyBoolean("StudentWeights.MaximizeAssignment", iMaximizeAssignment);
126        iPreciseComparison = config.getPropertyBoolean("StudentWeights.PreciseComparison", iPreciseComparison);
127        iQalityWeights = new double[StudentQuality.Type.values().length];
128        for (StudentQuality.Type type: StudentQuality.Type.values()) {
129            iQalityWeights[type.ordinal()] = config.getPropertyDouble(type.getWeightName(), type.getWeightDefault());
130        }
131        iImprovedBound = config.getPropertyBoolean("StudentWeights.ImprovedBound", iImprovedBound);
132        iPriortyBoost = config.getPropertyDouble("StudentWeights.PriortyBoost", 1.0);
133        iCriticalBoost = config.getPropertyDouble("StudentWeights.CriticalBoost", 1.0);
134    }
135        
136    public double getWeight(Request request) {
137        if (request.getStudent().isDummy() && iProjectedStudentWeight >= 0.0) {
138            double weight = iProjectedStudentWeight;
139            if (request.isAlternative())
140                weight *= iAlternativeRequestFactor;
141            return weight;
142        }
143        double total = 1000000.0;
144        int nrReq = request.getStudent().nrRequests();
145        double remain = (iLeftoverSpread ? Math.floor(1000000.0 * Math.pow(iPriorityFactor, nrReq) / nrReq) : 0.0);
146        for (int idx = 0; idx < request.getStudent().getRequests().size(); idx++) {
147            Request r = request.getStudent().getRequests().get(idx);
148            boolean last = (idx + 1 == request.getStudent().getRequests().size());
149            boolean lastNotAlt = !r.isAlternative() && (last || request.getStudent().getRequests().get(1 + idx).isAlternative());
150            double w = Math.ceil(iPriorityFactor * total) + remain;
151            if (!iLeftoverSpread && lastNotAlt) {
152                w = total;
153            } else {
154                total -= w;
155            }
156            if (r.equals(request)) {
157                return w / 1000000.0;
158            }
159        }
160        return 0.0;
161    }
162
163    public double getBoostedWeight(Request request) {
164        double weight = getWeight(request);
165        if (iPriortyBoost != 1.0) {
166            Double boost = request.getStudent().getPriority().getBoost();
167            if (boost != null)
168                weight *= boost * iPriortyBoost;
169        }
170        if (iCriticalBoost != 1.0) {
171            Double boost = request.getRequestPriority().getBoost();
172            if (boost != null)
173                weight *= boost * iCriticalBoost;
174        }
175        return weight;
176    }
177    
178    public double getCachedWeight(Request request) {
179        double[] cache = (double[])request.getExtra();
180        if (cache == null) {
181            double base = getBoostedWeight(request); 
182            cache = new double[]{base, computeBound(base, request)};
183            request.setExtra(cache);
184        }
185        return cache[0];
186    }
187    
188    /**
189     * Return how much the given enrollment is different from the initial enrollment
190     * @param enrollment given enrollment
191     * @return 0.0 when all the sections are the same, 1.0 when all the section are different (including different times)
192     */
193    protected double getDifference(Enrollment enrollment) {
194        if (enrollment.getStudent().isDummy() || !enrollment.isCourseRequest()) return 1.0;
195        Enrollment other = enrollment.getRequest().getInitialAssignment();
196        if (other != null) {
197            double similarSections = 0.0;
198            if (enrollment.getConfig().equals(other.getConfig())) {
199                // same configurations -- compare sections of matching subpart
200                for (Section section: enrollment.getSections()) {
201                    for (Section initial: other.getSections()) {
202                        if (section.getSubpart().equals(initial.getSubpart())) {
203                            if (section.equals(initial)) {
204                                similarSections += 1.0;
205                            } else if (section.sameChoice(initial)) {
206                                similarSections += iSameChoiceWeight;
207                            } else if (section.sameTime(initial)) {
208                                similarSections += iSameTimeWeight;
209                            }
210                            break;
211                        }
212                    }
213                }
214            } else {
215                // different configurations -- compare sections of matching itype
216                for (Section section: enrollment.getSections()) {
217                    for (Section initial: other.getSections()) {
218                        if (section.sameChoice(initial)) {
219                            similarSections += iSameChoiceWeight;
220                            break;
221                        } else if (section.sameInstructionalType(initial) && section.sameTime(initial)) {
222                            similarSections += iSameTimeWeight;
223                            break;
224                        }
225                    }
226                }
227            }
228            return 1.0 - similarSections / enrollment.getAssignments().size();
229        }
230        return 1.0;
231    }
232    
233    /**
234     * Return how much the given enrollment is different from the selection (if any)
235     * @param enrollment given enrollment
236     * @return 0.0 when all the sections are the same, 1.0 when all the section are different (including different times)
237     */
238    public double getSelection(Enrollment enrollment) {
239        if (enrollment.getStudent().isDummy()) return 1.0;
240        if (enrollment.isCourseRequest()) {
241            CourseRequest cr = (CourseRequest)enrollment.getRequest();
242            if (!cr.getSelectedChoices().isEmpty()) {
243                double similarSections = 0.0;
244                for (Section section: enrollment.getSections()) {
245                    double bestChoice = 0.0;
246                    for (Choice ch: cr.getSelectedChoices()) {
247                        if (bestChoice < 1.0 && ch.sameSection(section)) {
248                            bestChoice = 1.0;
249                        } else if (bestChoice < iSameChoiceWeight && ch.sameChoice(section)) {
250                            bestChoice = iSameChoiceWeight;
251                        } else if (bestChoice < iSameTimeWeight && ch.sameOffering(section) && ch.sameInstructionalType(section) && ch.sameTime(section)) {
252                            bestChoice = iSameTimeWeight;
253                        } else if (bestChoice < iSameConfigWeight && ch.sameConfiguration(section)) {
254                            bestChoice = iSameConfigWeight;
255                        }
256                    }
257                    similarSections += bestChoice;
258                }
259                return 1.0 - similarSections / enrollment.getAssignments().size();
260            } else {
261                return 1.0;
262            }
263        } else {
264            return 1.0;
265        }
266    }
267    
268
269    @Override
270    public double getBound(Request request) {
271        double[] cache = (double[])request.getExtra();
272        if (cache == null) {
273            double base = getBoostedWeight(request); 
274            cache = new double[]{base, computeBound(base, request)};
275            request.setExtra(cache);
276        }
277        return cache[1];
278    }
279    
280    protected double computeBound(double base, Request request) {
281        if (!iImprovedBound) return base;
282        if (iAdditiveWeights) {
283            double weight = 0.0;
284            if (request instanceof CourseRequest) {
285                CourseRequest cr = (CourseRequest)request;
286                if (iNoTimeFactor != 0.0 && !cr.getCourses().isEmpty()) {
287                    weight += iNoTimeFactor * cr.getCourses().get(0).getArrHrsBound();
288                }
289                if (iOnlineFactor != 0.0 && !cr.getCourses().isEmpty()) {
290                    weight += iOnlineFactor * cr.getCourses().get(0).getOnlineBound();
291                }
292                if (iMPP && cr.getInitialAssignment() == null) {
293                    weight += iPerturbationFactor;
294                }
295                if (iSelectionFactor != 0.0 && cr.getSelectedChoices().isEmpty()) {
296                    weight += iSelectionFactor;
297                }
298            }
299            return round(base * (1.0 - weight));
300        } else {
301            double weight = base;
302            if (request instanceof CourseRequest) {
303                CourseRequest cr = (CourseRequest)request;
304                if (iNoTimeFactor != 0.0 && !cr.getCourses().isEmpty()) {
305                    weight *= (1.0 - iNoTimeFactor * cr.getCourses().get(0).getArrHrsBound());
306                }
307                if (iOnlineFactor != 0.0 && !cr.getCourses().isEmpty()) {
308                    weight *= (1.0 - iOnlineFactor * cr.getCourses().get(0).getOnlineBound());
309                }
310                if (iMPP && cr.getInitialAssignment() == null) {
311                    weight *= (1.0 - iPerturbationFactor);
312                }
313                if (iSelectionFactor != 0.0 && cr.getSelectedChoices().isEmpty()) {
314                    weight *= (1.0 - iSelectionFactor);
315                }
316            }
317            return round(weight);
318        }
319    }
320    
321    protected double round(double value) {
322        return Math.ceil(1000000.0 * value) / 1000000.0;
323    }
324    
325    protected double getBaseWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
326        double weight = getCachedWeight(enrollment.getRequest());
327        switch (enrollment.getTruePriority()) {
328            case 0: break;
329            case 1: weight *= iFirstAlternativeFactor; break;
330            case 2: weight *= iSecondAlternativeFactor; break;
331            default:
332                weight *= Math.pow(iFirstAlternativeFactor, enrollment.getTruePriority());
333        }
334        return weight;
335    }
336    
337    @Override
338    public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
339        if (iAdditiveWeights)
340            return getWeightAdditive(assignment, enrollment);
341        else
342            return getWeightMultiplicative(assignment, enrollment);
343    }
344    
345    public double getWeightMultiplicative(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
346        double weight = getBaseWeight(assignment, enrollment);
347        if (enrollment.isCourseRequest() && iNoTimeFactor != 0.0) {
348            int noTimeSections = 0, total = 0;
349            for (Section section: enrollment.getSections()) {
350                if (section.getTime() == null) noTimeSections ++;
351                total ++;
352            }
353            if (noTimeSections > 0)
354                weight *= (1.0 - iNoTimeFactor * noTimeSections / total);
355        }
356        if (enrollment.isCourseRequest() && iOnlineFactor != 0.0) {
357            int onlineSections = 0, total = 0;
358            for (Section section: enrollment.getSections()) {
359                if (section.isOnline()) onlineSections ++;
360                total ++;
361            }
362            if (onlineSections > 0)
363                weight *= (1.0 - iOnlineFactor * onlineSections / total);
364        }
365        if (enrollment.getTruePriority() < enrollment.getPriority()) {
366            weight *= (1.0 - iReservationNotFollowedFactor);
367        }
368        if (enrollment.isCourseRequest() && iBalancingFactor != 0.0) {
369            double configUsed = enrollment.getConfig().getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight();
370            double disbalanced = 0;
371            double total = 0;
372            for (Section section: enrollment.getSections()) {
373                Subpart subpart = section.getSubpart();
374                if (subpart.getSections().size() <= 1) continue;
375                double used = section.getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight();
376                // sections have limits -> desired size is section limit x (total enrollment / total limit)
377                // unlimited sections -> desired size is total enrollment / number of sections
378                double desired = (subpart.getLimit() > 0
379                        ? section.getLimit() * (configUsed / subpart.getLimit())
380                        : configUsed / subpart.getSections().size());
381                if (used > desired)
382                    disbalanced += Math.min(enrollment.getRequest().getWeight(), used - desired) / enrollment.getRequest().getWeight();
383                else
384                    disbalanced -= Math.min(enrollment.getRequest().getWeight(), desired - used) / enrollment.getRequest().getWeight();
385                total ++;
386            }
387            if (disbalanced > 0)
388                weight *= (1.0 - disbalanced / total * iBalancingFactor);
389        }
390        if (iMPP) {
391            double difference = getDifference(enrollment);
392            if (difference > 0.0)
393                weight *= (1.0 - difference * iPerturbationFactor);
394        }
395        if (iSelectionFactor != 0.0) {
396            double selection = getSelection(enrollment);
397            if (selection > 0.0)
398                weight *= (1.0 - selection * iSelectionFactor);
399        }
400        if (enrollment.isCourseRequest() && iGroupFactor != 0.0) {
401            double sameGroup = 0.0; int groupCount = 0;
402            for (RequestGroup g: ((CourseRequest)enrollment.getRequest()).getRequestGroups()) {
403                if (g.getCourse().equals(enrollment.getCourse())) {
404                    sameGroup += g.getEnrollmentSpread(assignment, enrollment, iGroupBestRatio, iGroupFillRatio);
405                    groupCount ++;
406                }
407            }
408            if (groupCount > 0) {
409                double difference = 1.0 - sameGroup / groupCount;
410                weight *= (1.0 - difference * iGroupFactor);
411            }
412        }
413        return round(weight);
414    }
415    
416    public double getWeightAdditive(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
417        double base = getBaseWeight(assignment, enrollment);
418        double weight = 0.0;
419        if (enrollment.isCourseRequest() && iNoTimeFactor != 0.0) {
420            int noTimeSections = 0, total = 0;
421            for (Section section: enrollment.getSections()) {
422                if (section.getTime() == null) noTimeSections ++;
423                total ++;
424            }
425            if (noTimeSections > 0)
426                weight += iNoTimeFactor * noTimeSections / total;
427        }
428        if (enrollment.isCourseRequest() && iOnlineFactor != 0.0) {
429            int onlineSections = 0, total = 0;
430            for (Section section: enrollment.getSections()) {
431                if (section.isOnline()) onlineSections ++;
432                total ++;
433            }
434            if (onlineSections > 0)
435                weight += iOnlineFactor * onlineSections / total;
436        }
437        if (enrollment.getTruePriority() < enrollment.getPriority()) {
438            weight += iReservationNotFollowedFactor;
439        }
440        if (enrollment.isCourseRequest() && iBalancingFactor != 0.0) {
441            double configUsed = enrollment.getConfig().getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight();
442            double disbalanced = 0;
443            double total = 0;
444            for (Section section: enrollment.getSections()) {
445                Subpart subpart = section.getSubpart();
446                if (subpart.getSections().size() <= 1) continue;
447                double used = section.getEnrollmentTotalWeight(assignment, enrollment.getRequest()) + enrollment.getRequest().getWeight();
448                // sections have limits -> desired size is section limit x (total enrollment / total limit)
449                // unlimited sections -> desired size is total enrollment / number of sections
450                double desired = (subpart.getLimit() > 0
451                        ? section.getLimit() * (configUsed / subpart.getLimit())
452                        : configUsed / subpart.getSections().size());
453                if (used > desired)
454                    disbalanced += Math.min(enrollment.getRequest().getWeight(), used - desired) / enrollment.getRequest().getWeight();
455                else
456                    disbalanced -= Math.min(enrollment.getRequest().getWeight(), desired - used) / enrollment.getRequest().getWeight();
457                total ++;
458            }
459            if (disbalanced > 0)
460                weight += disbalanced / total * iBalancingFactor;
461        }
462        if (iMPP) {
463            double difference = getDifference(enrollment);
464            if (difference > 0.0)
465                weight += difference * iPerturbationFactor;
466        }
467        if (iSelectionFactor != 0.0) {
468            double selection = getSelection(enrollment);
469            if (selection > 0.0)
470                weight += selection * iSelectionFactor;
471        }
472        if (enrollment.isCourseRequest() && iGroupFactor != 0.0) {
473            double sameGroup = 0.0; int groupCount = 0;
474            for (RequestGroup g: ((CourseRequest)enrollment.getRequest()).getRequestGroups()) {
475                if (g.getCourse().equals(enrollment.getCourse())) {
476                    sameGroup += g.getEnrollmentSpread(assignment, enrollment, iGroupBestRatio, iGroupFillRatio);
477                    groupCount ++;
478                }
479            }
480            if (groupCount > 0) {
481                double difference = 1.0 - sameGroup / groupCount;
482                weight += difference * iGroupFactor;
483            }
484        }
485        return round(base * (1.0 - weight));
486    }
487    
488    @Override
489    public double getDistanceConflictWeight(Assignment<Request, Enrollment> assignment, DistanceConflict.Conflict c) {
490        if (iAdditiveWeights) {
491            if (c.getR1().getPriority() < c.getR2().getPriority()) {
492                return round(getBaseWeight(assignment, c.getE2()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict));
493            } else {
494                return round(getBaseWeight(assignment, c.getE1()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict));
495            }
496        } else {
497            if (c.getR1().getPriority() < c.getR2().getPriority()) {
498                return round(getWeightMultiplicative(assignment, c.getE2()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict));
499            } else {
500                return round(getWeightMultiplicative(assignment, c.getE1()) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict));
501            }
502        }
503    }
504    
505    @Override
506    public double getTimeOverlapConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment e, TimeOverlapsCounter.Conflict c) {
507        if (e == null || e.getRequest() == null) return 0.0;
508        double toc = Math.min(iTimeOverlapFactor * c.getShare() / e.getNrSlots(), iTimeOverlapMaxLimit);
509        if (iAdditiveWeights) {
510            return round(getBaseWeight(assignment, e) * toc);
511        } else {
512            return round(getWeightMultiplicative(assignment, e) * toc);
513        }
514    }
515    
516    @Override
517    public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
518        if (iAdditiveWeights) {
519            double base = getBaseWeight(assignment, enrollment);
520            double dc = 0.0;
521            if (distanceConflicts != null) {
522                for (DistanceConflict.Conflict c: distanceConflicts) {
523                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
524                    if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
525                        dc += base * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict);
526                    else
527                        dc += getBaseWeight(assignment, other) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict);
528                }
529            }
530            double toc = 0.0;
531            if (timeOverlappingConflicts != null) {
532                for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
533                    toc += base * Math.min(iTimeOverlapFactor * c.getShare() / enrollment.getNrSlots(), iTimeOverlapMaxLimit);
534                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
535                    if (other.getRequest() != null)
536                        toc += getBaseWeight(assignment, other) * Math.min(iTimeOverlapFactor * c.getShare() / other.getNrSlots(), iTimeOverlapMaxLimit);
537                }
538            }
539            return round(getWeight(assignment, enrollment) - dc - toc);
540        } else {
541            double base = getWeightMultiplicative(assignment, enrollment);
542            double dc = 0.0;
543            if (distanceConflicts != null) {
544                for (DistanceConflict.Conflict c: distanceConflicts) {
545                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
546                    if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
547                        dc += base * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict);
548                    else
549                        dc += getWeightMultiplicative(assignment, other) * (c.getStudent().isNeedShortDistances() ? iShortDistanceConflict : iDistanceConflict);
550                }
551            }
552            double toc = 0.0;
553            if (timeOverlappingConflicts != null) {
554                for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
555                    toc += base * Math.min(iTimeOverlapFactor * c.getShare() / enrollment.getNrSlots(), iTimeOverlapMaxLimit);
556                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
557                    if (other.getRequest() != null)
558                        toc += getWeightMultiplicative(assignment, other) * Math.min(iTimeOverlapFactor * c.getShare() / other.getNrSlots(), iTimeOverlapMaxLimit);
559                }
560            }
561            return round(base - dc - toc);
562        }
563    }
564    
565    
566    @Override
567    public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) {
568        if (currentSolution.getBestInfo() == null) return true;
569        if (iMaximizeAssignment) {
570            long acr = Math.round(((StudentSectioningModel)currentSolution.getModel()).getContext(currentSolution.getAssignment()).getAssignedCourseRequestWeight());
571            long bcr = Math.round(((StudentSectioningModel)currentSolution.getModel()).getBestAssignedCourseRequestWeight());
572            if (acr != bcr)
573                return acr > bcr;
574        }
575        return ((StudentSectioningModel)currentSolution.getModel()).getTotalValue(currentSolution.getAssignment(), iPreciseComparison) < currentSolution.getBestValue();
576    }
577    
578    @Override
579    public boolean isFreeTimeAllowOverlaps() {
580        return false;
581    }
582    
583    /**
584     * Test case -- run to see the weights for a few courses
585     * @param args program arguments
586     */
587    public static void main(String[] args) {
588        PriorityStudentWeights pw = new PriorityStudentWeights(new DataProperties());
589        DecimalFormat df = new DecimalFormat("0.000000");
590        Student s = new Student(0l);
591        new CourseRequest(1l, 0, false, s, ToolBox.toList(
592                new Course(1, "A", "1", new Offering(0, "A")),
593                new Course(1, "A", "2", new Offering(0, "A")),
594                new Course(1, "A", "3", new Offering(0, "A"))), false, null);
595        new CourseRequest(2l, 1, false, s, ToolBox.toList(
596                new Course(1, "B", "1", new Offering(0, "B")),
597                new Course(1, "B", "2", new Offering(0, "B")),
598                new Course(1, "B", "3", new Offering(0, "B"))), false, null);
599        new CourseRequest(3l, 2, false, s, ToolBox.toList(
600                new Course(1, "C", "1", new Offering(0, "C")),
601                new Course(1, "C", "2", new Offering(0, "C")),
602                new Course(1, "C", "3", new Offering(0, "C"))), false, null);
603        new CourseRequest(4l, 3, false, s, ToolBox.toList(
604                new Course(1, "D", "1", new Offering(0, "D")),
605                new Course(1, "D", "2", new Offering(0, "D")),
606                new Course(1, "D", "3", new Offering(0, "D"))), false, null);
607        new CourseRequest(5l, 4, false, s, ToolBox.toList(
608                new Course(1, "E", "1", new Offering(0, "E")),
609                new Course(1, "E", "2", new Offering(0, "E")),
610                new Course(1, "E", "3", new Offering(0, "E"))), false, null);
611        new CourseRequest(6l, 5, true, s, ToolBox.toList(
612                new Course(1, "F", "1", new Offering(0, "F")),
613                new Course(1, "F", "2", new Offering(0, "F")),
614                new Course(1, "F", "3", new Offering(0, "F"))), false, null);
615        new CourseRequest(7l, 6, true, s, ToolBox.toList(
616                new Course(1, "G", "1", new Offering(0, "G")),
617                new Course(1, "G", "2", new Offering(0, "G")),
618                new Course(1, "G", "3", new Offering(0, "G"))), false, null);
619        
620        Assignment<Request, Enrollment> assignment = new DefaultSingleAssignment<Request, Enrollment>();
621        Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>());
622        for (Request r: s.getRequests()) {
623            CourseRequest cr = (CourseRequest)r;
624            double[] w = new double[] {0.0, 0.0, 0.0};
625            for (int i = 0; i < cr.getCourses().size(); i++) {
626                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
627                Set<SctAssignment> sections = new HashSet<SctAssignment>();
628                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
629                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
630                w[i] = pw.getWeight(assignment, e, null, null);
631            }
632            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
633        }
634
635        System.out.println("With one distance conflict:");
636        for (Request r: s.getRequests()) {
637            CourseRequest cr = (CourseRequest)r;
638            double[] w = new double[] {0.0, 0.0, 0.0};
639            for (int i = 0; i < cr.getCourses().size(); i++) {
640                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
641                Set<SctAssignment> sections = new HashSet<SctAssignment>();
642                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
643                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
644                Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
645                dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
646                w[i] = pw.getWeight(assignment, e, dc, null);
647            }
648            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
649        }
650
651        System.out.println("With two distance conflicts:");
652        for (Request r: s.getRequests()) {
653            CourseRequest cr = (CourseRequest)r;
654            double[] w = new double[] {0.0, 0.0, 0.0};
655            for (int i = 0; i < cr.getCourses().size(); i++) {
656                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
657                Set<SctAssignment> sections = new HashSet<SctAssignment>();
658                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
659                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
660                Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
661                dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
662                dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e,
663                        new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null)));
664                w[i] = pw.getWeight(assignment, e, dc, null);
665            }
666            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
667        }
668
669        System.out.println("With 25% time overlapping conflict:");
670        for (Request r: s.getRequests()) {
671            CourseRequest cr = (CourseRequest)r;
672            double[] w = new double[] {0.0, 0.0, 0.0};
673            for (int i = 0; i < cr.getCourses().size(); i++) {
674                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
675                Set<SctAssignment> sections = new HashSet<SctAssignment>();
676                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
677                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
678                Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>();
679                toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next()));
680                w[i] = pw.getWeight(assignment, e, null, toc);
681            }
682            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
683        }
684        
685        System.out.println("Disbalanced sections (by 2 / 10 students):");
686        for (Request r: s.getRequests()) {
687            CourseRequest cr = (CourseRequest)r;
688            double[] w = new double[] {0.0, 0.0, 0.0};
689            for (int i = 0; i < cr.getCourses().size(); i++) {
690                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
691                Set<SctAssignment> sections = new HashSet<SctAssignment>();
692                Subpart x = new Subpart(0, "Lec", "Lec", cfg, null);
693                Section a = new Section(0, 10, "x", x, p, null);
694                new Section(1, 10, "y", x, p, null);
695                sections.add(a);
696                a.assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment));
697                a.assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment));
698                cfg.getContext(assignment).assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment));
699                cfg.getContext(assignment).assigned(assignment, new Enrollment(s.getRequests().get(0), i, cfg, sections, assignment));
700                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
701                w[i] = pw.getWeight(assignment, e, null, null);
702            }
703            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
704        }
705        
706        System.out.println("Same choice sections:");
707        pw.iMPP = true;
708        for (Request r: s.getRequests()) {
709            CourseRequest cr = (CourseRequest)r;
710            double[] w = new double[] {0.0, 0.0, 0.0};
711            for (int i = 0; i < cr.getCourses().size(); i++) {
712                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
713                Set<SctAssignment> sections = new HashSet<SctAssignment>();
714                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
715                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
716                Set<SctAssignment> other = new HashSet<SctAssignment>();
717                other.add(new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
718                cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment));
719                w[i] = pw.getWeight(assignment, e, null, null);
720            }
721            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
722        }
723        
724        System.out.println("Same time sections:");
725        for (Request r: s.getRequests()) {
726            CourseRequest cr = (CourseRequest)r;
727            double[] w = new double[] {0.0, 0.0, 0.0};
728            for (int i = 0; i < cr.getCourses().size(); i++) {
729                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
730                Set<SctAssignment> sections = new HashSet<SctAssignment>();
731                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
732                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
733                Set<SctAssignment> other = new HashSet<SctAssignment>();
734                other.add(new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, new Instructor(1l, null, "Josef Novak", null)));
735                cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment));
736                w[i] = pw.getWeight(assignment, e, null, null);
737            }
738            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
739        }
740        
741        System.out.println("Different time sections:");
742        Placement q = new Placement(null, new TimeLocation(1, 102, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>());
743        for (Request r: s.getRequests()) {
744            CourseRequest cr = (CourseRequest)r;
745            double[] w = new double[] {0.0, 0.0, 0.0};
746            for (int i = 0; i < cr.getCourses().size(); i++) {
747                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
748                Set<SctAssignment> sections = new HashSet<SctAssignment>();
749                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
750                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
751                Set<SctAssignment> other = new HashSet<SctAssignment>();
752                other.add(new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), q, null));
753                cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment));
754                w[i] = pw.getWeight(assignment, e, null, null);
755            }
756            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
757        }
758        
759        System.out.println("Two sections, one same choice, one same time:");
760        for (Request r: s.getRequests()) {
761            CourseRequest cr = (CourseRequest)r;
762            double[] w = new double[] {0.0, 0.0, 0.0};
763            for (int i = 0; i < cr.getCourses().size(); i++) {
764                Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
765                Set<SctAssignment> sections = new HashSet<SctAssignment>();
766                sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
767                sections.add(new Section(1, 1, "y", new Subpart(1, "Rec", "Rec", cfg, null), p, null));
768                Enrollment e = new Enrollment(cr, i, cfg, sections, assignment);
769                Set<SctAssignment> other = new HashSet<SctAssignment>();
770                other.add(new Section(2, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null));
771                other.add(new Section(3, 1, "y", new Subpart(1, "Rec", "Rec", cfg, null), p, null, new Instructor(1l, null, "Josef Novak", null)));
772                cr.setInitialAssignment(new Enrollment(cr, i, cfg, other, assignment));
773                w[i] = pw.getWeight(assignment, e, null, null);
774            }
775            System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
776        }
777
778    }
779
780    @Override
781    public double getWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Set<StudentQuality.Conflict> qualityConflicts) {
782        if (iAdditiveWeights) {
783            double base = getBaseWeight(assignment, enrollment);
784            double penalty = 0.0;
785            if (qualityConflicts != null) {
786                for (StudentQuality.Conflict c: qualityConflicts) {
787                    switch (c.getType().getType()) {
788                        case REQUEST:
789                            if (enrollment.isCourseRequest())
790                                penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
791                            break;
792                        case BOTH:
793                            Enrollment other = c.getOther(enrollment);
794                            penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
795                            penalty += getBaseWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other);
796                            break;
797                        case LOWER:
798                            other = c.getOther(enrollment);
799                            if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
800                                penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
801                            else
802                                penalty += getBaseWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other);
803                            break;
804                        case HIGHER:
805                            other = c.getOther(enrollment);
806                            if (other.getRequest().getPriority() >= enrollment.getRequest().getPriority())
807                                penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
808                            else
809                                penalty += getBaseWeight(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other);
810                    }
811                }
812            }
813            return round(getWeight(assignment, enrollment) - penalty);
814        } else {
815            double base = getWeightMultiplicative(assignment, enrollment);
816            double penalty = 0.0;
817            if (qualityConflicts != null) {
818                for (StudentQuality.Conflict c: qualityConflicts) {
819                    Enrollment other = c.getOther(enrollment);
820                    switch (c.getType().getType()) {
821                        case REQUEST:
822                            if (enrollment.isCourseRequest())
823                                penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
824                            else if (other.isCourseRequest())
825                                penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other);
826                            break;
827                        case BOTH:
828                            penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
829                            if (other.getRequest() != null)
830                                penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other);
831                            break;
832                        case LOWER:
833                            other = c.getOther(enrollment);
834                            if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
835                                penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
836                            else if (other.getRequest() != null)
837                                penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other);
838                            break;
839                        case HIGHER:
840                            other = c.getOther(enrollment);
841                            if (other.getRequest().getPriority() >= enrollment.getRequest().getPriority())
842                                penalty += base * iQalityWeights[c.getType().ordinal()] * c.getWeight(enrollment);
843                            else if (other.getRequest() != null)
844                                penalty += getWeightMultiplicative(assignment, other) * iQalityWeights[c.getType().ordinal()] * c.getWeight(other);
845                    }
846                }
847            }
848            return round(base - penalty);
849        }
850    }
851
852    @Override
853    public double getStudentQualityConflictWeight(Assignment<Request, Enrollment> assignment, Enrollment enrollment, Conflict conflict) {
854        switch (conflict.getType().getType()) {
855            case BOTH:
856                if (enrollment == null || enrollment.getRequest() == null) return 0.0;
857                if (iAdditiveWeights) {
858                    return round(getBaseWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment));
859                } else {
860                    return round(getWeightMultiplicative(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment));
861                }
862            case REQUEST:
863                if (enrollment == null || enrollment.getRequest() == null || !enrollment.isCourseRequest()) return 0.0;
864                if (iAdditiveWeights) {
865                    return round(getBaseWeight(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment));
866                } else {
867                    return round(getWeightMultiplicative(assignment, enrollment) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(enrollment));
868                }
869            case LOWER:
870                if (iAdditiveWeights) {
871                    if (conflict.getR1().getPriority() < conflict.getR2().getPriority()) {
872                        return round(getBaseWeight(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2()));
873                    } else {
874                        return round(getBaseWeight(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1()));
875                    }
876                } else {
877                    if (conflict.getR1().getPriority() < conflict.getR2().getPriority()) {
878                        return round(getWeightMultiplicative(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2()));
879                    } else {
880                        return round(getWeightMultiplicative(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1()));
881                    }
882                }
883            case HIGHER:
884                if (iAdditiveWeights) {
885                    if (conflict.getR1().getPriority() > conflict.getR2().getPriority()) {
886                        return round(getBaseWeight(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2()));
887                    } else {
888                        return round(getBaseWeight(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1()));
889                    }
890                } else {
891                    if (conflict.getR1().getPriority() < conflict.getR2().getPriority()) {
892                        return round(getWeightMultiplicative(assignment, conflict.getE2()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE2()));
893                    } else {
894                        return round(getWeightMultiplicative(assignment, conflict.getE1()) * iQalityWeights[conflict.getType().ordinal()] * conflict.getWeight(conflict.getE1()));
895                    }
896                }
897            default:
898                return 0.0;
899        }
900    }
901}