org.cpsolver.exam.model

Class ExamModel

java.lang.Object

org.cpsolver.ifs.model.Model<V,T>

org.cpsolver.ifs.assignment.context.ModelWithContext<Exam,ExamPlacement,ExamContext>

org.cpsolver.exam.model.ExamModel

All Implemented Interfaces:

CanHoldContext, HasAssignmentContext<Exam,ExamPlacement,ExamContext>

public class ExamModel
extends ModelWithContext<Exam,ExamPlacement,ExamContext>

Examination timetabling model. Exams Exam are modeled as variables, rooms ExamRoom and students ExamStudent as constraints. Assignment of an exam to time (modeled as non-overlapping periods ExamPeriod) and space (set of rooms) is modeled using values ExamPlacement. In order to be able to model individual period and room preferences, period and room assignments are wrapped with ExamPeriodPlacement and ExamRoomPlacement classes respectively. Moreover, additional distribution constraint ExamDistributionConstraint can be defined in the model.

The objective function consists of the following criteria:

• Direct student conflicts (a student is enrolled in two exams that are scheduled at the same period, weighted by Exams.DirectConflictWeight)
• Back-to-Back student conflicts (a student is enrolled in two exams that are scheduled in consecutive periods, weighted by Exams.BackToBackConflictWeight). If Exams.IsDayBreakBackToBack is false, there is no conflict between the last period and the first period of consecutive days.
• Distance Back-to-Back student conflicts (same as Back-to-Back student conflict, but the maximum distance between rooms in which both exam take place is greater than Exams.BackToBackDistance, weighted by Exams.DistanceBackToBackConflictWeight).
• More than two exams a day (a student is enrolled in three exams that are scheduled at the same day, weighted by Exams.MoreThanTwoADayWeight).
• Period penalty (total of period penalties PeriodPenalty of all assigned exams, weighted by Exams.PeriodWeight).
• Room size penalty (total of room size penalties RoomSizePenalty of all assigned exams, weighted by Exams.RoomSizeWeight).
• Room split penalty (total of room split penalties RoomSplitPenalty of all assigned exams, weighted by Exams.RoomSplitWeight).
• Room penalty (total of room penalties RoomPenalty of all assigned exams, weighted by Exams.RoomWeight).
• Distribution penalty (total of distribution constraint weights ExamDistributionConstraint.getWeight() of all soft distribution constraints that are not satisfied, i.e., ExamDistributionConstraint.isSatisfied(Assignment) = false; weighted by Exams.DistributionWeight).
• Direct instructor conflicts (an instructor is enrolled in two exams that are scheduled at the same period, weighted by Exams.InstructorDirectConflictWeight)
• Back-to-Back instructor conflicts (an instructor is enrolled in two exams that are scheduled in consecutive periods, weighted by Exams.InstructorBackToBackConflictWeight). If Exams.IsDayBreakBackToBack is false, there is no conflict between the last period and the first period of consecutive days.
• Distance Back-to-Back instructor conflicts (same as Back-to-Back instructor conflict, but the maximum distance between rooms in which both exam take place is greater than Exams.BackToBackDistance, weighted by Exams.InstructorDistanceBackToBackConflictWeight).
• Room split distance penalty (if an examination is assigned between two or three rooms, distance between these rooms can be minimized using this criterion)
• Front load penalty (large exams can be penalized if assigned on or after a certain period)

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.assignment.context.ModelWithContext

ModelWithContext.ContextUpdateType

Field Summary

Fields inherited from class org.cpsolver.ifs.model.Model

sDoubleFormat, sPercentageFormat, sTimeFormat

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

sMaxSize

Constructor Summary

Constructors

Constructor and Description
ExamModel(DataProperties properties) Constructor

Method Summary

Modifier and Type	Method and Description
ExamPeriod	addPeriod(Long id, String day, String time, int length, int penalty) Add a period
ExamContext	createAssignmentContext(Assignment<Exam,ExamPlacement> assignment) Create a new assignment context for the given assignment.
double	getBackToBackDistance() Back-to-back distance, can be set by problem property Exams.BackToBackDistance, or in the input xml file, property backToBackDistance)
DistanceMetric	getDistanceMetric()
List<ExamDistributionConstraint>	getDistributionConstraints() Distribution constraints
Map<String,String>	getExtendedInfo(Assignment<Exam,ExamPlacement> assignment) Extended info table
List<ExamInstructor>	getInstructors() Problem instructors
Map<ExamInstructor,Set<Exam>>	getInstructorsOfDay(Assignment<Exam,ExamPlacement> assignment, ExamPeriod period)
Map<ExamInstructor,Set<Exam>>	getInstructorsOfDay(Assignment<Exam,ExamPlacement> assignment, int day)
Map<ExamInstructor,Set<Exam>>	getInstructorsOfPeriod(Assignment<Exam,ExamPlacement> assignment, ExamPeriod period)
int	getMaxRooms() Default maximum number of rooms (can be set by problem property Exams.MaxRooms, or in the input xml file, property maxRooms)
int	getNrDays() Number of days
int	getNrPeriods() Number of periods
ExamPeriod	getPeriod(Long id) Period of given unique id
List<ExamPeriod>	getPeriods() List of periods, use addPeriod(Long, String, String, int, int) to add a period
DataProperties	getProperties() Problem properties
List<ExamRoom>	getRooms() Problem rooms
ExamRoomSharing	getRoomSharing() Return examination room sharing model
List<ExamStudent>	getStudents() Problem students
Map<ExamStudent,Set<Exam>>	getStudentsOfDay(Assignment<Exam,ExamPlacement> assignment, ExamPeriod period)
Map<ExamStudent,Set<Exam>>	getStudentsOfDay(Assignment<Exam,ExamPlacement> assignment, int day)
Map<ExamStudent,Set<Exam>>	getStudentsOfPeriod(Assignment<Exam,ExamPlacement> assignment, ExamPeriod period)
double[]	getTotalMultiValue(Assignment<Exam,ExamPlacement> assignment) Return weighted individual objective criteria.
double	getTotalValue(Assignment<Exam,ExamPlacement> assignment) Objective function.
boolean	hasRoomSharing() True if there is an examination sharing model
void	init() Initialization of the model
boolean	isCheckForPeriodOverlaps() Check for examination periods that overlap with each other
boolean	isDayBreakBackToBack() True when back-to-back student conflict is to be encountered when a student is enrolled into an exam that is on the last period of one day and another exam that is on the first period of the consecutive day.
boolean	load(Document document, Assignment<Exam,ExamPlacement> assignment) Load model (including its solution) from XML.
boolean	load(Document document, Assignment<Exam,ExamPlacement> assignment, Callback saveBest) Load model (including its solution) from XML.
Document	save(Assignment<Exam,ExamPlacement> assignment) Save model (including its solution) into XML.
void	setCheckForPeriodOverlaps(boolean check) Enable checking for period overlaps
void	setMaxRooms(int maxRooms) Default maximum number of rooms (can be set by problem property Exams.MaxRooms, or in the input xml file, property maxRooms)
void	setRoomSharing(ExamRoomSharing sharing) Set examination sharing model
String	toString(Assignment<Exam,ExamPlacement> assignment) String representation -- returns a list of values of objective criteria

Methods inherited from class org.cpsolver.ifs.assignment.context.ModelWithContext

afterAssigned, afterUnassigned, beforeAssigned, beforeUnassigned, getAssignmentContextReference, getContext, getContext, getContextUpdateType, setAssignmentContextReference, setContextUpdateType

Methods inherited from class org.cpsolver.ifs.model.Model

addConstraint, addCriterion, addGlobalConstraint, addModelListener, addVariable, afterAssigned, afterUnassigned, assignedVariables, assignedVariables, beforeAssigned, beforeUnassigned, bestUnassignedVariables, bestUnassignedVariables, clearAssignmentContexts, clearBest, conflictConstraints, conflictValues, conflictValues, constraints, countConstraints, countGlobalConstraints, countVariables, createAssignmentContexts, createInheritedAssignment, createReference, getBestPerturbations, getBestUnassignedVariables, getBestValue, getCriteria, getCriterion, getDefaultAssignment, getEmptyAssignment, getExtendedInfo, getInfo, getInfo, getInfo, getInfo, getInfoProviders, getModelListeners, getPerc, getPercRev, getTotalValue, getTotalValue, getTotalValue, globalConstraints, inConflict, inConflict, init, invalidateVariablesWithInitialValueCache, modelListenerOfType, nrAssignedVariables, nrAssignedVariables, nrUnassignedVariables, nrUnassignedVariables, perturbVariables, perturbVariables, perturbVariables, perturbVariables, perturbVariables, removeConstraint, removeCriterion, removeCriterion, removeGlobalConstraint, removeModelListener, removeReference, removeVariable, restoreBest, restoreBest, restoreBest, saveBest, saveBest, setBestValue, setDefaultAssignment, toString, unassignedHardConstraints, unassignedVariables, unassignedVariables, variables, variablesWithInitialValue, weaken

Methods inherited from class java.lang.Object

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

Constructor Detail

ExamModel

public ExamModel(DataProperties properties)

Constructor

Parameters:

properties - problem properties

Method Detail

getDistanceMetric

public DistanceMetric getDistanceMetric()

hasRoomSharing

public boolean hasRoomSharing()

True if there is an examination sharing model

Returns:

true if there is an examination sharing model

getRoomSharing

public ExamRoomSharing getRoomSharing()

Return examination room sharing model

Returns:

examination room sharing model, if set

setRoomSharing

public void setRoomSharing(ExamRoomSharing sharing)

Set examination sharing model

Parameters:

sharing - examination sharing model

init

public void init()

Initialization of the model

getMaxRooms

public int getMaxRooms()

Default maximum number of rooms (can be set by problem property Exams.MaxRooms, or in the input xml file, property maxRooms)

Returns:

default maximum number of rooms for an exam

setMaxRooms

public void setMaxRooms(int maxRooms)

Default maximum number of rooms (can be set by problem property Exams.MaxRooms, or in the input xml file, property maxRooms)

Parameters:

maxRooms - default maximum number of rooms for an exam

isCheckForPeriodOverlaps

public boolean isCheckForPeriodOverlaps()

Check for examination periods that overlap with each other

Returns:

true if examination periods can overlap with each other

setCheckForPeriodOverlaps

public void setCheckForPeriodOverlaps(boolean check)

Enable checking for period overlaps

addPeriod

public ExamPeriod addPeriod(Long id,
                            String day,
                            String time,
                            int length,
                            int penalty)

Add a period

Parameters:

id - period unique identifier

day - day (e.g., 07/12/10)

time - (e.g., 8:00am-10:00am)

length - length of period in minutes

penalty - period penalty

Returns:

added period

getNrDays

public int getNrDays()

Number of days

Returns:

number of days

getNrPeriods

public int getNrPeriods()

Number of periods

Returns:

number of periods

getPeriods

public List<ExamPeriod> getPeriods()

List of periods, use addPeriod(Long, String, String, int, int) to add a period

Returns:

list of ExamPeriod

getPeriod

public ExamPeriod getPeriod(Long id)

Period of given unique id

Parameters:

id - period unique id

Returns:

the appropriate period

isDayBreakBackToBack

public boolean isDayBreakBackToBack()

True when back-to-back student conflict is to be encountered when a student is enrolled into an exam that is on the last period of one day and another exam that is on the first period of the consecutive day. It can be set by problem property Exams.IsDayBreakBackToBack, or in the input xml file, property isDayBreakBackToBack)

Returns:

true if last exam on one day is back-to-back to the first exam of the following day

getBackToBackDistance

public double getBackToBackDistance()

Back-to-back distance, can be set by problem property Exams.BackToBackDistance, or in the input xml file, property backToBackDistance)

Returns:

back-to-back distance in meters

getTotalValue

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

Objective function.

Overrides:

getTotalValue in class Model<Exam,ExamPlacement>

Parameters:

assignment - current assignment

Returns:

weighted sum of objective criteria

getTotalMultiValue

public double[] getTotalMultiValue(Assignment<Exam,ExamPlacement> assignment)

Return weighted individual objective criteria.

Parameters:

assignment - current assignment

Returns:

an array of weighted objective criteria

toString

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

String representation -- returns a list of values of objective criteria

Overrides:

toString in class Model<Exam,ExamPlacement>

Parameters:

assignment - current assignment

Returns:

comma separated list of AbstractCriterion.toString(Assignment)

getExtendedInfo

public Map<String,String> getExtendedInfo(Assignment<Exam,ExamPlacement> assignment)

Extended info table

Overrides:

getExtendedInfo in class Model<Exam,ExamPlacement>

Parameters:

assignment - current assignment

Returns:

extended info table

getProperties

public DataProperties getProperties()

Problem properties

Returns:

solver configuration

getRooms

public List<ExamRoom> getRooms()

Problem rooms

Returns:

list of ExamRoom

getStudents

public List<ExamStudent> getStudents()

Problem students

Returns:

list of ExamStudent

getInstructors

public List<ExamInstructor> getInstructors()

Problem instructors

Returns:

list of ExamInstructor

getDistributionConstraints

public List<ExamDistributionConstraint> getDistributionConstraints()

Distribution constraints

Returns:

list of ExamDistributionConstraint

save

public Document save(Assignment<Exam,ExamPlacement> assignment)

Save model (including its solution) into XML.

Parameters:

assignment - current assignment

Returns:

created XML document

load

public boolean load(Document document,
                    Assignment<Exam,ExamPlacement> assignment)

Load model (including its solution) from XML.

Parameters:

document - XML document

assignment - assignment to be loaded

Returns:

true if successfully loaded

load

public boolean load(Document document,
                    Assignment<Exam,ExamPlacement> assignment,
                    Callback saveBest)

Load model (including its solution) from XML.

Parameters:

document - XML document

assignment - assignment to be loaded

saveBest - callback executed once the best assignment is loaded and assigned

Returns:

true if successfully loaded

createAssignmentContext

public ExamContext createAssignmentContext(Assignment<Exam,ExamPlacement> assignment)

Description copied from interface: HasAssignmentContext

Create a new assignment context for the given assignment. If there are already some variables assigned in the value, the method should make sure that the context is appropriately initialized.

Parameters:

assignment - an assignment for which there needs to be an assignment context

Returns:

a new instance of the assignment context, filled according to the given assignment

getStudentsOfPeriod

public Map<ExamStudent,Set<Exam>> getStudentsOfPeriod(Assignment<Exam,ExamPlacement> assignment,
                                                      ExamPeriod period)

getStudentsOfDay

public Map<ExamStudent,Set<Exam>> getStudentsOfDay(Assignment<Exam,ExamPlacement> assignment,
                                                   ExamPeriod period)

getStudentsOfDay

public Map<ExamStudent,Set<Exam>> getStudentsOfDay(Assignment<Exam,ExamPlacement> assignment,
                                                   int day)

getInstructorsOfPeriod

public Map<ExamInstructor,Set<Exam>> getInstructorsOfPeriod(Assignment<Exam,ExamPlacement> assignment,
                                                            ExamPeriod period)

getInstructorsOfDay

public Map<ExamInstructor,Set<Exam>> getInstructorsOfDay(Assignment<Exam,ExamPlacement> assignment,
                                                         ExamPeriod period)

getInstructorsOfDay

public Map<ExamInstructor,Set<Exam>> getInstructorsOfDay(Assignment<Exam,ExamPlacement> assignment,
                                                         int day)