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