    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.log4j.Logger sLog = org.apache.log4j.Logger.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}