001package net.sf.cpsolver.studentsct.heuristics.selection;
002
003import java.text.DecimalFormat;
004import java.util.Iterator;
005import java.util.List;
006
007import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
008import net.sf.cpsolver.ifs.model.Neighbour;
009import net.sf.cpsolver.ifs.solution.Solution;
010import net.sf.cpsolver.ifs.solver.Solver;
011import net.sf.cpsolver.ifs.util.DataProperties;
012import net.sf.cpsolver.ifs.util.Progress;
013import net.sf.cpsolver.studentsct.StudentSectioningModel;
014import net.sf.cpsolver.studentsct.heuristics.selection.BranchBoundSelection.BranchBoundNeighbour;
015import net.sf.cpsolver.studentsct.heuristics.studentord.StudentChoiceRealFirstOrder;
016import net.sf.cpsolver.studentsct.heuristics.studentord.StudentOrder;
017import net.sf.cpsolver.studentsct.model.Enrollment;
018import net.sf.cpsolver.studentsct.model.Request;
019import 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 Tomáš Müller<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
052public 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}