001package org.cpsolver.exam.heuristics;
002
003import java.util.Collections;
004import java.util.HashSet;
005import java.util.Set;
006
007import org.cpsolver.exam.model.Exam;
008import org.cpsolver.exam.model.ExamModel;
009import org.cpsolver.exam.model.ExamPeriodPlacement;
010import org.cpsolver.exam.model.ExamPlacement;
011import org.cpsolver.exam.model.ExamRoomPlacement;
012import org.cpsolver.exam.neighbours.ExamSimpleNeighbour;
013import org.cpsolver.ifs.assignment.Assignment;
014import org.cpsolver.ifs.assignment.context.AssignmentContext;
015import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
016import org.cpsolver.ifs.model.Neighbour;
017import org.cpsolver.ifs.solution.Solution;
018import org.cpsolver.ifs.solver.Solver;
019import org.cpsolver.ifs.util.DataProperties;
020import org.cpsolver.ifs.util.Progress;
021
022
023/**
024 * Initial solution construction heuristics. <br>
025 * <br>
026 * While there are exams that are still not assigned:
027 * <ul>
028 * <li>The worst unassigned exam is selected (using {@link Exam#compareTo(Exam)})
029 * <li>The best period that does not break any hard constraint and for which
030 * there is a room assignment available is selected together with the set the
031 * best available rooms for the exam in the best period (computed using
032 * {@link Exam#findBestAvailableRooms(Assignment, ExamPeriodPlacement)}).
033 * </ul>
034 * <br>
035 * <br>
036 * If problem property ExamConstruction.CheckLocalOptimality is true, local
037 * (time) optimality is enforced at the end of this phase. During this
038 * procedure, for each exam, it tries to change the period of the exam so that
039 * the time cost is lower (see {@link ExamPlacement#getTimeCost(Assignment)}), but no hard
040 * constraint is violated. The problem is considered locally optimal if there is
041 * no such move. <br>
042 * <br>
043 * 
044 * @version ExamTT 1.3 (Examination Timetabling)<br>
045 *          Copyright (C) 2008 - 2014 Tomas Muller<br>
046 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
047 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
048 * <br>
049 *          This library is free software; you can redistribute it and/or modify
050 *          it under the terms of the GNU Lesser General Public License as
051 *          published by the Free Software Foundation; either version 3 of the
052 *          License, or (at your option) any later version. <br>
053 * <br>
054 *          This library is distributed in the hope that it will be useful, but
055 *          WITHOUT ANY WARRANTY; without even the implied warranty of
056 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
057 *          Lesser General Public License for more details. <br>
058 * <br>
059 *          You should have received a copy of the GNU Lesser General Public
060 *          License along with this library; if not see
061 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
062 */
063public class ExamConstruction extends NeighbourSelectionWithContext<Exam, ExamPlacement, ExamConstruction.Context> {
064    private boolean iCheckLocalOptimality = false;
065    private Progress iProgress = null;
066    private boolean iActive = false;
067
068    /**
069     * Constructor
070     * 
071     * @param properties
072     *            problem properties
073     */
074    public ExamConstruction(DataProperties properties) {
075        iCheckLocalOptimality = properties.getPropertyBoolean("ExamConstruction.CheckLocalOptimality", iCheckLocalOptimality);
076    }
077
078    /**
079     * Initialization
080     */
081    @Override
082    public void init(Solver<Exam, ExamPlacement> solver) {
083        super.init(solver);
084        // solver.setUpdateProgress(false);
085        iProgress = Progress.getInstance(solver.currentSolution().getModel());
086        iActive = false;
087    }
088
089    /**
090     * Find a new assignment of one of the assigned exams that improves the time
091     * cost {@link ExamPlacement#getTimeCost(Assignment)} and for which there is a set of
092     * available rooms {@link Exam#findBestAvailableRooms(Assignment, ExamPeriodPlacement)}.
093     * Return null, if there is no such assignment (the problem is considered
094     * locally optimal).
095     * @param assignment current assignment
096     * @param model problem model
097     * @return a neighbour to assign or null if none was found
098     */
099    public Neighbour<Exam, ExamPlacement> checkLocalOptimality(Assignment<Exam, ExamPlacement> assignment, ExamModel model) {
100        if (iCheckLocalOptimality) {
101            Context context = getContext(assignment); 
102            for (Exam exam : assignment.assignedVariables()) {
103                ExamPlacement current = assignment.getValue(exam);
104                if (current.getTimeCost(assignment) <= 0)
105                    continue;
106                ExamPlacement best = null;
107                for (ExamPeriodPlacement period : exam.getPeriodPlacements()) {
108                    if (exam.countStudentConflicts(assignment, period) > 0) {
109                        if (context.assignments().contains(exam.getId() + ":" + period.getIndex()))
110                            continue;
111                    }
112                    if (!exam.checkDistributionConstraints(assignment, period))
113                        continue;
114                    ExamPlacement placement = new ExamPlacement(exam, period, null);
115                    if (best == null || best.getTimeCost(assignment) > placement.getTimeCost(assignment)) {
116                        Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(assignment, period);
117                        if (rooms != null)
118                            best = new ExamPlacement(exam, period, rooms);
119                    }
120                }
121                if (best != null && best.getTimeCost(assignment) < current.getTimeCost(assignment))
122                    return new ExamSimpleNeighbour(assignment, best);
123            }
124        }
125        iActive = false;
126        return null;
127    }
128
129    /**
130     * Select a neighbour. While there are exams that are still not assigned:
131     * <ul>
132     * <li>The worst unassigned exam is selected (using
133     * {@link Exam#compareTo(Exam)})
134     * <li>The best period that does not break any hard constraint and for which
135     * there is a room assignment available is selected together with the set
136     * the best available rooms for the exam in the best period (computed using
137     * {@link Exam#findBestAvailableRooms(Assignment, ExamPeriodPlacement)}).
138     * </ul>
139     * Return null when done (all variables are assigned and the problem is
140     * locally optimal).
141     */
142    @Override
143    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
144        ExamModel model = (ExamModel) solution.getModel();
145        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
146        Context context = getContext(assignment);
147        if (!iActive) {
148            iActive = true;
149            // iProgress.setPhase("Construction ...", model.variables().size());
150            iProgress.info("[" + Thread.currentThread().getName() + "] Construction ...");
151        }
152        // iProgress.setProgress(assignment.nrAssignedVariables());
153        if (model.variables().size() - assignment.nrAssignedVariables() <= context.skip().size())
154            return checkLocalOptimality(assignment, model);
155        Exam bestExam = null;
156        for (Exam exam : model.variables()) {
157            if (assignment.getValue(exam) != null || context.skip().contains(exam))
158                continue;
159            if (bestExam == null || exam.compareTo(bestExam) < 0)
160                bestExam = exam;
161        }
162        ExamPlacement best = null;
163        for (ExamPeriodPlacement period : bestExam.getPeriodPlacements()) {
164            if (bestExam.countStudentConflicts(assignment, period) > 0) {
165                if (context.assignments().contains(bestExam.getId() + ":" + period.getIndex()))
166                    continue;
167            }
168            if (!bestExam.checkDistributionConstraints(assignment, period))
169                continue;
170            ExamPlacement placement = new ExamPlacement(bestExam, period, null);
171            if (best == null || best.getTimeCost(assignment) > placement.getTimeCost(assignment)) {
172                Set<ExamRoomPlacement> rooms = bestExam.findBestAvailableRooms(assignment, period);
173                if (rooms != null)
174                    best = new ExamPlacement(bestExam, period, rooms);
175            }
176        }
177        if (best != null) {
178            context.assignments().add(bestExam.getId() + ":" + best.getPeriod().getIndex());
179            return new ExamSimpleNeighbour(assignment, best);
180        } /*
181           * else { for (Enumeration
182           * e=bestExam.getPeriodPlacements().elements();e.hasMoreElements();) {
183           * ExamPeriodPlacement period = (ExamPeriodPlacement)e.nextElement();
184           * ExamPlacement placement = new ExamPlacement(bestExam, period,
185           * null); if (best==null ||
186           * best.getTimeCost()>placement.getTimeCost()) { Set rooms =
187           * bestExam.findBestAvailableRooms(period); if (rooms!=null) best =
188           * new ExamPlacement(bestExam, period, rooms); } } if (best!=null) {
189           * bestExam.allowAllStudentConflicts(best.getPeriod());
190           * iAssignments.add(bestExam.getId()+":"+best.getPeriod().getIndex());
191           * return new ExamSimpleNeighbour(best); } }
192           */
193        if (!context.skip().contains(bestExam)) {
194            context.skip().add(bestExam);
195            return selectNeighbour(solution);
196        }
197        return checkLocalOptimality(assignment, model);
198    }
199    
200    @Override
201    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
202        return new Context();
203    }
204
205    public class Context implements AssignmentContext {
206        private Set<String> iAssignments = Collections.synchronizedSet(new HashSet<String>());
207        private Set<Exam> iSkip = Collections.synchronizedSet(new HashSet<Exam>());
208        
209        public Set<Exam> skip() { return iSkip; }
210        
211        public Set<String> assignments() { return iAssignments; }
212    }
213}