net.sf.cpsolver.coursett.heuristics
Class UniversalPerturbationsCounter

java.lang.Object
  net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter
      net.sf.cpsolver.coursett.heuristics.UniversalPerturbationsCounter

All Implemented Interfaces:

PerturbationsCounter

public class UniversalPerturbationsCounter
extends DefaultPerturbationsCounter

Perturbation penalty computation.

In practise, the strategy for computing perturbations needs to be extended. For example, a change in time is usually much worse than a movement to a different classroom. The number of enrolled/involved students should also be taken into account. Another factor is whether the solution has already been published or not.
The priorities for evaluating perturbations are as follows. Before publishing timetable:

• minimize number of classes with time changes,
• minimize number of student conflicts,
• optimize satisfaction of problem soft constraints.

After publishing the timetable (class time changes are not allowed):

• minimize number of additional (new) student conflicts,
• minimize number of students with time changes,
• minimize number of classes with time changes,
• optimize satisfaction of problem soft constraints.

In both cases, the number of classes with room change is not significant at all. Before the timetable is published, minimizing the number of classes with time changes is the most important criteria for the MPP as long as it does not create too many additional student conflicts in the process. Therefore, as a compromise, the cost (in equivalent conflicts) of changing the time assigned to a class equals a number like 5% of the students enrolled in that class. Otherwise none of our other criteria would have any importance.

Similar properties apply between other criteria as well. To fulfil all these needs we have crated a function (called perturbations penalty) which can be computed over a partial solution. This is a weighted sum of various perturbations criteria like the number of classes with time changes or the number of additional student conflicts. This perturbation penalty is added as an extra optimization criterion to the solution comparator and to value selection criterion, so we can also setup the weights between this perturbation penalty and other (initial) soft constraints.

Parameters:

Parameter	Type	Comment
Perturbations.DifferentPlacement	Double	Different value than initial is assigned
Perturbations.AffectedStudentWeight	Double	Number of students which are enrolled in a class which is placed to a different location than initial (a student can be included twice or more)
Perturbations.AffectedInstructorWeight	Double	Number of instructors which are assigned to classes which are placed to different locations than initial (an instructor can be included twice or more)
Perturbations.DifferentRoomWeight	Double	Number of classes which are placed to a different room than initial
Perturbations.DifferentBuildingWeight	Double	Number of classes which are placed to a different building than initial
Perturbations.DifferentTimeWeight	Double	Number of classes which are placed in a different time than initial
Perturbations.DifferentDayWeight	Double	Number of classes which are placed in a different days than initial
Perturbations.DifferentHourWeight	Double	Number of classes which are placed in a different hours than initial
Perturbations.DeltaStudentConflictsWeight	Double	Difference of student conflicts of classes assigned to current placements instead of initial placements. It is a difference between number of students conflicts which are in the initial solution and the current one. Student conflicts created by classes without initial placement are not taken into account
Perturbations.NewStudentConflictsWeight	Double	New created student conflicts -- particular students are taken into account. Student conflicts created by classes without initial placement are not taken into account
Perturbations.TooFarForInstructorsWeight	Double	New placement of a class is too far from the intial placement (instructor-wise). It is computed only when the class has an instructor assigned, moreover: 0 < distance(currentPlacement,initialPlacement) <= 5 .. weight is taken once 5 < distance(currentPlacement,initialPlacement) <= 20 .. weight is taken twice 20 < distance(currentPlacement,initialPlacement) .. weight is taken ten times
Perturbations.TooFarForStudentsWeight	Double	New placement of a class is too far from the intial placement (instructor-student). It is weighted by the number of students enrolled in the class when distance(currentPlacement,initialPlacement) > 67
Perturbations.DeltaInstructorDistancePreferenceWeight	Double	Difference between number of instructor distance preferences of the initial (but maybe inconsistent) solution and the current solution. Instructor distance preferences of classes without initial placement are not taken into account
Perturbations.DeltaRoomPreferenceWeight	Double	Difference between room preferences of the initial and the current solution. Room preferences of classes without initial placement are not taken into account
Perturbations.DeltaTimePreferenceWeight	Double	Difference between time preferences of the initial and the current solution. Time preferences of classes without initial placement are not taken into account
Perturbations.AffectedStudentByTimeWeight	Double	Number of students which are enrolled in a class which is placed to a different time than initial
Perturbations.AffectedInstructorByTimeWeight	Double	Number of instructors which are assigned to classes which are placed to different time than initial
Perturbations.AffectedStudentByRoomWeight	Double	Number of students which are enrolled in a class which is placed to a different room than initial
Perturbations.AffectedInstructorByRoomWeight	Double	Number of instructors which are assigned to classes which are placed to different room than initial
Perturbations.AffectedStudentByBldgWeight	Double	Number of students which are enrolled in a class which is placed to a different building than initial
Perturbations.AffectedInstructorByBldgWeight	Double	Number of instructors which are assigned to classes which are placed to different building than initial

Version:

CourseTT 1.1 (University Course Timetabling)
Copyright (C) 2006 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

Field Summary

Fields inherited from class net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter

sDoubleFormat

Constructor Summary

UniversalPerturbationsCounter(DataProperties properties)

Method Summary

Hashtable	getCompactInfo(Model model, boolean includeZero, boolean weighted)
Hashtable	getCompactInfo(Model model, Placement assignedPlacement, boolean includeZero, boolean weighted)
void	getInfo(Dictionary info, Model model) Some (perturbation) information about the solution might be returned here.
void	getInfo(Dictionary info, Model model, Vector variables) Some (perturbation) information about the solution might be returned here (only include variables from the given set).
protected double	getPenalty(Value assignedValue, Value initialValue) Computes perturbation penalty between assigned and initial value of the same lecture.

Methods inherited from class net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter

getPenaltyA, getPenaltyB, getPenaltyC, getPenaltyD, getPerturbationPenalty, getPerturbationPenalty, getPerturbationPenalty, getViolatedInitials, init

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

UniversalPerturbationsCounter

public UniversalPerturbationsCounter(DataProperties properties)

Method Detail

getPenalty

protected double getPenalty(Value assignedValue,
                            Value initialValue)

Description copied from class: DefaultPerturbationsCounter

Computes perturbation penalty between assigned and initial value of the same lecture. It is called only when assignedValue is different to initialValue.

Overrides:

getPenalty in class DefaultPerturbationsCounter

Parameters:

assignedValue - value assigned to a varuable (null when variable is unassigned)

initialValue - initial value of the same varaible (always not null)

getInfo

public void getInfo(Dictionary info,
                    Model model)

Description copied from interface: PerturbationsCounter

Some (perturbation) information about the solution might be returned here.

Specified by:

getInfo in interface PerturbationsCounter

Overrides:

getInfo in class DefaultPerturbationsCounter

Parameters:

info - resultant info table

model - current model

getInfo

public void getInfo(Dictionary info,
                    Model model,
                    Vector variables)

Description copied from interface: PerturbationsCounter

Some (perturbation) information about the solution might be returned here (only include variables from the given set).

Specified by:

getInfo in interface PerturbationsCounter

Overrides:

getInfo in class DefaultPerturbationsCounter

Parameters:

info - resultant info table

model - current model

getCompactInfo

public Hashtable getCompactInfo(Model model,
                                boolean includeZero,
                                boolean weighted)

getCompactInfo

public Hashtable getCompactInfo(Model model,
                                Placement assignedPlacement,
                                boolean includeZero,
                                boolean weighted)