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