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