    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}