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