org.cpsolver.exam.split

Class ExamSplitter

java.lang.Object

org.cpsolver.ifs.criteria.AbstractCriterion<Exam,ExamPlacement>

org.cpsolver.exam.criteria.ExamCriterion

org.cpsolver.exam.split.ExamSplitter

All Implemented Interfaces:

CanHoldContext, HasAssignmentContext<Exam,ExamPlacement,AbstractCriterion.ValueContext>, Criterion<Exam,ExamPlacement>, ExtendedInfoProvider<Exam,ExamPlacement>, InfoProvider<Exam,ExamPlacement>, ModelListener<Exam,ExamPlacement>

public class ExamSplitter
extends ExamCriterion

Experimental criterion that allows an exam to be split into two if it decreases the number of student conflicts.

An examination split is improving (and is considered) if the weighted number of student conflicts that will be removed by the split is bigger than the weight of the splitter criterion AbstractCriterion.getWeight().

To enable examination splitting, following parameters needs to be set:

• HillClimber.AdditionalNeighbours=org.cpsolver.exam.split.ExamSplitMoves
• GreatDeluge.AdditionalNeighbours=org.cpsolver.exam.split.ExamSplitMoves
• Exams.AdditionalCriteria=org.cpsolver.exam.split.ExamSplitter
• Exams.ExamSplitWeight=500

The Exams.ExamSplitWeight represents the weight of a split. For instance, to allow only splits that decrease the number of student direct conflicts, half of the weight of a direct student conflict is a good value for this weight.

Version:

ExamTT 1.3 (Examination Timetabling)
Copyright (C) 2008 - 2014 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

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 3 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 see http://www.gnu.org/licenses/.

Author:

Tomáš Müller

Nested Class Summary

Nested classes/interfaces inherited from class org.cpsolver.ifs.criteria.AbstractCriterion

AbstractCriterion.ValueContext, AbstractCriterion.ValueUpdateType

Field Summary

Fields inherited from class org.cpsolver.ifs.criteria.AbstractCriterion

iBest, iDebug, iWeight, sDoubleFormat, sPercentFormat

Fields inherited from interface org.cpsolver.ifs.assignment.context.CanHoldContext

sMaxSize

Constructor Summary

Constructors

Constructor and Description
ExamSplitter() Examination splitter criterion.

Method Summary

Modifier and Type	Method and Description
void	bestRestored(Assignment<Exam,ExamPlacement> assignment) Best solution was restored, change the splits back to what it was in the best solution
void	bestSaved(Assignment<Exam,ExamPlacement> assignment) Best solution was saved, remember the current splits
boolean	canMerge(Exam exam) True, if the given exam can be merged (it has been split)
boolean	canSplit(Exam exam) True, if an exam can be split
List<Exam>	children(Exam parent) Children exams of an exam that has been split.
double	delta(Assignment<Exam,ExamPlacement> assignment, ExamStudent student, ExamPlacement oldPlacement, ExamPlacement newPlacement) Difference in the total weighted student conflicts (including StudentDirectConflicts, StudentMoreThan2ADayConflicts, and StudentBackToBackConflicts) if a student is moved from an exam with one placement into an exam with another placement.
double[]	getBounds(Assignment<Exam,ExamPlacement> assignment, Collection<Exam> exams) Not used
void	getInfo(Assignment<Exam,ExamPlacement> assignment, Map<String,String> info) Lists the split
double	getValue(Assignment<Exam,ExamPlacement> assignment) Current value of the criterion (optimization objective)
double	getValue(Assignment<Exam,ExamPlacement> assignment, ExamPlacement value, Set<ExamPlacement> conflicts) Not used
double	getWeightDefault(DataProperties config) Returns half of a student direct conflict weight
String	getWeightName() Returns Exams.ExamSplitWeight
String	getXmlWeightName() Returns examSplitWeight
boolean	init(Solver<Exam,ExamPlacement> solver) Initialization
Exam	merge(Assignment<Exam,ExamPlacement> assignment, Exam child, long iteration) Merge an exam
Exam	parent(Exam exam) Parent of an exam that has been split.
void	shuffle(Assignment<Exam,ExamPlacement> assignment, Exam exam, long iteration) Shuffle students between the given exam and all the other exams in the split (if there are any).
Exam	split(Assignment<Exam,ExamPlacement> assignment, Exam parent, long iteration, ExamPlacement placement) Split an exam
String	toString(Assignment<Exam,ExamPlacement> assignment) Simple text representation of the criterion and its value.

Methods inherited from class org.cpsolver.exam.criteria.ExamCriterion

getPeriodValue, getRoomValue, getXmlParameters, isPeriodCriterion, isRoomCriterion, setWeight, setXmlParameters

Methods inherited from class org.cpsolver.ifs.criteria.AbstractCriterion

afterAssigned, afterUnassigned, beforeAssigned, beforeUnassigned, clearCache, computeBounds, configure, constraintAdded, constraintRemoved, createAssignmentContext, getAbbreviation, getAssignmentContextReference, getBest, getBounds, getBounds, getBounds, getContext, getContext, getExtendedInfo, getInfo, getModel, getName, getPerc, getPercentage, getPercRev, getValue, getValue, getValue, getValueUpdateType, getWeight, getWeightedBest, getWeightedValue, getWeightedValue, getWeightedValue, getWeightedValue, getWeightedValue, getWeightedValue, inc, inc, setAssignmentContextReference, setModel, setValueUpdateType, variableAdded, variableRemoved

Methods inherited from class java.lang.Object

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

Constructor Detail

ExamSplitter

public ExamSplitter()

Examination splitter criterion.

Method Detail

init

public boolean init(Solver<Exam,ExamPlacement> solver)

Initialization

Specified by:

init in interface ModelListener<Exam,ExamPlacement>

Overrides:

init in class AbstractCriterion<Exam,ExamPlacement>

Parameters:

solver - IFS solver

Returns:

true if successfully initialized

getWeightName

public String getWeightName()

Returns Exams.ExamSplitWeight

Overrides:

getWeightName in class ExamCriterion

Returns:

name of the weight associated with this criterion

getXmlWeightName

public String getXmlWeightName()

Returns examSplitWeight

Overrides:

getXmlWeightName in class ExamCriterion

Returns:

name of the weight parameter in the XML

getWeightDefault

public double getWeightDefault(DataProperties config)

Returns half of a student direct conflict weight

Overrides:

getWeightDefault in class AbstractCriterion<Exam,ExamPlacement>

Parameters:

config - solver configuration

Returns:

default criterion weight value

canSplit

public boolean canSplit(Exam exam)

True, if an exam can be split

Parameters:

exam - given exam

Returns:

true if the given exam can be split

parent

public Exam parent(Exam exam)

Parent of an exam that has been split.

Parameters:

exam - an exam in question

Returns:

parent exam if the exam has been split, or the exam itself otherwise (each non-split exam is its own parent)

children

public List<Exam> children(Exam parent)

Children exams of an exam that has been split. These are all the exams that the parent exam has been split into.

Parameters:

parent - an exam in question

Returns:

all children exams, or null of the exam has not been split yet

split

public Exam split(Assignment<Exam,ExamPlacement> assignment,
                  Exam parent,
                  long iteration,
                  ExamPlacement placement)

Split an exam

Parameters:

assignment - current assignment

parent - an exam to be split

iteration - solver iteration

placement - placement of the new exam

Returns:

new exam assigned to the given placement with students moved into it; null if the given exam cannot be split

canMerge

public boolean canMerge(Exam exam)

True, if the given exam can be merged (it has been split)

Parameters:

exam - given exam

Returns:

true if the given exam can be merged back

merge

public Exam merge(Assignment<Exam,ExamPlacement> assignment,
                  Exam child,
                  long iteration)

Merge an exam

Parameters:

assignment - current assignment

child - an exam to be merged

iteration - solver iteration

Returns:

parent exam of the exam that has been deleted; null if the given exam cannot be merged

delta

public double delta(Assignment<Exam,ExamPlacement> assignment,
                    ExamStudent student,
                    ExamPlacement oldPlacement,
                    ExamPlacement newPlacement)

Difference in the total weighted student conflicts (including StudentDirectConflicts, StudentMoreThan2ADayConflicts, and StudentBackToBackConflicts) if a student is moved from an exam with one placement into an exam with another placement.

Parameters:

assignment - current assignment

student - a student in question

oldPlacement - placement of the exam in which the student is now

newPlacement - placement of the exam into which the student would be moved

Returns:

difference in the student conflict weight

shuffle

public void shuffle(Assignment<Exam,ExamPlacement> assignment,
                    Exam exam,
                    long iteration)

Shuffle students between the given exam and all the other exams in the split (if there are any). Only moves between exams that improve delta(Assignment, ExamStudent, ExamPlacement, ExamPlacement) are considered.

Parameters:

assignment - current assignment

exam - an exam in question

iteration - solver iteration

getValue

public double getValue(Assignment<Exam,ExamPlacement> assignment)

Description copied from interface: Criterion

Current value of the criterion (optimization objective)

Specified by:

getValue in interface Criterion<Exam,ExamPlacement>

Overrides:

getValue in class AbstractCriterion<Exam,ExamPlacement>

Parameters:

assignment - current assignment

Returns:

value of this criterion

getValue

public double getValue(Assignment<Exam,ExamPlacement> assignment,
                       ExamPlacement value,
                       Set<ExamPlacement> conflicts)

Not used

Parameters:

assignment - current assignment

value - given value

conflicts - values conflicting with the given value

Returns:

change in this criterion value when assigned

getBounds

public double[] getBounds(Assignment<Exam,ExamPlacement> assignment,
                          Collection<Exam> exams)

Not used

Specified by:

getBounds in interface Criterion<Exam,ExamPlacement>

Overrides:

getBounds in class ExamCriterion

Parameters:

assignment - current assignment

exams - list of problem variables

Returns:

minimum and maximum of this criterion for the given sub-problem

toString

public String toString(Assignment<Exam,ExamPlacement> assignment)

Description copied from class: AbstractCriterion

Simple text representation of the criterion and its value. E.g., X:x where X is the AbstractCriterion.getAbbreviation() and x is the current value AbstractCriterion.getValue(Assignment).

Specified by:

toString in interface Criterion<Exam,ExamPlacement>

Overrides:

toString in class AbstractCriterion<Exam,ExamPlacement>

Parameters:

assignment - current assignment

Returns:

short string representation (e.g., PP:95% for period preference)

getInfo

public void getInfo(Assignment<Exam,ExamPlacement> assignment,
                    Map<String,String> info)

Lists the split

Specified by:

getInfo in interface InfoProvider<Exam,ExamPlacement>

Overrides:

getInfo in class ExamCriterion

Parameters:

assignment - current assignment

info - info table

bestSaved

public void bestSaved(Assignment<Exam,ExamPlacement> assignment)

Best solution was saved, remember the current splits

Specified by:

bestSaved in interface Criterion<Exam,ExamPlacement>

Overrides:

bestSaved in class AbstractCriterion<Exam,ExamPlacement>

Parameters:

assignment - current assignment

bestRestored

public void bestRestored(Assignment<Exam,ExamPlacement> assignment)

Best solution was restored, change the splits back to what it was in the best solution

Specified by:

bestRestored in interface Criterion<Exam,ExamPlacement>

Overrides:

bestRestored in class AbstractCriterion<Exam,ExamPlacement>

Parameters:

assignment - current assignment