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 }