001    package net.sf.cpsolver.studentsct.heuristics.selection;
002    
003    import java.text.DecimalFormat;
004    import java.util.Iterator;
005    import java.util.List;
006    
007    import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
008    import net.sf.cpsolver.ifs.model.Neighbour;
009    import net.sf.cpsolver.ifs.solution.Solution;
010    import net.sf.cpsolver.ifs.solver.Solver;
011    import net.sf.cpsolver.ifs.util.DataProperties;
012    import net.sf.cpsolver.ifs.util.Progress;
013    import net.sf.cpsolver.studentsct.StudentSectioningModel;
014    import net.sf.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour;
015    import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
016    import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
017    import net.sf.cpsolver.studentsct.model.Enrollment;
018    import net.sf.cpsolver.studentsct.model.Request;
019    import net.sf.cpsolver.studentsct.model.Student;
020    
021    /**
022     * This selection is very much like {@link BranchBoundSelection}, but it works in cycles
023     * (over all the students) assigning only the first N priority courses. It starts with
024     * N = 1 and increases it by one after each cycle. The selection ends when no student can 
025     * get more requests assigned in a whole cycle. Run the selection only once (at the 
026     * beginning), the selection falls back to {@link BranchBoundSelection} if there are already
027     * some requests assigned at the time of initialization.
028     * 
029     * <br>
030     * <br>
031     * 
032     * @version StudentSct 1.2 (Student Sectioning)<br>
033     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
034     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
035     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
036     * <br>
037     *          This library is free software; you can redistribute it and/or modify
038     *          it under the terms of the GNU Lesser General Public License as
039     *          published by the Free Software Foundation; either version 3 of the
040     *          License, or (at your option) any later version. <br>
041     * <br>
042     *          This library is distributed in the hope that it will be useful, but
043     *          WITHOUT ANY WARRANTY; without even the implied warranty of
044     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
045     *          Lesser General Public License for more details. <br>
046     * <br>
047     *          You should have received a copy of the GNU Lesser General Public
048     *          License along with this library; if not see
049     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
050     */
051    
052    public class PriorityConstructionSelection implements NeighbourSelection<Request, Enrollment> {
053        private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(PriorityConstructionSelection.class);
054        private static DecimalFormat sDF = new DecimalFormat("0.00");
055        private int iCycle = 0;
056        private int iMaxCycles = 7;
057        private boolean iImproved = false;
058        private boolean iSkip = false;
059        private BranchBoundSelection iBranchBoundSelection = null;
060        protected Iterator<Student> iStudentsEnumeration = null;
061        protected StudentOrder iOrder = new StudentChoiceRealFirstOrder();
062        protected List<Student> iStudents = null;
063    
064        /**
065         * Constructor
066         * 
067         * @param properties
068         *            configuration
069         */
070        public PriorityConstructionSelection(DataProperties properties) {
071            iBranchBoundSelection = new BranchBoundSelection(properties);
072            if (properties.getProperty("Neighbour.PriorityConstructionOrder") != null) {
073                try {
074                    iOrder = (StudentOrder) Class.forName(properties.getProperty("Neighbour.PriorityConstructionOrder"))
075                            .getConstructor(new Class[] { DataProperties.class }).newInstance(new Object[] { properties });
076                } catch (Exception e) {
077                    sLog.error("Unable to set student order, reason:" + e.getMessage(), e);
078                }
079            }
080            iMaxCycles = properties.getPropertyInteger("Neighbour.PriorityConstructionCycles", iMaxCycles);
081        }
082        
083        /**
084         * Initialize
085         */
086        @Override
087        public void init(Solver<Request, Enrollment> solver) {
088            iCycle = 1;
089            iImproved = false;
090            iSkip = !solver.currentSolution().getModel().assignedVariables().isEmpty();
091            if (iSkip) {
092                iBranchBoundSelection.init(solver);
093            } else {
094                iStudents = iOrder.order(((StudentSectioningModel) solver.currentSolution().getModel()).getStudents());
095                iStudentsEnumeration = iStudents.iterator();
096                iBranchBoundSelection.init(solver, "Construction[" + iCycle + "]...");
097            }
098        }
099        
100        /**
101         * Find best solution for the next student using {@link BranchBoundSelection}.
102         */
103        public Neighbour<Request, Enrollment> branchAndBound(Solution<Request, Enrollment> solution) {
104            while (iStudentsEnumeration.hasNext()) {
105                Student student = iStudentsEnumeration.next();
106                Progress.getInstance(solution.getModel()).incProgress();
107                /*
108                if (student.nrRequests() < iCycle) {
109                    // not enough requests -> nothing to improve -> skip
110                    continue;
111                }
112                if (student.nrAssignedRequests() + 1 < iCycle) {
113                    // previous step cycle already did not improve the assignment -> skip
114                    continue;
115                }
116                */
117                Neighbour<Request, Enrollment> neighbour = iBranchBoundSelection.getSelection(student).select();
118                if (neighbour != null)
119                    return neighbour;
120            }
121            return null;
122        }
123        
124        /** Increment cycle */
125        protected void nextCycle(Solution<Request, Enrollment> solution) {
126            iCycle ++; iImproved = false;
127            sLog.debug("Assigning up to " + iCycle + " requests...");
128            
129            StudentSectioningModel m = (StudentSectioningModel)solution.getModel();
130            double tv = m.getTotalValue(true);
131            sLog.debug("**CURR** " + solution.getModel().toString() + ", TM:" + sDF.format(solution.getTime() / 3600.0) + "h, " + 
132                    "TV:" + sDF.format(-tv) + " (" + sDF.format(-100.0 * tv / m.getStudents().size()) + "%)");
133            
134            iStudentsEnumeration = iStudents.iterator();
135            Progress.getInstance(solution.getModel()).setPhase("Construction[" + iCycle + "]...", iStudents.size());
136        }
137    
138        /**
139         * Select neighbor. All students are taken, one by one in a random order.
140         * For each student a branch & bound search is employed.
141         */
142        @Override
143        public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) {
144            if (iSkip)
145                return iBranchBoundSelection.selectNeighbour(solution);
146            Neighbour<Request, Enrollment> n = branchAndBound(solution);
147            if (n == null) {
148                if (iCycle == iMaxCycles || !iImproved) return null;
149                nextCycle(solution);
150                n = branchAndBound(solution);
151            }
152            return (n == null ? null : new ConstructionNeighbour((BranchBoundNeighbour)n));
153            
154        }
155        
156        /**
157         * Takes {@link BranchBoundNeighbour} but only assign the given
158         * number of assignments, corresponding to the number of cycles.
159         */
160        public class ConstructionNeighbour extends Neighbour<Request, Enrollment>{
161            private BranchBoundNeighbour iNeighbour;
162            
163            public ConstructionNeighbour(BranchBoundNeighbour neighbour) {
164                iNeighbour = neighbour;
165            }
166    
167            /**
168             * Only assign given number of assignments (from the first priority down).
169             * Mark the cycle as improving if there was enough assignments to do.
170             */
171            @Override
172            public void assign(long iteration) {
173                if (iCycle >= iMaxCycles) {
174                    iNeighbour.assign(iteration);
175                    return;
176                }
177                for (Request r: iNeighbour.getStudent().getRequests())
178                    if (r.getAssignment() != null) r.unassign(iteration);
179                int n = iCycle;
180                for (int i = 0; i < iNeighbour.getAssignment().length; i++) {
181                    if (iNeighbour.getAssignment()[i] != null) {
182                        iNeighbour.getAssignment()[i].variable().assign(iteration, iNeighbour.getAssignment()[i]);
183                        n --;
184                    }
185                    if (n == 0) {
186                        iImproved = true; break;
187                    }
188                }
189            }
190    
191            @Override
192            public double value() {
193                return iNeighbour.value();
194            }
195            
196            @Override
197            public String toString() {
198                int n = iCycle;
199                StringBuffer sb = new StringBuffer("B&B[" + n + "]{ " + 
200                        iNeighbour.getStudent() + " " + sDF.format(-value() * 100.0) + "%");
201                int idx = 0;
202                for (Iterator<Request> e = iNeighbour.getStudent().getRequests().iterator(); e.hasNext(); idx++) {
203                    Request request = e.next();
204                    sb.append("\n  " + request);
205                    Enrollment enrollment = iNeighbour.getAssignment()[idx];
206                    if (enrollment == null) {
207                        sb.append("  -- not assigned");
208                    } else {
209                        sb.append("  -- " + enrollment);
210                        n --;
211                    }
212                    if (n == 0) break;
213                }
214                sb.append("\n}");
215                return sb.toString();
216            }
217        }
218    
219        
220    }