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}