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        /**
207         * Test case -- run to see the weights for a few courses
208         */
209        public static void main(String[] args) {
210            PriorityStudentWeights pw = new PriorityStudentWeights(new DataProperties());
211            DecimalFormat df = new DecimalFormat("0.0000");
212            Student s = new Student(0l);
213            new CourseRequest(1l, 0, false, s, ToolBox.toList(
214                    new Course(1, "A", "1", new Offering(0, "A")),
215                    new Course(1, "A", "2", new Offering(0, "A")),
216                    new Course(1, "A", "3", new Offering(0, "A"))), false, null);
217            new CourseRequest(2l, 1, false, s, ToolBox.toList(
218                    new Course(1, "B", "1", new Offering(0, "B")),
219                    new Course(1, "B", "2", new Offering(0, "B")),
220                    new Course(1, "B", "3", new Offering(0, "B"))), false, null);
221            new CourseRequest(3l, 2, false, s, ToolBox.toList(
222                    new Course(1, "C", "1", new Offering(0, "C")),
223                    new Course(1, "C", "2", new Offering(0, "C")),
224                    new Course(1, "C", "3", new Offering(0, "C"))), false, null);
225            new CourseRequest(4l, 3, false, s, ToolBox.toList(
226                    new Course(1, "D", "1", new Offering(0, "D")),
227                    new Course(1, "D", "2", new Offering(0, "D")),
228                    new Course(1, "D", "3", new Offering(0, "D"))), false, null);
229            new CourseRequest(5l, 4, false, s, ToolBox.toList(
230                    new Course(1, "E", "1", new Offering(0, "E")),
231                    new Course(1, "E", "2", new Offering(0, "E")),
232                    new Course(1, "E", "3", new Offering(0, "E"))), false, null);
233            new CourseRequest(6l, 5, true, s, ToolBox.toList(
234                    new Course(1, "F", "1", new Offering(0, "F")),
235                    new Course(1, "F", "2", new Offering(0, "F")),
236                    new Course(1, "F", "3", new Offering(0, "F"))), false, null);
237            new CourseRequest(7l, 6, true, s, ToolBox.toList(
238                    new Course(1, "G", "1", new Offering(0, "G")),
239                    new Course(1, "G", "2", new Offering(0, "G")),
240                    new Course(1, "G", "3", new Offering(0, "G"))), false, null);
241            
242            Placement p = new Placement(null, new TimeLocation(1, 90, 12, 0, 0, null, null, new BitSet(), 10), new ArrayList<RoomLocation>());
243            for (Request r: s.getRequests()) {
244                CourseRequest cr = (CourseRequest)r;
245                double[] w = new double[] {0.0, 0.0, 0.0};
246                for (int i = 0; i < cr.getCourses().size(); i++) {
247                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
248                    Set<Assignment> sections = new HashSet<Assignment>();
249                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
250                    Enrollment e = new Enrollment(cr, i, cfg, sections);
251                    w[i] = pw.getWeight(e, null, null);
252                }
253                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
254            }
255    
256            System.out.println("With one distance conflict:");
257            for (Request r: s.getRequests()) {
258                CourseRequest cr = (CourseRequest)r;
259                double[] w = new double[] {0.0, 0.0, 0.0};
260                for (int i = 0; i < cr.getCourses().size(); i++) {
261                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
262                    Set<Assignment> sections = new HashSet<Assignment>();
263                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
264                    Enrollment e = new Enrollment(cr, i, cfg, sections);
265                    Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
266                    dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
267                    w[i] = pw.getWeight(e, dc, null);
268                }
269                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
270            }
271    
272            System.out.println("With two distance conflicts:");
273            for (Request r: s.getRequests()) {
274                CourseRequest cr = (CourseRequest)r;
275                double[] w = new double[] {0.0, 0.0, 0.0};
276                for (int i = 0; i < cr.getCourses().size(); i++) {
277                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
278                    Set<Assignment> sections = new HashSet<Assignment>();
279                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
280                    Enrollment e = new Enrollment(cr, i, cfg, sections);
281                    Set<DistanceConflict.Conflict> dc = new HashSet<DistanceConflict.Conflict>();
282                    dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e, (Section)sections.iterator().next()));
283                    dc.add(new DistanceConflict.Conflict(s, e, (Section)sections.iterator().next(), e,
284                            new Section(1, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null)));
285                    w[i] = pw.getWeight(e, dc, null);
286                }
287                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
288            }
289    
290            System.out.println("With 25% time overlapping conflict:");
291            for (Request r: s.getRequests()) {
292                CourseRequest cr = (CourseRequest)r;
293                double[] w = new double[] {0.0, 0.0, 0.0};
294                for (int i = 0; i < cr.getCourses().size(); i++) {
295                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
296                    Set<Assignment> sections = new HashSet<Assignment>();
297                    sections.add(new Section(0, 1, "x", new Subpart(0, "Lec", "Lec", cfg, null), p, null, null, null));
298                    Enrollment e = new Enrollment(cr, i, cfg, sections);
299                    Set<TimeOverlapsCounter.Conflict> toc = new HashSet<TimeOverlapsCounter.Conflict>();
300                    toc.add(new TimeOverlapsCounter.Conflict(s, 3, e, sections.iterator().next(), e, sections.iterator().next()));
301                    w[i] = pw.getWeight(e, null, toc);
302                }
303                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
304            }
305            
306            System.out.println("Disbalanced sections (by 2 / 10 students):");
307            for (Request r: s.getRequests()) {
308                CourseRequest cr = (CourseRequest)r;
309                double[] w = new double[] {0.0, 0.0, 0.0};
310                for (int i = 0; i < cr.getCourses().size(); i++) {
311                    Config cfg = new Config(0l, -1, "", cr.getCourses().get(i).getOffering());
312                    Set<Assignment> sections = new HashSet<Assignment>();
313                    Subpart x = new Subpart(0, "Lec", "Lec", cfg, null);
314                    Section a = new Section(0, 10, "x", x, p, null, null, null);
315                    new Section(1, 10, "y", x, p, null, null, null);
316                    sections.add(a);
317                    a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
318                    a.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
319                    cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
320                    cfg.assigned(new Enrollment(s.getRequests().get(0), i, cfg, sections));
321                    Enrollment e = new Enrollment(cr, i, cfg, sections);
322                    w[i] = pw.getWeight(e, null, null);
323                }
324                System.out.println(cr + ": " + df.format(w[0]) + "  " + df.format(w[1]) + "  " + df.format(w[2]));
325            }
326        }
327    }