org.cpsolver.coursett.constraint

Class GroupConstraint

java.lang.Object

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

org.cpsolver.ifs.assignment.context.ConstraintWithContext<Lecture,Placement,GroupConstraint.GroupConstraintContext>

org.cpsolver.coursett.constraint.GroupConstraint

All Implemented Interfaces:

Comparable<Constraint<Lecture,Placement>>, CanHoldContext, HasAssignmentContext<Lecture,Placement,GroupConstraint.GroupConstraintContext>

public class GroupConstraint
extends ConstraintWithContext<Lecture,Placement,GroupConstraint.GroupConstraintContext>

Group constraint.
This constraint expresses relations between several classes, e.g., that two sections of the same lecture can not be taught at the same time, or that some classes have to be taught one immediately after another. It can be either hard or soft.

Following constraints are now supported:

Related Solver Parameters

Constraint	Comment
SAME_TIME	Same time: given classes have to be taught in the same hours. If the classes are of different length, the smaller one cannot start before the longer one and it cannot end after the longer one.
SAME_DAYS	Same days: given classes have to be taught in the same day. If the classes are of different time patterns, the days of one class have to form a subset of the days of the other class.
BTB	Back-to-back constraint: given classes have to be taught in the same room and they have to follow one strictly after another.
BTB_TIME	Back-to-back constraint: given classes have to follow one strictly after another, but they can be taught in different rooms.
DIFF_TIME	Different time: given classes cannot overlap in time.
NHB(1), NHB(1.5), NHB(2), ... NHB(8)	Number of hours between: between the given classes, the exact number of hours have to be kept.
SAME_START	Same starting hour: given classes have to start in the same hour.
SAME_ROOM	Same room: given classes have to be placed in the same room.
NHB_GTE(1)	Greater than or equal to 1 hour between: between the given classes, the number of hours have to be one or more.
NHB_LT(6)	Less than 6 hours between: between the given classes, the number of hours have to be less than six.

Version:

CourseTT 1.3 (University Course Timetabling)
Copyright (C) 2006 - 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

Modifier and Type	Class and Description
static interface	GroupConstraint.AssignmentPairCheck Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), only need to implement this interface.
static interface	GroupConstraint.AssignmentParameterPairCheck<P> Group constraints that can have parameters need to implement this interface instead of GroupConstraint.AssignmentPairCheck or GroupConstraint.PairCheck.
static class	GroupConstraint.ConstraintType Group constraint type.
static interface	GroupConstraint.ConstraintTypeInterface Constraint type interface
static class	GroupConstraint.Flag Group constraint building blocks (individual constraints that need more than GroupConstraint.PairCheck)
class	GroupConstraint.GroupConstraintContext
static interface	GroupConstraint.PairCheck Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), only need to implement this interface.
static class	GroupConstraint.ParametrizedConstraintType<P> Constraint type with a parameter

Field Summary

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

iConstraintListeners, iId

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

sMaxSize

Constructor Summary

Constructors

Constructor and Description
GroupConstraint()
GroupConstraint(Long id, GroupConstraint.ConstraintTypeInterface type, String preference) Constructor

Method Summary

Modifier and Type	Method and Description
void	addVariable(Lecture lecture) Add a variable to this constraint
boolean	canShareRoom()
void	computeConflicts(Assignment<Lecture,Placement> assignment, Placement value, Set<Placement> conflicts) The only method which has to be implemented by any constraint.
void	computeConflicts(Assignment<Lecture,Placement> assignment, Placement value, Set<Placement> conflicts, boolean fwdCheck)
void	computeConflictsNoForwardCheck(Assignment<Lecture,Placement> assignment, Placement value, Set<Placement> conflicts) Compute conflicts method that does not do any forward checking.
GroupConstraint.GroupConstraintContext	createAssignmentContext(Assignment<Lecture,Placement> assignment) Create a new assignment context for the given assignment.
boolean	equals(Object o) Compare two constraints for equality (Constraint.getId() is used)
boolean	forwardCheck(Assignment<Lecture,Placement> assignment, Placement value, Set<GroupConstraint> ignore, int depth)
void	forwardCheck(Assignment<Lecture,Placement> assignment, Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth)
Long	getConstraintId() Constraint id
static GroupConstraint.ConstraintTypeInterface	getConstraintType(String reference) Constraint type from reference
int	getCurrentPreference(Assignment<Lecture,Placement> assignment) Current constraint preference (0 if prohibited or required, depends on current satisfaction of the constraint)
int	getCurrentPreference(Assignment<Lecture,Placement> assignment, Placement placement) Current constraint preference change (if given placement is assigned)
protected long	getGeneratedId() Generated unique id
long	getId() Unique id
String	getName() Constraint's name -- for printing purposes
int	getPreference() Constraint preference (0 if prohibited or required)
String	getPrologPreference() Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for preference
GroupConstraint.ConstraintTypeInterface	getType() Return constraint type (e.g, GroupConstraint.ConstraintType.SAME_TIME)
boolean	inConflict(Assignment<Lecture,Placement> assignment, Placement value) Returns true if the given assignment is inconsistent with the existing assignments respecting this constraint.
boolean	isChildrenNotOverlap(Assignment<Lecture,Placement> assignment, Lecture lec1, Placement plc1, Lecture lec2, Placement plc2)
boolean	isConsistent(Placement value1, Placement value2) Returns true if the given assignments are consistent respecting this constraint.
boolean	isHard() Returns true if the constraint is hard.
protected boolean	isOnline(Placement p)
boolean	isProhibited() Is constraint prohibited
boolean	isRequired() Is constraint required
boolean	isSatisfied(Assignment<Lecture,Placement> assignment)
boolean	isSatisfiedPair(Assignment<Lecture,Placement> assignment, Placement plc1, Placement plc2)
protected int	nrSlotsADay(Assignment<Lecture,Placement> assignment, int dayCode, BitSet week, HashMap<Lecture,Placement> assignments, Set<Placement> conflicts)
protected int	nrSlotsADay(Assignment<Lecture,Placement> assignment, int date, HashMap<Lecture,Placement> assignments, Set<Placement> conflicts)
void	removeVariable(Lecture lecture) Remove a variable from this constraint
void	setModel(Model<Lecture,Placement> model) Sets the model which the constraint belongs to
void	setType(GroupConstraint.ConstraintType type) Set constraint type
String	toString()

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

assigned, getAssignmentContextReference, getContext, getContext, setAssignmentContextReference, unassigned

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

addConstraintListener, assignedVariables, compareTo, constraintListeners, countAssignedVariables, countVariables, getDescription, getModel, hashCode, removeConstraintListener, variables

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

GroupConstraint

public GroupConstraint()

GroupConstraint

public GroupConstraint(Long id,
                       GroupConstraint.ConstraintTypeInterface type,
                       String preference)

Constructor

Parameters:

id - constraint id

type - constraString type (e.g, GroupConstraint.ConstraintType.SAME_TIME)

preference - time preference ("R" for required, "P" for prohibited, "-2", "-1", "1", "2" for soft preference)

Method Detail

getConstraintType

public static GroupConstraint.ConstraintTypeInterface getConstraintType(String reference)

Constraint type from reference

Parameters:

reference - constraint reference

Returns:

constraint of the reference

setModel

public void setModel(Model<Lecture,Placement> model)

Description copied from class: Constraint

Sets the model which the constraint belongs to

Overrides:

setModel in class ConstraintWithContext<Lecture,Placement,GroupConstraint.GroupConstraintContext>

Parameters:

model - problem model

addVariable

public void addVariable(Lecture lecture)

Description copied from class: Constraint

Add a variable to this constraint

Overrides:

addVariable in class Constraint<Lecture,Placement>

Parameters:

lecture - a variable

removeVariable

public void removeVariable(Lecture lecture)

Description copied from class: Constraint

Remove a variable from this constraint

Overrides:

removeVariable in class Constraint<Lecture,Placement>

Parameters:

lecture - a variable

getConstraintId

public Long getConstraintId()

Constraint id

Returns:

constraint unique id

getId

public long getId()

Description copied from class: Constraint

Unique id

Overrides:

getId in class Constraint<Lecture,Placement>

Returns:

constraint id

getGeneratedId

protected long getGeneratedId()

Generated unique id

Returns:

generated unique id

getType

public GroupConstraint.ConstraintTypeInterface getType()

Return constraint type (e.g, GroupConstraint.ConstraintType.SAME_TIME)

Returns:

constraint type

setType

public void setType(GroupConstraint.ConstraintType type)

Set constraint type

Parameters:

type - constraint type

isRequired

public boolean isRequired()

Is constraint required

Returns:

true if required

isProhibited

public boolean isProhibited()

Is constraint prohibited

Returns:

true if prohibited

getPrologPreference

public String getPrologPreference()

Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for preference

Returns:

prolog preference

isConsistent

public boolean isConsistent(Placement value1,
                            Placement value2)

Description copied from class: Constraint

Returns true if the given assignments are consistent respecting this constraint. This method is used by MAC (see MacPropagation).

Overrides:

isConsistent in class Constraint<Lecture,Placement>

Parameters:

value1 - a value

value2 - a value

Returns:

true if the constraint is ok with the assignment

computeConflicts

public void computeConflicts(Assignment<Lecture,Placement> assignment,
                             Placement value,
                             Set<Placement> conflicts)

Description copied from class: Constraint

The only method which has to be implemented by any constraint. It returns the values which needs to be unassigned in order to make this constraint consistent with the given value if it is assigned to its variable. The computed list of conflicting values is added to the given set of conflicts.

Specified by:

computeConflicts in class Constraint<Lecture,Placement>

Parameters:

assignment - current assignment

value - value to be assigned to its variable

conflicts - resultant set of conflicting values

computeConflictsNoForwardCheck

public void computeConflictsNoForwardCheck(Assignment<Lecture,Placement> assignment,
                                           Placement value,
                                           Set<Placement> conflicts)

Description copied from class: Constraint

Compute conflicts method that does not do any forward checking. This method defaults to Constraint.computeConflicts(Assignment, Value, Set) and it is called during assignment (from Constraint.assigned(Assignment, long, Value)) to check for conflicting variables that need to be unassigned first.

Overrides:

computeConflictsNoForwardCheck in class Constraint<Lecture,Placement>

Parameters:

assignment - current assignment

value - value to be assigned to its variable

conflicts - resultant set of conflicting values

computeConflicts

public void computeConflicts(Assignment<Lecture,Placement> assignment,
                             Placement value,
                             Set<Placement> conflicts,
                             boolean fwdCheck)

forwardCheck

public void forwardCheck(Assignment<Lecture,Placement> assignment,
                         Placement value,
                         Set<Placement> conflicts,
                         Set<GroupConstraint> ignore,
                         int depth)

inConflict

public boolean inConflict(Assignment<Lecture,Placement> assignment,
                          Placement value)

Description copied from class: Constraint

Returns true if the given assignment is inconsistent with the existing assignments respecting this constraint. This method is used by MAC (see MacPropagation).

Overrides:

inConflict in class Constraint<Lecture,Placement>

Parameters:

assignment - current assignment

value - given value

Returns:

true if there is a conflict with other assigned variables of the constraint

forwardCheck

public boolean forwardCheck(Assignment<Lecture,Placement> assignment,
                            Placement value,
                            Set<GroupConstraint> ignore,
                            int depth)

getPreference

public int getPreference()

Constraint preference (0 if prohibited or required)

Returns:

constraint preference (if soft)

getCurrentPreference

public int getCurrentPreference(Assignment<Lecture,Placement> assignment)

Current constraint preference (0 if prohibited or required, depends on current satisfaction of the constraint)

Parameters:

assignment - current assignment

Returns:

current preference

getCurrentPreference

public int getCurrentPreference(Assignment<Lecture,Placement> assignment,
                                Placement placement)

Current constraint preference change (if given placement is assigned)

Parameters:

assignment - current assignment

placement - placement that is being considered

Returns:

change in the current preference, if assigned

toString

public String toString()

Overrides:

toString in class Object

isHard

public boolean isHard()

Description copied from class: Constraint

Returns true if the constraint is hard. Only hard constraints are allowed to unassign a variable when there is a conflict with a value that is being assigned

Overrides:

isHard in class Constraint<Lecture,Placement>

Returns:

true if the constraint is hard

getName

public String getName()

Description copied from class: Constraint

Constraint's name -- for printing purposes

Overrides:

getName in class Constraint<Lecture,Placement>

Returns:

constraint name

isSatisfied

public boolean isSatisfied(Assignment<Lecture,Placement> assignment)

isChildrenNotOverlap

public boolean isChildrenNotOverlap(Assignment<Lecture,Placement> assignment,
                                    Lecture lec1,
                                    Placement plc1,
                                    Lecture lec2,
                                    Placement plc2)

isSatisfiedPair

public boolean isSatisfiedPair(Assignment<Lecture,Placement> assignment,
                               Placement plc1,
                               Placement plc2)

canShareRoom

public boolean canShareRoom()

nrSlotsADay

protected int nrSlotsADay(Assignment<Lecture,Placement> assignment,
                          int dayCode,
                          BitSet week,
                          HashMap<Lecture,Placement> assignments,
                          Set<Placement> conflicts)

nrSlotsADay

protected int nrSlotsADay(Assignment<Lecture,Placement> assignment,
                          int date,
                          HashMap<Lecture,Placement> assignments,
                          Set<Placement> conflicts)

equals

public boolean equals(Object o)

Description copied from class: Constraint

Compare two constraints for equality (Constraint.getId() is used)

Overrides:

equals in class Constraint<Lecture,Placement>

createAssignmentContext

public GroupConstraint.GroupConstraintContext createAssignmentContext(Assignment<Lecture,Placement> 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

isOnline

protected boolean isOnline(Placement p)