    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}