001package org.cpsolver.studentsct;
002
003import java.text.DecimalFormat;
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Comparator;
007import java.util.HashSet;
008import java.util.List;
009import java.util.Map;
010import java.util.Set;
011import java.util.TreeSet;
012
013import org.apache.log4j.Logger;
014import org.cpsolver.ifs.assignment.Assignment;
015import org.cpsolver.ifs.assignment.InheritedAssignment;
016import org.cpsolver.ifs.assignment.OptimisticInheritedAssignment;
017import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
018import org.cpsolver.ifs.assignment.context.ModelWithContext;
019import org.cpsolver.ifs.model.Constraint;
020import org.cpsolver.ifs.model.ConstraintListener;
021import org.cpsolver.ifs.model.InfoProvider;
022import org.cpsolver.ifs.model.Model;
023import org.cpsolver.ifs.solution.Solution;
024import org.cpsolver.ifs.util.DataProperties;
025import org.cpsolver.studentsct.constraint.ConfigLimit;
026import org.cpsolver.studentsct.constraint.CourseLimit;
027import org.cpsolver.studentsct.constraint.LinkedSections;
028import org.cpsolver.studentsct.constraint.RequiredReservation;
029import org.cpsolver.studentsct.constraint.ReservationLimit;
030import org.cpsolver.studentsct.constraint.SectionLimit;
031import org.cpsolver.studentsct.constraint.StudentConflict;
032import org.cpsolver.studentsct.extension.DistanceConflict;
033import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
034import org.cpsolver.studentsct.model.Config;
035import org.cpsolver.studentsct.model.Course;
036import org.cpsolver.studentsct.model.CourseRequest;
037import org.cpsolver.studentsct.model.Enrollment;
038import org.cpsolver.studentsct.model.Offering;
039import org.cpsolver.studentsct.model.Request;
040import org.cpsolver.studentsct.model.Section;
041import org.cpsolver.studentsct.model.Student;
042import org.cpsolver.studentsct.model.Subpart;
043import org.cpsolver.studentsct.reservation.Reservation;
044import org.cpsolver.studentsct.weights.PriorityStudentWeights;
045import org.cpsolver.studentsct.weights.StudentWeights;
046
047/**
048 * Student sectioning model.
049 * 
050 * <br>
051 * <br>
052 * 
053 * @version StudentSct 1.3 (Student Sectioning)<br>
054 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
055 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
056 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
057 * <br>
058 *          This library is free software; you can redistribute it and/or modify
059 *          it under the terms of the GNU Lesser General Public License as
060 *          published by the Free Software Foundation; either version 3 of the
061 *          License, or (at your option) any later version. <br>
062 * <br>
063 *          This library is distributed in the hope that it will be useful, but
064 *          WITHOUT ANY WARRANTY; without even the implied warranty of
065 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
066 *          Lesser General Public License for more details. <br>
067 * <br>
068 *          You should have received a copy of the GNU Lesser General Public
069 *          License along with this library; if not see
070 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
071 */
072public class StudentSectioningModel extends ModelWithContext<Request, Enrollment, StudentSectioningModel.StudentSectioningModelContext> {
073    private static Logger sLog = Logger.getLogger(StudentSectioningModel.class);
074    protected static DecimalFormat sDecimalFormat = new DecimalFormat("0.000");
075    private List<Student> iStudents = new ArrayList<Student>();
076    private List<Offering> iOfferings = new ArrayList<Offering>();
077    private List<LinkedSections> iLinkedSections = new ArrayList<LinkedSections>();
078    private DataProperties iProperties;
079    private DistanceConflict iDistanceConflict = null;
080    private TimeOverlapsCounter iTimeOverlaps = null;
081    private int iNrDummyStudents = 0, iNrDummyRequests = 0;
082    private double iTotalDummyWeight = 0.0;
083    private double iTotalCRWeight = 0.0, iTotalDummyCRWeight = 0.0;
084    private double iTotalReservedSpace = 0.0;
085    private StudentWeights iStudentWeights = null;
086    private boolean iReservationCanAssignOverTheLimit;
087    protected double iProjectedStudentWeight = 0.0100;
088    private int iMaxDomainSize = -1; 
089
090
091    /**
092     * Constructor
093     * 
094     * @param properties
095     *            configuration
096     */
097    @SuppressWarnings("unchecked")
098    public StudentSectioningModel(DataProperties properties) {
099        super();
100        iReservationCanAssignOverTheLimit =  properties.getPropertyBoolean("Reservation.CanAssignOverTheLimit", false);
101        iStudentWeights = new PriorityStudentWeights(properties);
102        iMaxDomainSize = properties.getPropertyInt("Sectioning.MaxDomainSize", iMaxDomainSize);
103        if (properties.getPropertyBoolean("Sectioning.SectionLimit", true)) {
104            SectionLimit sectionLimit = new SectionLimit(properties);
105            addGlobalConstraint(sectionLimit);
106            if (properties.getPropertyBoolean("Sectioning.SectionLimit.Debug", false)) {
107                sectionLimit.addConstraintListener(new ConstraintListener<Request, Enrollment>() {
108                    @Override
109                    public void constraintBeforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Constraint<Request, Enrollment> constraint, Enrollment enrollment, Set<Enrollment> unassigned) {
110                        if (enrollment.getStudent().isDummy())
111                            for (Enrollment conflict : unassigned) {
112                                if (!conflict.getStudent().isDummy()) {
113                                    sLog.warn("Enrolment of a real student " + conflict.getStudent() + " is unassigned "
114                                            + "\n  -- " + conflict + "\ndue to an enrollment of a dummy student "
115                                            + enrollment.getStudent() + " " + "\n  -- " + enrollment);
116                                }
117                            }
118                    }
119
120                    @Override
121                    public void constraintAfterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Constraint<Request, Enrollment> constraint, Enrollment assigned, Set<Enrollment> unassigned) {
122                    }
123                });
124            }
125        }
126        if (properties.getPropertyBoolean("Sectioning.ConfigLimit", true)) {
127            ConfigLimit configLimit = new ConfigLimit(properties);
128            addGlobalConstraint(configLimit);
129        }
130        if (properties.getPropertyBoolean("Sectioning.CourseLimit", true)) {
131            CourseLimit courseLimit = new CourseLimit(properties);
132            addGlobalConstraint(courseLimit);
133        }
134        if (properties.getPropertyBoolean("Sectioning.ReservationLimit", true)) {
135            ReservationLimit reservationLimit = new ReservationLimit(properties);
136            addGlobalConstraint(reservationLimit);
137        }
138        if (properties.getPropertyBoolean("Sectioning.RequiredReservations", true)) {
139            RequiredReservation requiredReservation = new RequiredReservation();
140            addGlobalConstraint(requiredReservation);
141        }
142        try {
143            Class<StudentWeights> studentWeightsClass = (Class<StudentWeights>)Class.forName(properties.getProperty("StudentWeights.Class", PriorityStudentWeights.class.getName()));
144            iStudentWeights = studentWeightsClass.getConstructor(DataProperties.class).newInstance(properties);
145        } catch (Exception e) {
146            sLog.error("Unable to create custom student weighting model (" + e.getMessage() + "), using default.", e);
147            iStudentWeights = new PriorityStudentWeights(properties);
148        }
149        iProjectedStudentWeight = properties.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight);
150        iProperties = properties;
151    }
152    
153    /**
154     * Return true if reservation that has {@link Reservation#canAssignOverLimit()} can assign enrollments over the limit
155     * @return true if reservation that has {@link Reservation#canAssignOverLimit()} can assign enrollments over the limit
156     */
157    public boolean getReservationCanAssignOverTheLimit() {
158        return iReservationCanAssignOverTheLimit;
159    }
160    
161    /**
162     * Return student weighting model
163     * @return student weighting model
164     */
165    public StudentWeights getStudentWeights() {
166        return iStudentWeights;
167    }
168
169    /**
170     * Set student weighting model
171     * @param weights student weighting model
172     */
173    public void setStudentWeights(StudentWeights weights) {
174        iStudentWeights = weights;
175    }
176
177    /**
178     * Students
179     * @return all students in the problem
180     */
181    public List<Student> getStudents() {
182        return iStudents;
183    }
184
185    /**
186     * Add a student into the model
187     * @param student a student to be added into the problem
188     */
189    public void addStudent(Student student) {
190        iStudents.add(student);
191        if (student.isDummy())
192            iNrDummyStudents++;
193        for (Request request : student.getRequests())
194            addVariable(request);
195        if (getProperties().getPropertyBoolean("Sectioning.StudentConflict", true)) {
196            addConstraint(new StudentConflict(student));
197        }
198    }
199    
200    @Override
201    public void addVariable(Request request) {
202        super.addVariable(request);
203        if (request instanceof CourseRequest)
204            iTotalCRWeight += request.getWeight();
205        if (request.getStudent().isDummy()) {
206            iNrDummyRequests++;
207            iTotalDummyWeight += request.getWeight();
208            if (request instanceof CourseRequest)
209                iTotalDummyCRWeight += request.getWeight();
210        }
211    }
212    
213    /** 
214     * Recompute cached request weights
215     * @param assignment current assignment
216     */
217    public void requestWeightsChanged(Assignment<Request, Enrollment> assignment) {
218        getContext(assignment).requestWeightsChanged(assignment);
219    }
220
221    /**
222     * Remove a student from the model
223     * @param student a student to be removed from the problem
224     */
225    public void removeStudent(Student student) {
226        iStudents.remove(student);
227        if (student.isDummy())
228            iNrDummyStudents--;
229        StudentConflict conflict = null;
230        for (Request request : student.getRequests()) {
231            for (Constraint<Request, Enrollment> c : request.constraints()) {
232                if (c instanceof StudentConflict) {
233                    conflict = (StudentConflict) c;
234                    break;
235                }
236            }
237            if (conflict != null) 
238                conflict.removeVariable(request);
239            removeVariable(request);
240        }
241        if (conflict != null) 
242            removeConstraint(conflict);
243    }
244    
245    @Override
246    public void removeVariable(Request request) {
247        super.removeVariable(request);
248        if (request instanceof CourseRequest) {
249            CourseRequest cr = (CourseRequest)request;
250            for (Course course: cr.getCourses())
251                course.getRequests().remove(request);
252        }
253        if (request.getStudent().isDummy()) {
254            iNrDummyRequests--;
255            iTotalDummyWeight -= request.getWeight();
256            if (request instanceof CourseRequest)
257                iTotalDummyCRWeight -= request.getWeight();
258        }
259        if (request instanceof CourseRequest)
260            iTotalCRWeight -= request.getWeight();
261    }
262
263
264    /**
265     * List of offerings
266     * @return all instructional offerings of the problem
267     */
268    public List<Offering> getOfferings() {
269        return iOfferings;
270    }
271
272    /**
273     * Add an offering into the model
274     * @param offering an instructional offering to be added into the problem
275     */
276    public void addOffering(Offering offering) {
277        iOfferings.add(offering);
278        offering.setModel(this);
279    }
280    
281    /**
282     * Link sections using {@link LinkedSections}
283     * @param sections a linked section constraint to be added into the problem
284     */
285    public void addLinkedSections(Section... sections) {
286        LinkedSections constraint = new LinkedSections(sections);
287        iLinkedSections.add(constraint);
288        constraint.createConstraints();
289    }
290
291    /**
292     * Link sections using {@link LinkedSections}
293     * @param sections a linked section constraint to be added into the problem
294     */
295    public void addLinkedSections(Collection<Section> sections) {
296        LinkedSections constraint = new LinkedSections(sections);
297        iLinkedSections.add(constraint);
298        constraint.createConstraints();
299    }
300
301    /**
302     * List of linked sections
303     * @return all linked section constraints of the problem
304     */
305    public List<LinkedSections> getLinkedSections() {
306        return iLinkedSections;
307    }
308
309    /**
310     * Model info
311     */
312    @Override
313    public Map<String, String> getInfo(Assignment<Request, Enrollment> assignment) {
314        Map<String, String> info = super.getInfo(assignment);
315        StudentSectioningModelContext context = getContext(assignment);
316        if (!getStudents().isEmpty())
317            info.put("Students with complete schedule", sDoubleFormat.format(100.0 * context.nrComplete() / getStudents().size()) + "% (" + context.nrComplete() + "/" + getStudents().size() + ")");
318        if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts(assignment) != 0)
319            info.put("Student distance conflicts", String.valueOf(getDistanceConflict().getTotalNrConflicts(assignment)));
320        if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts(assignment) != 0)
321            info.put("Time overlapping conflicts", String.valueOf(getTimeOverlaps().getTotalNrConflicts(assignment)));
322        int nrLastLikeStudents = getNrLastLikeStudents(false);
323        if (nrLastLikeStudents != 0 && nrLastLikeStudents != getStudents().size()) {
324            int nrRealStudents = getStudents().size() - nrLastLikeStudents;
325            int nrLastLikeCompleteStudents = getNrCompleteLastLikeStudents(assignment, false);
326            int nrRealCompleteStudents = context.nrComplete() - nrLastLikeCompleteStudents;
327            if (nrLastLikeStudents > 0)
328                info.put("Projected students with complete schedule", sDecimalFormat.format(100.0
329                        * nrLastLikeCompleteStudents / nrLastLikeStudents)
330                        + "% (" + nrLastLikeCompleteStudents + "/" + nrLastLikeStudents + ")");
331            if (nrRealStudents > 0)
332                info.put("Real students with complete schedule", sDecimalFormat.format(100.0 * nrRealCompleteStudents
333                        / nrRealStudents)
334                        + "% (" + nrRealCompleteStudents + "/" + nrRealStudents + ")");
335            int nrLastLikeRequests = getNrLastLikeRequests(false);
336            int nrRealRequests = variables().size() - nrLastLikeRequests;
337            int nrLastLikeAssignedRequests = context.getNrAssignedLastLikeRequests();
338            int nrRealAssignedRequests = assignment.nrAssignedVariables() - nrLastLikeAssignedRequests;
339            if (nrLastLikeRequests > 0)
340                info.put("Projected assigned requests", sDecimalFormat.format(100.0 * nrLastLikeAssignedRequests / nrLastLikeRequests)
341                        + "% (" + nrLastLikeAssignedRequests + "/" + nrLastLikeRequests + ")");
342            if (nrRealRequests > 0)
343                info.put("Real assigned requests", sDecimalFormat.format(100.0 * nrRealAssignedRequests / nrRealRequests)
344                        + "% (" + nrRealAssignedRequests + "/" + nrRealRequests + ")");
345            if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts(assignment) > 0)
346                info.put("Student distance conflicts", String.valueOf(getDistanceConflict().getTotalNrConflicts(assignment)));
347            if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts(assignment) > 0)
348                info.put("Time overlapping conflicts", String.valueOf(getTimeOverlaps().getTotalNrConflicts(assignment)));
349        }
350        context.getInfo(assignment, info);
351
352        return info;
353    }
354
355    /**
356     * Overall solution value
357     * @param assignment current assignment
358     * @param precise true if should be computed
359     * @return solution value
360     */
361    public double getTotalValue(Assignment<Request, Enrollment> assignment, boolean precise) {
362        if (precise) {
363            double total = 0;
364            for (Request r: assignment.assignedVariables())
365                total += r.getWeight() * iStudentWeights.getWeight(assignment, assignment.getValue(r));
366            if (iDistanceConflict != null)
367                for (DistanceConflict.Conflict c: iDistanceConflict.computeAllConflicts(assignment))
368                    total -= avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
369            if (iTimeOverlaps != null)
370                for (TimeOverlapsCounter.Conflict c: iTimeOverlaps.getContext(assignment).computeAllConflicts(assignment)) {
371                    total -= c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
372                    total -= c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
373                }
374            return -total;
375        }
376        return getContext(assignment).getTotalValue();
377    }
378    
379    /**
380     * Overall solution value
381     */
382    @Override
383    public double getTotalValue(Assignment<Request, Enrollment> assignment) {
384        return getContext(assignment).getTotalValue();
385    }
386
387    /**
388     * Configuration
389     * @return solver configuration
390     */
391    public DataProperties getProperties() {
392        return iProperties;
393    }
394
395    /**
396     * Empty online student sectioning infos for all sections (see
397     * {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}).
398     */
399    public void clearOnlineSectioningInfos() {
400        for (Offering offering : iOfferings) {
401            for (Config config : offering.getConfigs()) {
402                for (Subpart subpart : config.getSubparts()) {
403                    for (Section section : subpart.getSections()) {
404                        section.setSpaceExpected(0);
405                        section.setSpaceHeld(0);
406                    }
407                }
408            }
409        }
410    }
411
412    /**
413     * Compute online student sectioning infos for all sections (see
414     * {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}).
415     * @param assignment current assignment
416     */
417    public void computeOnlineSectioningInfos(Assignment<Request, Enrollment> assignment) {
418        clearOnlineSectioningInfos();
419        for (Student student : getStudents()) {
420            if (!student.isDummy())
421                continue;
422            for (Request request : student.getRequests()) {
423                if (!(request instanceof CourseRequest))
424                    continue;
425                CourseRequest courseRequest = (CourseRequest) request;
426                Enrollment enrollment = assignment.getValue(courseRequest);
427                if (enrollment != null) {
428                    for (Section section : enrollment.getSections()) {
429                        section.setSpaceHeld(courseRequest.getWeight() + section.getSpaceHeld());
430                    }
431                }
432                List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>();
433                int totalLimit = 0;
434                for (Enrollment enrl : courseRequest.values(assignment)) {
435                    boolean overlaps = false;
436                    for (Request otherRequest : student.getRequests()) {
437                        if (otherRequest.equals(courseRequest) || !(otherRequest instanceof CourseRequest))
438                            continue;
439                        Enrollment otherErollment = assignment.getValue(otherRequest);
440                        if (otherErollment == null)
441                            continue;
442                        if (enrl.isOverlapping(otherErollment)) {
443                            overlaps = true;
444                            break;
445                        }
446                    }
447                    if (!overlaps) {
448                        feasibleEnrollments.add(enrl);
449                        if (totalLimit >= 0) {
450                            int limit = enrl.getLimit();
451                            if (limit < 0) totalLimit = -1;
452                            else totalLimit += limit;
453                        }
454                    }
455                }
456                double increment = courseRequest.getWeight() / (totalLimit > 0 ? totalLimit : feasibleEnrollments.size());
457                for (Enrollment feasibleEnrollment : feasibleEnrollments) {
458                    for (Section section : feasibleEnrollment.getSections()) {
459                        if (totalLimit > 0) {
460                            section.setSpaceExpected(section.getSpaceExpected() + increment * feasibleEnrollment.getLimit());
461                        } else {
462                            section.setSpaceExpected(section.getSpaceExpected() + increment);
463                        }
464                    }
465                }
466            }
467        }
468    }
469
470    /**
471     * Sum of weights of all requests that are not assigned (see
472     * {@link Request#getWeight()}).
473     * @param assignment current assignment
474     * @return unassigned request weight
475     */
476    public double getUnassignedRequestWeight(Assignment<Request, Enrollment> assignment) {
477        double weight = 0.0;
478        for (Request request : assignment.unassignedVariables(this)) {
479            weight += request.getWeight();
480        }
481        return weight;
482    }
483
484    /**
485     * Sum of weights of all requests (see {@link Request#getWeight()}).
486     * @return total request weight
487     */
488    public double getTotalRequestWeight() {
489        double weight = 0.0;
490        for (Request request : variables()) {
491            weight += request.getWeight();
492        }
493        return weight;
494    }
495
496    /**
497     * Set distance conflict extension
498     * @param dc distance conflicts extension
499     */
500    public void setDistanceConflict(DistanceConflict dc) {
501        iDistanceConflict = dc;
502    }
503
504    /**
505     * Return distance conflict extension
506     * @return distance conflicts extension
507     */
508    public DistanceConflict getDistanceConflict() {
509        return iDistanceConflict;
510    }
511
512    /**
513     * Set time overlaps extension
514     * @param toc time overlapping conflicts extension
515     */
516    public void setTimeOverlaps(TimeOverlapsCounter toc) {
517        iTimeOverlaps = toc;
518    }
519
520    /**
521     * Return time overlaps extension
522     * @return time overlapping conflicts extension
523     */
524    public TimeOverlapsCounter getTimeOverlaps() {
525        return iTimeOverlaps;
526    }
527
528    /**
529     * Average priority of unassigned requests (see
530     * {@link Request#getPriority()})
531     * @param assignment current assignment
532     * @return average priority of unassigned requests
533     */
534    public double avgUnassignPriority(Assignment<Request, Enrollment> assignment) {
535        double totalPriority = 0.0;
536        for (Request request : assignment.unassignedVariables(this)) {
537            if (request.isAlternative())
538                continue;
539            totalPriority += request.getPriority();
540        }
541        return 1.0 + totalPriority / assignment.nrUnassignedVariables(this);
542    }
543
544    /**
545     * Average number of requests per student (see {@link Student#getRequests()}
546     * )
547     * @return average number of requests per student
548     */
549    public double avgNrRequests() {
550        double totalRequests = 0.0;
551        int totalStudents = 0;
552        for (Student student : getStudents()) {
553            if (student.nrRequests() == 0)
554                continue;
555            totalRequests += student.nrRequests();
556            totalStudents++;
557        }
558        return totalRequests / totalStudents;
559    }
560
561    /** Number of last like ({@link Student#isDummy()} equals true) students. 
562     * @param precise true if to be computed
563     * @return number of last like (projected) students
564     **/
565    public int getNrLastLikeStudents(boolean precise) {
566        if (!precise)
567            return iNrDummyStudents;
568        int nrLastLikeStudents = 0;
569        for (Student student : getStudents()) {
570            if (student.isDummy())
571                nrLastLikeStudents++;
572        }
573        return nrLastLikeStudents;
574    }
575
576    /** Number of real ({@link Student#isDummy()} equals false) students. 
577     * @param precise true if to be computed
578     * @return number of real students
579     **/
580    public int getNrRealStudents(boolean precise) {
581        if (!precise)
582            return getStudents().size() - iNrDummyStudents;
583        int nrRealStudents = 0;
584        for (Student student : getStudents()) {
585            if (!student.isDummy())
586                nrRealStudents++;
587        }
588        return nrRealStudents;
589    }
590
591    /**
592     * Number of last like ({@link Student#isDummy()} equals true) students with
593     * a complete schedule ({@link Student#isComplete(Assignment)} equals true).
594     * @param assignment current assignment
595     * @param precise true if to be computed
596     * @return number of last like (projected) students with a complete schedule
597     */
598    public int getNrCompleteLastLikeStudents(Assignment<Request, Enrollment> assignment, boolean precise) {
599        if (!precise)
600            return getContext(assignment).getNrCompleteLastLikeStudents();
601        int nrLastLikeStudents = 0;
602        for (Student student : getStudents()) {
603            if (student.isComplete(assignment) && student.isDummy())
604                nrLastLikeStudents++;
605        }
606        return nrLastLikeStudents;
607    }
608
609    /**
610     * Number of real ({@link Student#isDummy()} equals false) students with a
611     * complete schedule ({@link Student#isComplete(Assignment)} equals true).
612     * @param assignment current assignment
613     * @param precise true if to be computed
614     * @return number of real students with a complete schedule
615     */
616    public int getNrCompleteRealStudents(Assignment<Request, Enrollment> assignment, boolean precise) {
617        if (!precise)
618            return getContext(assignment).nrComplete() - getContext(assignment).getNrCompleteLastLikeStudents();
619        int nrRealStudents = 0;
620        for (Student student : getStudents()) {
621            if (student.isComplete(assignment) && !student.isDummy())
622                nrRealStudents++;
623        }
624        return nrRealStudents;
625    }
626
627    /**
628     * Number of requests from projected ({@link Student#isDummy()} equals true)
629     * students.
630     * @param precise true if to be computed
631     * @return number of requests from projected students 
632     */
633    public int getNrLastLikeRequests(boolean precise) {
634        if (!precise)
635            return iNrDummyRequests;
636        int nrLastLikeRequests = 0;
637        for (Request request : variables()) {
638            if (request.getStudent().isDummy())
639                nrLastLikeRequests++;
640        }
641        return nrLastLikeRequests;
642    }
643
644    /**
645     * Number of requests from real ({@link Student#isDummy()} equals false)
646     * students.
647     * @param precise true if to be computed
648     * @return number of requests from real students 
649     */
650    public int getNrRealRequests(boolean precise) {
651        if (!precise)
652            return variables().size() - iNrDummyRequests;
653        int nrRealRequests = 0;
654        for (Request request : variables()) {
655            if (!request.getStudent().isDummy())
656                nrRealRequests++;
657        }
658        return nrRealRequests;
659    }
660
661    /**
662     * Number of requests from projected ({@link Student#isDummy()} equals true)
663     * students that are assigned.
664     * @param assignment current assignment
665     * @param precise true if to be computed
666     * @return number of requests from projected students that are assigned
667     */
668    public int getNrAssignedLastLikeRequests(Assignment<Request, Enrollment> assignment, boolean precise) {
669        if (!precise)
670            return getContext(assignment).getNrAssignedLastLikeRequests();
671        int nrLastLikeRequests = 0;
672        for (Request request : assignment.assignedVariables()) {
673            if (request.getStudent().isDummy())
674                nrLastLikeRequests++;
675        }
676        return nrLastLikeRequests;
677    }
678
679    /**
680     * Number of requests from real ({@link Student#isDummy()} equals false)
681     * students that are assigned.
682     * @param assignment current assignment
683     * @param precise true if to be computed
684     * @return number of requests from real students that are assigned
685     */
686    public int getNrAssignedRealRequests(Assignment<Request, Enrollment> assignment, boolean precise) {
687        if (!precise)
688            return assignment.nrAssignedVariables() - getContext(assignment).getNrAssignedLastLikeRequests();
689        int nrRealRequests = 0;
690        for (Request request : assignment.assignedVariables()) {
691            if (!request.getStudent().isDummy())
692                nrRealRequests++;
693        }
694        return nrRealRequests;
695    }
696
697    /**
698     * Model extended info. Some more information (that is more expensive to
699     * compute) is added to an ordinary {@link Model#getInfo(Assignment)}.
700     */
701    @Override
702    public Map<String, String> getExtendedInfo(Assignment<Request, Enrollment> assignment) {
703        Map<String, String> info = getInfo(assignment);
704        /*
705        int nrLastLikeStudents = getNrLastLikeStudents(true);
706        if (nrLastLikeStudents != 0 && nrLastLikeStudents != getStudents().size()) {
707            int nrRealStudents = getStudents().size() - nrLastLikeStudents;
708            int nrLastLikeCompleteStudents = getNrCompleteLastLikeStudents(true);
709            int nrRealCompleteStudents = getCompleteStudents().size() - nrLastLikeCompleteStudents;
710            info.put("Projected students with complete schedule", sDecimalFormat.format(100.0
711                    * nrLastLikeCompleteStudents / nrLastLikeStudents)
712                    + "% (" + nrLastLikeCompleteStudents + "/" + nrLastLikeStudents + ")");
713            info.put("Real students with complete schedule", sDecimalFormat.format(100.0 * nrRealCompleteStudents
714                    / nrRealStudents)
715                    + "% (" + nrRealCompleteStudents + "/" + nrRealStudents + ")");
716            int nrLastLikeRequests = getNrLastLikeRequests(true);
717            int nrRealRequests = variables().size() - nrLastLikeRequests;
718            int nrLastLikeAssignedRequests = getNrAssignedLastLikeRequests(true);
719            int nrRealAssignedRequests = assignedVariables().size() - nrLastLikeAssignedRequests;
720            info.put("Projected assigned requests", sDecimalFormat.format(100.0 * nrLastLikeAssignedRequests
721                    / nrLastLikeRequests)
722                    + "% (" + nrLastLikeAssignedRequests + "/" + nrLastLikeRequests + ")");
723            info.put("Real assigned requests", sDecimalFormat.format(100.0 * nrRealAssignedRequests / nrRealRequests)
724                    + "% (" + nrRealAssignedRequests + "/" + nrRealRequests + ")");
725        }
726        */
727        // info.put("Average unassigned priority", sDecimalFormat.format(avgUnassignPriority()));
728        // info.put("Average number of requests", sDecimalFormat.format(avgNrRequests()));
729        
730        /*
731        double total = 0;
732        for (Request r: variables())
733            if (r.getAssignment() != null)
734                total += r.getWeight() * iStudentWeights.getWeight(r.getAssignment());
735        */
736        double dc = 0;
737        if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts(assignment) != 0) {
738            Set<DistanceConflict.Conflict> conf = getDistanceConflict().getAllConflicts(assignment);
739            for (DistanceConflict.Conflict c: conf)
740                dc += avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
741            if (!conf.isEmpty())
742                info.put("Student distance conflicts", conf.size() + " (weighted: " + sDecimalFormat.format(dc) + ")");
743        }
744        double toc = 0;
745        if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts(assignment) != 0) {
746            Set<TimeOverlapsCounter.Conflict> conf = getTimeOverlaps().getAllConflicts(assignment);
747            int share = 0;
748            for (TimeOverlapsCounter.Conflict c: conf) {
749                toc += c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
750                toc += c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
751                share += c.getShare();
752            }
753            if (toc != 0.0)
754                info.put("Time overlapping conflicts", share + " (average: " + sDecimalFormat.format(5.0 * share / getStudents().size()) + " min, weighted: " + sDoubleFormat.format(toc) + ")");
755        }
756        /*
757        info.put("Overall solution value", sDecimalFormat.format(total - dc - toc) + (dc == 0.0 && toc == 0.0 ? "" :
758            " (" + (dc != 0.0 ? "distance: " + sDecimalFormat.format(dc): "") + (dc != 0.0 && toc != 0.0 ? ", " : "") + 
759            (toc != 0.0 ? "overlap: " + sDecimalFormat.format(toc) : "") + ")")
760            );
761        */
762        
763        double disbWeight = 0;
764        int disbSections = 0;
765        int disb10Sections = 0;
766        int disb10Limit = getProperties().getPropertyInt("Info.ListDisbalancedSections", 0);
767        Set<String> disb10SectionList = (disb10Limit == 0 ? null : new TreeSet<String>()); 
768        for (Offering offering: getOfferings()) {
769            for (Config config: offering.getConfigs()) {
770                double enrl = config.getEnrollmentWeight(assignment, null);
771                for (Subpart subpart: config.getSubparts()) {
772                    if (subpart.getSections().size() <= 1) continue;
773                    if (subpart.getLimit() > 0) {
774                        // sections have limits -> desired size is section limit x (total enrollment / total limit)
775                        double ratio = enrl / subpart.getLimit();
776                        for (Section section: subpart.getSections()) {
777                            double desired = ratio * section.getLimit();
778                            disbWeight += Math.abs(section.getEnrollmentWeight(assignment, null) - desired);
779                            disbSections ++;
780                            if (Math.abs(desired - section.getEnrollmentWeight(assignment, null)) >= Math.max(1.0, 0.1 * section.getLimit())) {
781                                disb10Sections++;
782                                if (disb10SectionList != null)
783                                        disb10SectionList.add(section.getSubpart().getConfig().getOffering().getName() + " " + section.getSubpart().getName() + " " + section.getName()); 
784                            }
785                        }
786                    } else {
787                        // unlimited sections -> desired size is total enrollment / number of sections
788                        for (Section section: subpart.getSections()) {
789                            double desired = enrl / subpart.getSections().size();
790                            disbWeight += Math.abs(section.getEnrollmentWeight(assignment, null) - desired);
791                            disbSections ++;
792                            if (Math.abs(desired - section.getEnrollmentWeight(assignment, null)) >= Math.max(1.0, 0.1 * desired)) {
793                                disb10Sections++;
794                                if (disb10SectionList != null)
795                                        disb10SectionList.add(section.getSubpart().getConfig().getOffering().getName() + " " + section.getSubpart().getName() + " " + section.getName());
796                            }
797                        }
798                    }
799                }
800            }
801        }
802        if (disbSections != 0) {
803            double assignedCRWeight = getContext(assignment).getAssignedCourseRequestWeight();
804            info.put("Average disbalance", sDecimalFormat.format(disbWeight / disbSections) + " (" + sDecimalFormat.format(assignedCRWeight == 0 ? 0.0 : 100.0 * disbWeight / assignedCRWeight) + "%)");
805            String list = "";
806            if (disb10SectionList != null) {
807                int i = 0;
808                for (String section: disb10SectionList) {
809                    if (i == disb10Limit) {
810                        list += "<br>...";
811                        break;
812                    }
813                    list += "<br>" + section;
814                    i++;
815                }
816            }
817            info.put("Sections disbalanced by 10% or more", disb10Sections + " (" + sDecimalFormat.format(disbSections == 0 ? 0.0 : 100.0 * disb10Sections / disbSections) + "%)" + list);
818        }
819        return info;
820    }
821    
822    @Override
823    public void restoreBest(Assignment<Request, Enrollment> assignment) {
824        restoreBest(assignment, new Comparator<Request>() {
825            @Override
826            public int compare(Request r1, Request r2) {
827                Enrollment e1 = r1.getBestAssignment();
828                Enrollment e2 = r2.getBestAssignment();
829                // Reservations first
830                if (e1.getReservation() != null && e2.getReservation() == null) return -1;
831                if (e1.getReservation() == null && e2.getReservation() != null) return 1;
832                // Then assignment iteration (i.e., order in which assignments were made)
833                if (r1.getBestAssignmentIteration() != r2.getBestAssignmentIteration())
834                    return (r1.getBestAssignmentIteration() < r2.getBestAssignmentIteration() ? -1 : 1);
835                // Then student and priority
836                return r1.compareTo(r2);
837            }
838        });
839    }
840        
841    @Override
842    public String toString(Assignment<Request, Enrollment> assignment) {
843        return   (getNrRealStudents(false) > 0 ? "RRq:" + getNrAssignedRealRequests(assignment, false) + "/" + getNrRealRequests(false) + ", " : "")
844                + (getNrLastLikeStudents(false) > 0 ? "DRq:" + getNrAssignedLastLikeRequests(assignment, false) + "/" + getNrLastLikeRequests(false) + ", " : "")
845                + (getNrRealStudents(false) > 0 ? "RS:" + getNrCompleteRealStudents(assignment, false) + "/" + getNrRealStudents(false) + ", " : "")
846                + (getNrLastLikeStudents(false) > 0 ? "DS:" + getNrCompleteLastLikeStudents(assignment, false) + "/" + getNrLastLikeStudents(false) + ", " : "")
847                + "V:"
848                + sDecimalFormat.format(-getTotalValue(assignment))
849                + (getDistanceConflict() == null ? "" : ", DC:" + getDistanceConflict().getTotalNrConflicts(assignment))
850                + (getTimeOverlaps() == null ? "" : ", TOC:" + getTimeOverlaps().getTotalNrConflicts(assignment))
851                + ", %:" + sDecimalFormat.format(-100.0 * getTotalValue(assignment) / (getStudents().size() - iNrDummyStudents + 
852                        (iProjectedStudentWeight < 0.0 ? iNrDummyStudents * (iTotalDummyWeight / iNrDummyRequests) :iProjectedStudentWeight * iTotalDummyWeight)));
853
854    }
855    
856    /**
857     * Quadratic average of two weights.
858     * @param w1 first weight
859     * @param w2 second weight
860     * @return average of the two weights
861     */
862    public double avg(double w1, double w2) {
863        return Math.sqrt(w1 * w2);
864    }
865
866    /**
867     * Maximal domain size (i.e., number of enrollments of a course request), -1 if there is no limit.
868     * @return maximal domain size, -1 if unlimited
869     */
870    public int getMaxDomainSize() { return iMaxDomainSize; }
871
872    /**
873     * Maximal domain size (i.e., number of enrollments of a course request), -1 if there is no limit.
874     * @param maxDomainSize maximal domain size, -1 if unlimited
875     */
876    public void setMaxDomainSize(int maxDomainSize) { iMaxDomainSize = maxDomainSize; }
877    
878
879    @Override
880    public StudentSectioningModelContext createAssignmentContext(Assignment<Request, Enrollment> assignment) {
881        return new StudentSectioningModelContext(assignment);
882    }
883    
884    public class StudentSectioningModelContext implements AssignmentConstraintContext<Request, Enrollment>, InfoProvider<Request, Enrollment>{
885        private Set<Student> iCompleteStudents = new HashSet<Student>();
886        private double iTotalValue = 0.0;
887        private int iNrAssignedDummyRequests = 0, iNrCompleteDummyStudents = 0;
888        private double iAssignedCRWeight = 0.0, iAssignedDummyCRWeight = 0.0;
889        private double iReservedSpace = 0.0;
890
891        public StudentSectioningModelContext(Assignment<Request, Enrollment> assignment) {
892            for (Request request: variables()) {
893                Enrollment enrollment = assignment.getValue(request);
894                if (enrollment != null)
895                    assigned(assignment, enrollment);
896            }
897        }
898
899        /**
900         * Called after an enrollment was assigned to a request. The list of
901         * complete students and the overall solution value are updated.
902         */
903        @Override
904        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
905            Student student = enrollment.getStudent();
906            if (student.isComplete(assignment))
907                iCompleteStudents.add(student);
908            double value = enrollment.getRequest().getWeight() * iStudentWeights.getWeight(assignment, enrollment);
909            iTotalValue -= value;
910            enrollment.variable().getContext(assignment).setLastWeight(value);
911            if (enrollment.isCourseRequest())
912                iAssignedCRWeight += enrollment.getRequest().getWeight();
913            if (enrollment.getReservation() != null)
914                iReservedSpace += enrollment.getRequest().getWeight();
915            if (enrollment.isCourseRequest() && ((CourseRequest)enrollment.getRequest()).hasReservations())
916                iTotalReservedSpace += enrollment.getRequest().getWeight();
917            if (student.isDummy()) {
918                iNrAssignedDummyRequests++;
919                if (enrollment.isCourseRequest())
920                    iAssignedDummyCRWeight += enrollment.getRequest().getWeight();
921                if (student.isComplete(assignment))
922                    iNrCompleteDummyStudents++;
923            }
924        }
925
926        /**
927         * Called before an enrollment was unassigned from a request. The list of
928         * complete students and the overall solution value are updated.
929         */
930        @Override
931        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
932            Student student = enrollment.getStudent();
933            if (iCompleteStudents.contains(student) && !student.isComplete(assignment)) {
934                iCompleteStudents.remove(student);
935                if (student.isDummy())
936                    iNrCompleteDummyStudents--;
937            }
938            Request.RequestContext cx = enrollment.variable().getContext(assignment);
939            Double value = cx.getLastWeight();
940            if (value == null)
941                value = enrollment.getRequest().getWeight() * iStudentWeights.getWeight(assignment, enrollment);
942            iTotalValue += value;
943            cx.setLastWeight(null);
944            if (enrollment.isCourseRequest())
945                iAssignedCRWeight -= enrollment.getRequest().getWeight();
946            if (enrollment.getReservation() != null)
947                iReservedSpace -= enrollment.getRequest().getWeight();
948            if (enrollment.isCourseRequest() && ((CourseRequest)enrollment.getRequest()).hasReservations())
949                iTotalReservedSpace -= enrollment.getRequest().getWeight();
950            if (student.isDummy()) {
951                iNrAssignedDummyRequests--;
952                if (enrollment.isCourseRequest())
953                    iAssignedDummyCRWeight -= enrollment.getRequest().getWeight();
954            }
955        }
956        
957        public void add(Assignment<Request, Enrollment> assignment, DistanceConflict.Conflict c) {
958            iTotalValue += avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
959        }
960
961        public void remove(Assignment<Request, Enrollment> assignment, DistanceConflict.Conflict c) {
962            iTotalValue -= avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
963        }
964        
965        public void add(Assignment<Request, Enrollment> assignment, TimeOverlapsCounter.Conflict c) {
966            iTotalValue += c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
967            iTotalValue += c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
968        }
969
970        public void remove(Assignment<Request, Enrollment> assignment, TimeOverlapsCounter.Conflict c) {
971            iTotalValue -= c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
972            iTotalValue -= c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
973        }
974        
975        /**
976         * Students with complete schedules (see {@link Student#isComplete(Assignment)})
977         * @return students with complete schedule
978         */
979        public Set<Student> getCompleteStudents() {
980            return iCompleteStudents;
981        }
982        
983        /**
984         * Number of students with complete schedule
985         * @return number of students with complete schedule
986         */
987        public int nrComplete() {
988            return getCompleteStudents().size();
989        }
990        
991        /** 
992         * Recompute cached request weights
993         * @param assignment curent assignment
994         */
995        public void requestWeightsChanged(Assignment<Request, Enrollment> assignment) {
996            iTotalCRWeight = 0.0;
997            iTotalDummyWeight = 0.0; iTotalDummyCRWeight = 0.0;
998            iAssignedCRWeight = 0.0;
999            iAssignedDummyCRWeight = 0.0;
1000            iNrDummyRequests = 0; iNrAssignedDummyRequests = 0;
1001            iTotalReservedSpace = 0.0; iReservedSpace = 0.0;
1002            for (Request request: variables()) {
1003                boolean cr = (request instanceof CourseRequest);
1004                if (cr)
1005                    iTotalCRWeight += request.getWeight();
1006                if (request.getStudent().isDummy()) {
1007                    iTotalDummyWeight += request.getWeight();
1008                    iNrDummyRequests ++;
1009                    if (cr)
1010                        iTotalDummyCRWeight += request.getWeight();
1011                }
1012                if (assignment.getValue(request) != null) {
1013                    if (cr)
1014                        iAssignedCRWeight += request.getWeight();
1015                    if (assignment.getValue(request).getReservation() != null)
1016                        iReservedSpace += request.getWeight();
1017                    if (cr && ((CourseRequest)request).hasReservations())
1018                        iTotalReservedSpace += request.getWeight();
1019                    if (request.getStudent().isDummy()) {
1020                        iNrAssignedDummyRequests ++;
1021                        if (cr)
1022                            iAssignedDummyCRWeight += request.getWeight();
1023                    }
1024                }
1025            }
1026        }
1027        
1028        /**
1029         * Overall solution value
1030         * @return solution value
1031         */
1032        public double getTotalValue() {
1033            return iTotalValue;
1034        }
1035        
1036        /**
1037         * Number of last like ({@link Student#isDummy()} equals true) students with
1038         * a complete schedule ({@link Student#isComplete(Assignment)} equals true).
1039         * @return number of last like (projected) students with a complete schedule
1040         */
1041        public int getNrCompleteLastLikeStudents() {
1042            return iNrCompleteDummyStudents;
1043        }
1044        
1045        /**
1046         * Number of requests from projected ({@link Student#isDummy()} equals true)
1047         * students that are assigned.
1048         * @return number of real students with a complete schedule
1049         */
1050        public int getNrAssignedLastLikeRequests() {
1051            return iNrAssignedDummyRequests;
1052        }
1053
1054        @Override
1055        public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
1056            if (iTotalCRWeight > 0.0) {
1057                info.put("Assigned course requests", sDecimalFormat.format(100.0 * iAssignedCRWeight / iTotalCRWeight) + "% (" + (int)Math.round(iAssignedCRWeight) + "/" + (int)Math.round(iTotalCRWeight) + ")");
1058                if (getNrLastLikeStudents(false) != getStudents().size() && iTotalCRWeight != iTotalDummyCRWeight) {
1059                    if (iTotalDummyCRWeight > 0.0)
1060                        info.put("Projected assigned course requests", sDecimalFormat.format(100.0 * iAssignedDummyCRWeight / iTotalDummyCRWeight) + "% (" + (int)Math.round(iAssignedDummyCRWeight) + "/" + (int)Math.round(iTotalDummyCRWeight) + ")");
1061                    info.put("Real assigned course requests", sDecimalFormat.format(100.0 * (iAssignedCRWeight - iAssignedDummyCRWeight) / (iTotalCRWeight - iTotalDummyCRWeight)) +
1062                            "% (" + (int)Math.round(iAssignedCRWeight - iAssignedDummyCRWeight) + "/" + (int)Math.round(iTotalCRWeight - iTotalDummyCRWeight) + ")");
1063                }
1064            }
1065            if (iTotalReservedSpace > 0.0)
1066                info.put("Reservations", sDoubleFormat.format(100.0 * iReservedSpace / iTotalReservedSpace) + "% (" + Math.round(iReservedSpace) + "/" + Math.round(iTotalReservedSpace) + ")"); 
1067        }
1068
1069        @Override
1070        public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
1071        }
1072        
1073        public double getAssignedCourseRequestWeight() {
1074            return iAssignedCRWeight;
1075        }
1076    }
1077    
1078    @Override
1079    public InheritedAssignment<Request, Enrollment> createInheritedAssignment(Solution<Request, Enrollment> solution, int index) {
1080        return new OptimisticInheritedAssignment<Request, Enrollment>(solution, index);
1081    }
1082
1083}