001    package net.sf.cpsolver.studentsct.weights;
002    
003    import java.text.DecimalFormat;
004    import java.util.ArrayList;
005    import java.util.BitSet;
006    import java.util.HashSet;
007    import java.util.Set;
008    
009    import net.sf.cpsolver.coursett.model.Placement;
010    import net.sf.cpsolver.coursett.model.RoomLocation;
011    import net.sf.cpsolver.coursett.model.TimeLocation;
012    import net.sf.cpsolver.ifs.solution.Solution;
013    import net.sf.cpsolver.ifs.util.DataProperties;
014    import net.sf.cpsolver.ifs.util.ToolBox;
015    import net.sf.cpsolver.studentsct.extension.DistanceConflict;
016    import net.sf.cpsolver.studentsct.extension.TimeOverlapsCounter;
017    import net.sf.cpsolver.studentsct.model.Assignment;
018    import net.sf.cpsolver.studentsct.model.Config;
019    import net.sf.cpsolver.studentsct.model.Course;
020    import net.sf.cpsolver.studentsct.model.CourseRequest;
021    import net.sf.cpsolver.studentsct.model.Enrollment;
022    import net.sf.cpsolver.studentsct.model.Offering;
023    import net.sf.cpsolver.studentsct.model.Request;
024    import net.sf.cpsolver.studentsct.model.Section;
025    import net.sf.cpsolver.studentsct.model.Student;
026    import net.sf.cpsolver.studentsct.model.Subpart;
027    
028    /**
029     * New weighting model. It tries to obey the following principles:
030     * <ul>
031     *      <li> Total student weight is between zero and one (one means student got the best schedule)
032     *      <li> Weight of the given priority course is higher than sum of the remaining weights the student can get
033     *      <li> First alternative is better than the following course
034     *      <li> Second alternative is better than the second following course
035     *      <li> Distance conflicts are considered secondary (priorities should be maximized first)
036     *      <li> If alternative sections are otherwise equal, use the better balanced one
037     * </ul>
038     * 
039     * @version StudentSct 1.2 (Student Sectioning)<br>
040     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
041     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
042     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
043     * <br>
044     *          This library is free software; you can redistribute it and/or modify
045     *          it under the terms of the GNU Lesser General Public License as
046     *          published by the Free Software Foundation; either version 3 of the
047     *          License, or (at your option) any later version. <br>
048     * <br>
049     *          This library is distributed in the hope that it will be useful, but
050     *          WITHOUT ANY WARRANTY; without even the implied warranty of
051     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
052     *          Lesser General Public License for more details. <br>
053     * <br>
054     *          You should have received a copy of the GNU Lesser General Public
055     *          License along with this library; if not see
056     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
057     */
058    
059    public class PriorityStudentWeights implements StudentWeights {
060        protected double iPriorityFactor = 0.5010;
061        protected double iFirstAlternativeFactor = 0.5010;
062        protected double iSecondAlternativeFactor = 0.2510;
063        protected double iDistanceConflict = 0.0100;
064        protected double iTimeOverlapFactor = 0.5000;
065        protected double iTimeOverlapMaxLimit = 0.5000;
066        protected boolean iLeftoverSpread = false;
067        protected double iBalancingFactor = 0.0050;
068        protected double iAlternativeRequestFactor = 0.1260;
069        protected double iProjectedStudentWeight = 0.0100;
070        
071        public PriorityStudentWeights(DataProperties config) {
072            iPriorityFactor = config.getPropertyDouble("StudentWeights.Priority", iPriorityFactor);
073            iFirstAlternativeFactor = config.getPropertyDouble("StudentWeights.FirstAlternative", iFirstAlternativeFactor);
074            iSecondAlternativeFactor = config.getPropertyDouble("StudentWeights.SecondAlternative", iSecondAlternativeFactor);
075            iDistanceConflict = config.getPropertyDouble("StudentWeights.DistanceConflict", iDistanceConflict);
076            iTimeOverlapFactor = config.getPropertyDouble("StudentWeights.TimeOverlapFactor", iTimeOverlapFactor);
077            iTimeOverlapMaxLimit = config.getPropertyDouble("StudentWeights.TimeOverlapMaxLimit", iTimeOverlapMaxLimit);
078            iLeftoverSpread = config.getPropertyBoolean("StudentWeights.LeftoverSpread", iLeftoverSpread);
079            iBalancingFactor = config.getPropertyDouble("StudentWeights.BalancingFactor", iBalancingFactor);
080            iAlternativeRequestFactor = config.getPropertyDouble("StudentWeights.AlternativeRequestFactor", iAlternativeRequestFactor);
081            iProjectedStudentWeight = config.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight);
082        }
083            
084        public double getWeight(Request request) {
085            if (request.getStudent().isDummy() && iProjectedStudentWeight >= 0.0) {
086                double weight = iProjectedStudentWeight;
087                if (request.isAlternative())
088                    weight *= iAlternativeRequestFactor;
089                return weight;
090            }
091            double total = 10000.0;
092            int nrReq = request.getStudent().nrRequests();
093            double remain = (iLeftoverSpread ? Math.floor(10000.0 * Math.pow(iPriorityFactor, nrReq) / nrReq) : 0.0);
094            for (int idx = 0; idx < request.getStudent().getRequests().size(); idx++) {
095                Request r = request.getStudent().getRequests().get(idx);
096                boolean last = (idx + 1 == request.getStudent().getRequests().size());
097                boolean lastNotAlt = !r.isAlternative() && (last || request.getStudent().getRequests().get(1 + idx).isAlternative());
098                double w = Math.ceil(iPriorityFactor * total) + remain;
099                if (lastNotAlt || last) {
100                    w = total;
101                } else {
102                    total -= w;
103                }
104                if (r.equals(request)) {
105                    return w / 10000.0;
106                }
107            }
108            return 0.0;
109        }
110        
111        public double getCachedWeight(Request request) {
112            Double w = (Double)request.getExtra();
113            if (w == null) {
114                w = getWeight(request);
115                request.setExtra(w);
116            }
117            return w;
118        }
119    
120        @Override
121        public double getBound(Request request) {
122            return getCachedWeight(request);
123        }
124        
125        protected double round(double value) {
126            return Math.ceil(10000.0 * value) / 10000.0;
127        }
128        
129        @Override
130        public double getWeight(Enrollment enrollment) {
131            double weight = getCachedWeight(enrollment.getRequest());
132            switch (enrollment.getPriority()) {
133                case 1: weight *= iFirstAlternativeFactor; break;
134                case 2: weight *= iSecondAlternativeFactor; break;
135            }
136            if (enrollment.isCourseRequest() && iBalancingFactor != 0.0) {
137                double configUsed = enrollment.getConfig().getEnrollmentWeight(enrollment.getRequest()) + enrollment.getRequest().getWeight();
138                double disbalanced = 0;
139                double total = 0;
140                for (Section section: enrollment.getSections()) {
141                    Subpart subpart = section.getSubpart();
142                    if (subpart.getSections().size() <= 1) continue;
143                    double used = section.getEnrollmentWeight(enrollment.getRequest()) + enrollment.getRequest().getWeight();
144                    // sections have limits -> desired size is section limit x (total enrollment / total limit)
145                    // unlimited sections -> desired size is total enrollment / number of sections
146                    double desired = (subpart.getLimit() > 0
147                            ? section.getLimit() * (configUsed / subpart.getLimit())
148                            : configUsed / subpart.getSections().size());
149                    if (used > desired)
150                        disbalanced += Math.min(enrollment.getRequest().getWeight(), used - desired) / enrollment.getRequest().getWeight();
151                    else
152                        disbalanced -= Math.min(enrollment.getRequest().getWeight(), desired - used) / enrollment.getRequest().getWeight();
153                    total ++;
154                }
155                if (disbalanced > 0)
156                    weight *= (1.0 - disbalanced / total * iBalancingFactor);
157            }
158            return round(weight);
159        }
160        
161        @Override
162        public double getDistanceConflictWeight(DistanceConflict.Conflict c) {
163            if (c.getR1().getPriority() < c.getR2().getPriority()) {
164                return round(getWeight(c.getE2()) * iDistanceConflict);
165            } else {
166                return round(getWeight(c.getE1()) * iDistanceConflict);
167            }
168        }
169        
170        @Override
171        public double getTimeOverlapConflictWeight(Enrollment e, TimeOverlapsCounter.Conflict c) {
172            double toc = Math.min(iTimeOverlapMaxLimit * c.getShare() / e.getNrSlots(), iTimeOverlapMaxLimit);
173            return round(getWeight(e) * toc);
174        }
175        
176        @Override
177        public double getWeight(Enrollment enrollment, Set<DistanceConflict.Conflict> distanceConflicts, Set<TimeOverlapsCounter.Conflict> timeOverlappingConflicts) {
178            double base = getWeight(enrollment);
179            double dc = 0.0;
180            if (distanceConflicts != null) {
181                for (DistanceConflict.Conflict c: distanceConflicts) {
182                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
183                    if (other.getRequest().getPriority() <= enrollment.getRequest().getPriority())
184                        dc += base * iDistanceConflict;
185                    else
186                        dc += getWeight(other) * iDistanceConflict;
187                }
188            }
189            double toc = 0.0;
190            if (timeOverlappingConflicts != null) {
191                for (TimeOverlapsCounter.Conflict c: timeOverlappingConflicts) {
192                    toc += base * Math.min(iTimeOverlapFactor * c.getShare() / enrollment.getNrSlots(), iTimeOverlapMaxLimit);
193                    Enrollment other = (c.getE1().equals(enrollment) ? c.getE2() : c.getE1());
194                    toc += getWeight(other) * Math.min(iTimeOverlapFactor * c.getShare() / other.getNrSlots(), iTimeOverlapMaxLimit);
195                }
196            }
197            return round(base - dc - toc);
198        }
199        
200        
201        @Override
202        public boolean isBetterThanBestSolution(Solution<Request, Enrollment> currentSolution) {
203            return currentSolution.getBestInfo() == null || currentSolution.getModel().getTotalValue() < currentSolution.getBestValue();
204        }
205        
206        @Override
207        public boolean isFreeTimeAllowOverlaps() {
208            return false;
209        }
210        
211        /**
212         * Test case -- run to see the weights for a few courses
213         */
214        public static void main(String[] args) {
215            PriorityStudentWeights pw = new PriorityStudentWeights(new DataProperties());
216            DecimalFormat df = new DecimalFormat("0.0000");
217            Student s = new Student(0l);
218            new CourseRequest(1l, 0, false, s, ToolBox.toList(
219                    new Course(1, "A", "1", new Offering(0, "A")),
220                    new Course(1, "A", "2", new Offering(0, "A")),
221                    new Course(1, "A", "3", new Offering(0, "A"))), false, null);
222            new CourseRequest(2l, 1, false, s, ToolBox.toList(
223                    new Course(1, "B", "1", new Offering(0, "B")),
224                    new Course(1, "B", "2", new Offering(0, "B")),
225                    new Course(1, "B", "3", new Offering(0, "B"))), false, null);
226            new CourseRequest(3l, 2, false, s, ToolBox.toList(
227                    new Course(1, "C", "1", new Offering(0, "C")),
228                    new Course(1, "C", "2", new Offering(0, "C")),
229                    new Course(1, "C", "3", new Offering(0, "C"))), false, null);
230            new CourseRequest(4l, 3, false, s, ToolBox.toList(
231                    new Course(1, "D", "1", new Offering(0, "D")),
232                    new Course(1, "D", "2", new Offering(0, "D")),
233                    new Course(1, "D", "3", new Offering(0, "D"))), false, null);
234            new CourseRequest(5l, 4, false, s, ToolBox.toList(
235                    new Course(1, "E", "1", new Offering(0, "E")),
236                    new Course(1, "E", "2", new Offering(0, "E")),
237                    new Course(1, "E", "3", new Offering(0, "E"))), false, null);
238            new CourseRequest(6l, 5, true, s, ToolBox.toList(
239                    new Course(1, "F", "1", new Offering(0, "F")),
240                    new Course(1, "F", "2", new Offering(0, "F")),
241                    new Course(1, "F", "3", new Offering(0, "F"))), false, null);
242            new CourseRequest(7l, 6, true, s, ToolBox.toList(
243                    new Course(1, "G", "1", new Offering(0, "G")),
244                    new Course(1, "G", "2", new Offering(0, "G")),
245                    new Course(1, "G", "3", new Offering(0, "G"))), false, null);
246            
247            Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>());
248            for (Request r: s.getRequests()) {
249                CourseRequest cr = (CourseRequest)r;
250                double[] w = new double[] {0.0, 0.0, 0.0};
251                for (int i = 0; i < cr.getCourses().size(); i++) {
252                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
253                    Set<Assignment> sections = new HashSet<Assignment>();
254                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
255                    Enrollment e = new Enrollment(cr, i, cfg, sections);
256                    w[i] = pw.getWeight(e, null, null);
257                }
258                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
259            }
260    
261            System.out.println("With one distance conflict:");
262            for (Request r: s.getRequests()) {
263                CourseRequest cr = (CourseRequest)r;
264                double[] w = new double[] {0.0, 0.0, 0.0};
265                for (int i = 0; i < cr.getCourses().size(); i++) {
266                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
267                    Set<Assignment> sections = new HashSet<Assignment>();
268                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
269                    Enrollment e = new Enrollment(cr, i, cfg, sections);
270                    Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
271                    dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
272                    w[i] = pw.getWeight(e, dc, null);
273                }
274                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
275            }
276    
277            System.out.println("With two distance conflicts:");
278            for (Request r: s.getRequests()) {
279                CourseRequest cr = (CourseRequest)r;
280                double[] w = new double[] {0.0, 0.0, 0.0};
281                for (int i = 0; i < cr.getCourses().size(); i++) {
282                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
283                    Set<Assignment> sections = new HashSet<Assignment>();
284                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
285                    Enrollment e = new Enrollment(cr, i, cfg, sections);
286                    Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
287                    dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
288                    dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e,
289                            new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)));
290                    w[i] = pw.getWeight(e, dc, null);
291                }
292                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
293            }
294    
295            System.out.println("With 25% time overlapping conflict:");
296            for (Request r: s.getRequests()) {
297                CourseRequest cr = (CourseRequest)r;
298                double[] w = new double[] {0.0, 0.0, 0.0};
299                for (int i = 0; i < cr.getCourses().size(); i++) {
300                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
301                    Set<Assignment> sections = new HashSet<Assignment>();
302                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
303                    Enrollment e = new Enrollment(cr, i, cfg, sections);
304                    Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>();
305                    toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next()));
306                    w[i] = pw.getWeight(e, null, toc);
307                }
308                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
309            }
310            
311            System.out.println("Disbalanced sections (by 2 / 10 students):");
312            for (Request r: s.getRequests()) {
313                CourseRequest cr = (CourseRequest)r;
314                double[] w = new double[] {0.0, 0.0, 0.0};
315                for (int i = 0; i < cr.getCourses().size(); i++) {
316                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
317                    Set<Assignment> sections = new HashSet<Assignment>();
318                    Subpart x = new Subpart(0, "Lec", "Lec", cfg, null);
319                    Section a = new Section(0, 10, "x", x, p, null, null, null);
320                    new Section(1, 10, "y", x, p, null, null, null);
321                    sections.add(a);
322                    a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
323                    a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
324                    cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
325                    cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
326                    Enrollment e = new Enrollment(cr, i, cfg, sections);
327                    w[i] = pw.getWeight(e, null, null);
328                }
329                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
330            }
331        }
332    }