001package org.cpsolver.studentsct.heuristics.selection; 002 003import org.cpsolver.ifs.assignment.Assignment; 004import org.cpsolver.ifs.model.Neighbour; 005import org.cpsolver.ifs.solution.Solution; 006import org.cpsolver.ifs.solver.Solver; 007import org.cpsolver.ifs.util.DataProperties; 008import org.cpsolver.ifs.util.JProf; 009import org.cpsolver.ifs.util.Progress; 010import org.cpsolver.studentsct.model.Enrollment; 011import org.cpsolver.studentsct.model.Request; 012import org.cpsolver.studentsct.model.Student; 013 014/** 015 * Assign initial enrollments. An extension of {@link BranchBoundSelection}, 016 * where only initial enrollments (see {@link Request#getInitialAssignment()}) can 017 * be assigned. Students that already has a schedule 018 * ({@link Student#nrAssignedRequests(Assignment)} is greater then zero) are ignored. 019 * 020 * <br> 021 * <br> 022 * 023 * @version StudentSct 1.3 (Student Sectioning)<br> 024 * Copyright (C) 2007 - 2015 Tomáš Müller<br> 025 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 026 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 027 * <br> 028 * This library is free software; you can redistribute it and/or modify 029 * it under the terms of the GNU Lesser General Public License as 030 * published by the Free Software Foundation; either version 3 of the 031 * License, or (at your option) any later version. <br> 032 * <br> 033 * This library is distributed in the hope that it will be useful, but 034 * WITHOUT ANY WARRANTY; without even the implied warranty of 035 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 036 * Lesser General Public License for more details. <br> 037 * <br> 038 * You should have received a copy of the GNU Lesser General Public 039 * License along with this library; if not see 040 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 041 */ 042public class AssignInitialSelection extends BranchBoundSelection { 043 044 public AssignInitialSelection(DataProperties properties) { 045 super(properties); 046 } 047 048 @Override 049 public void init(Solver<Request, Enrollment> solver) { 050 init(solver, "Assign initial enrollments..."); 051 } 052 053 @Override 054 public Neighbour<Request, Enrollment> selectNeighbour(Solution<Request, Enrollment> solution) { 055 Student student = null; 056 while ((student = nextStudent()) != null) { 057 Progress.getInstance(solution.getModel()).incProgress(); 058 if (student.nrAssignedRequests(solution.getAssignment()) > 0) continue; 059 Neighbour<Request, Enrollment> neighbour = new InitialSelection(student, solution.getAssignment()).select(); 060 if (neighbour != null) 061 return neighbour; 062 } 063 return null; 064 } 065 066 public class InitialSelection extends Selection { 067 public InitialSelection(Student student, Assignment<Request, Enrollment> assignment) { 068 super(student, assignment); 069 } 070 071 @Override 072 public void backTrack(int idx) { 073 if (iTimeout > 0 && (JProf.currentTimeMillis() - iT0) > iTimeout) { 074 iTimeoutReached = true; 075 return; 076 } 077 if (getBestAssignment() != null && getBound(idx) >= getBestValue()) { 078 return; 079 } 080 if (idx == iAssignment.length) { 081 if (getBestAssignment() == null || getValue() < getBestValue()) { 082 saveBest(); 083 } 084 return; 085 } 086 Request request = iStudent.getRequests().get(idx); 087 if (!canAssign(request, idx)) { 088 backTrack(idx + 1); 089 return; 090 } 091 if (request.isMPP()) { 092 Enrollment initial = request.getInitialAssignment(); 093 if (initial != null) { 094 if (!inConflict(idx, initial)) { 095 iAssignment[idx] = initial; 096 backTrack(idx + 1); 097 iAssignment[idx] = null; 098 } 099 } else { 100 backTrack(idx + 1); 101 } 102 } else { 103 backTrack(idx + 1); 104 } 105 } 106 } 107}