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 Tomáš Müller<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.countInstructorConflicts(assignment, period) > 0) {
113                        if (context.assignments().contains(exam.getId() + ":" + period.getIndex()))
114                            continue;
115                    }
116                    if (!exam.checkDistributionConstraints(assignment, period))
117                        continue;
118                    ExamPlacement placement = new ExamPlacement(exam, period, null);
119                    if (best == null || best.getTimeCost(assignment) > placement.getTimeCost(assignment)) {
120                        Set<ExamRoomPlacement> rooms = exam.findBestAvailableRooms(assignment, period);
121                        if (rooms != null)
122                            best = new ExamPlacement(exam, period, rooms);
123                    }
124                }
125                if (best != null && best.getTimeCost(assignment) < current.getTimeCost(assignment))
126                    return new ExamSimpleNeighbour(assignment, best);
127            }
128        }
129        iActive = false;
130        return null;
131    }
132
133    /**
134     * Select a neighbour. While there are exams that are still not assigned:
135     * <ul>
136     * <li>The worst unassigned exam is selected (using
137     * {@link Exam#compareTo(Exam)})
138     * <li>The best period that does not break any hard constraint and for which
139     * there is a room assignment available is selected together with the set
140     * the best available rooms for the exam in the best period (computed using
141     * {@link Exam#findBestAvailableRooms(Assignment, ExamPeriodPlacement)}).
142     * </ul>
143     * Return null when done (all variables are assigned and the problem is
144     * locally optimal).
145     */
146    @Override
147    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
148        ExamModel model = (ExamModel) solution.getModel();
149        Assignment<Exam, ExamPlacement> assignment = solution.getAssignment();
150        Context context = getContext(assignment);
151        if (!iActive) {
152            iActive = true;
153            // iProgress.setPhase("Construction ...", model.variables().size());
154            iProgress.info("[" + Thread.currentThread().getName() + "] Construction ...");
155        }
156        // iProgress.setProgress(assignment.nrAssignedVariables());
157        if (model.variables().size() - assignment.nrAssignedVariables() <= context.skip().size())
158            return checkLocalOptimality(assignment, model);
159        Exam bestExam = null;
160        for (Exam exam : model.variables()) {
161            if (assignment.getValue(exam) != null || context.skip().contains(exam))
162                continue;
163            if (bestExam == null || exam.compareTo(bestExam) < 0)
164                bestExam = exam;
165        }
166        ExamPlacement best = null;
167        for (ExamPeriodPlacement period : bestExam.getPeriodPlacements()) {
168            if (bestExam.countStudentConflicts(assignment, period) > 0) {
169                if (context.assignments().contains(bestExam.getId() + ":" + period.getIndex()))
170                    continue;
171            }
172            if (bestExam.countInstructorConflicts(assignment, period) > 0) {
173                if (context.assignments().contains(bestExam.getId() + ":" + period.getIndex()))
174                    continue;
175            }
176            if (!bestExam.checkDistributionConstraints(assignment, period))
177                continue;
178            ExamPlacement placement = new ExamPlacement(bestExam, period, null);
179            if (best == null || best.getTimeCost(assignment) > placement.getTimeCost(assignment)) {
180                Set<ExamRoomPlacement> rooms = bestExam.findBestAvailableRooms(assignment, period);
181                if (rooms != null)
182                    best = new ExamPlacement(bestExam, period, rooms);
183            }
184        }
185        if (best != null) {
186            context.assignments().add(bestExam.getId() + ":" + best.getPeriod().getIndex());
187            return new ExamSimpleNeighbour(assignment, best);
188        } /*
189           * else { for (Enumeration
190           * e=bestExam.getPeriodPlacements().elements();e.hasMoreElements();) {
191           * ExamPeriodPlacement period = (ExamPeriodPlacement)e.nextElement();
192           * ExamPlacement placement = new ExamPlacement(bestExam, period,
193           * null); if (best==null ||
194           * best.getTimeCost()>placement.getTimeCost()) { Set rooms =
195           * bestExam.findBestAvailableRooms(period); if (rooms!=null) best =
196           * new ExamPlacement(bestExam, period, rooms); } } if (best!=null) {
197           * bestExam.allowAllStudentConflicts(best.getPeriod());
198           * iAssignments.add(bestExam.getId()+":"+best.getPeriod().getIndex());
199           * return new ExamSimpleNeighbour(best); } }
200           */
201        if (!context.skip().contains(bestExam)) {
202            context.skip().add(bestExam);
203            return selectNeighbour(solution);
204        }
205        return checkLocalOptimality(assignment, model);
206    }
207    
208    @Override
209    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
210        return new Context();
211    }
212
213    public class Context implements AssignmentContext {
214        private Set<String> iAssignments = Collections.synchronizedSet(new HashSet<String>());
215        private Set<Exam> iSkip = Collections.synchronizedSet(new HashSet<Exam>());
216        
217        public Set<Exam> skip() { return iSkip; }
218        
219        public Set<String> assignments() { return iAssignments; }
220    }
221}