University of Nottingham
School of Computer Science
1
Lecture 6 – Constraint Handling Techniques
•General Considerations
•Tackling Constraints
− Rejecting Infeasible Solutions
− Repairing Infeasible Solutions
− Penalising Infeasible Solutions
− Enforcing Feasible Solutions
− Treating Constraints As Objectives
Learning outcomes:
− Identify the key issues to be considered when dealing with constraints
in heuristic search
− Understand the various methods to handle constraints within
heuristic search methods
PA184 - Heuristic Search Methods
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
2
General Considerations
In optimisation problems the goal is to find the best feasible solution.
The key question when dealing with constraints is:
Should infeasible solutions be considered during the search?
or
Should infeasible solutions be rejected straight away?
The evaluation function plays a crucial role in ranking solutions both
feasible and infeasible.
The search space usually consists of
disjoint subsets of feasible (F) and
infeasible (I) solutions, although
there is no guarantee that these
subsets are connected.
search space
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
3
Issues When Dealing with Infeasible Solutions
• Evaluate quality of feasible and infeasible solutions
• Discriminate between feasible and infeasible solutions
• Decide if infeasibility should be eliminated
• Decide if infeasibility should be repaired
• Decide if infeasibility should be penalised
• Initiate the search with feasible solutions, infeasible ones or both
• Maintain feasibility with specialised representations, moves and operators
• Design a decoder to translate an encoding into a feasible solution
• Focus the search on specific areas, e.g. in the boundaries
A constraint handling technique is required to help the effective and efficient
exploration of the search space.
search space
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
4
Examples of Constrained COPs
}1,0{
(2)21for1
(1)21forsubject to
ZMaximise
knapsacktoitemassigningfor0profit
0capacityofeachknapsacks
0sizeofeachitems
1
1
1 1












 
ij
m
j
ij
n
i
jiji
m
j
n
i
ijij
ij
j
i
x
n,,ix
m,,jbxs
xp
jip
bm
sn


Multiple-knapsack problem Bin-packing problem
}1,0{and}1,0{
(2)21for1
(1)21forsubject to
Minimise
0capacityequalofeachbins
0sizeofeachitems
1
1
1












jij
m
j
ij
n
i
jiji
m
j
j
i
yx
n,,ix
m,,jbyxs
yZ
bm
sn


Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
5
School timetabling problem
0,,and}1,0{
(2)21for
(1)21for1subject to
Minimise
0costahasworkertotaskassigning
availabletime0hasworker
taskcompletetotime0takesworker
workersandtasks
1
1
1 1












 
jijijij
n
i
jijij
m
j
ij
m
j
n
i
ijij
ij
j
ij
Ttcx
m,,jTxt
n,,ix
xcZ
cji
Tj
itj
mn


Generalised assignment problem
}1,0{
(3)1;1for1
(2)1;1for1
(1)1;1fors.t.
1;1;1forFind
classmeetmustteachertimesofnumberis
rematrix wheais
timeslotsandteachersclasses,
1
1
1












ijk
m
i
ijk
n
j
ijk
p
k
ijijk
ijk
ij
nm
x
pknjx
pkmix
njmirx
pknjmix
ijr
R
pnm




Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
6
Designing the Evaluation Function
For some problems like BIN PACKING and SCHOOL TT, designing
an appropriate evaluation function to provide a good search
landscape is not trivial.
To compare solutions an ordering relation might be required instead
of a detailed evaluation function.
A common way to evaluate infeasibility is to add a component to the
evaluation function:
fitness_function(x) = evaluationfeasible(x)  evaluationinfeasible(x)
The evaluationinfeasible(x) component represents a penalty or cost and
it is also difficult to design it correctly to facilitate the search.
Key issue: to compare a feasible solution xfea and an infeasible
solution xinf when xinf is perhaps ‘next’ to the optimal solution x*.
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
7
Rejecting Infeasible Solutions
This is a simple strategy that has serious limitations particularly on
those problems where generating feasible solutions is considerably
more difficult that generating infeasible ones.
A heuristic search algorithm might need to cross between the
feasible and infeasible regions of the search space.
In local search, assessing the feasibility of neighbour solutions
might be helpful as it could help to obtain an idea of the fitness
landscape topology.
Important issue: assess
Tackling Constraints
SS
S
S
S
F
F
ofportionfeasibletheis
ionconsideratunderspacesearchtheis
where,
||
||
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
8
Enforcing Feasible Solutions
The use of specialised representations, decoders, neighbourhood
moves and reproduction operators is a reasonable way to avoid
generating infeasible solutions.
The characteristics of a good decoder are as follows:
• For each feasible solution there is an encoded one
• Each encoded solution corresponds to a feasible solution
• All feasible solutions should be represented by the same
number of encoded ones
• The decoding procedure is computationally fast
• Small changes to the encoded solution represent small changes
to the feasible solution
For example, a decoder can be used to convert a binary string into a
solution to the BIN PACKING problem.
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
9
Repairing Infeasible Solutions
This is a popular strategy to handle constraints in heuristic search
where an infeasible solution xinf is transformed into a repaired
feasible solution xrep.
Then, xrep can replace xinf or it might be that xinf remains but it is
evaluated as xrep.
It is possible that in a population-based heuristic only a number of
infeasible solutions are repaired in order to maintain diversity.
The major weakness of the repairing strategy is that is very problem
dependant.
For example, in the BIN PACKING problem a common repair
strategy would be simply to remove items from the overloaded bin to
another open or new bin.
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
10
Penalising Infeasible Solutions
The key issue is to establish the relationship between the infeasible
solution and the feasible part of the search space in order to assess
the value of the components in the infeasible solution.
xinf  Sfeasible
Penalties applied can be fixed or varied as the search progresses.
When tuning penalty functions: discrimination vs. exploration
For example, for the BIN PACKING problem a way to penalise
infeasible solutions can be to add a weighted penalty due to the
amount of exceeded capacity.
• fixed penalty for infeasibility
• penalty proportional to degree of infeasibility
• penalty proportional to cost of repairing
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
11
Some guidelines when designing constraint penalties:
• Penalties should that indicate ‘distance from feasibility’ in order
to guide the search more effectively.
• If the problem has few constraints, just counting the number of
constraint violations is generally not effective.
• Good penalty functions (static or dynamic) can be constructed by
estimating the completion cost, i.e. the increase in the cost
function (considering minimisation) incurred when transforming
an infeasible solution into a feasible one.
• There is a compromise for the accuracy of the penalty function. It
should be able to differentiate among infeasible solutions and not
be too expensive to compute.
• A compromise for the weight value associated to the violation of
each constraint should be found. Too small weights might produce
final infeasible solutions. Too large weights might provoke
convergence to suboptimal feasible solutions.
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
12
Treating Constraints As Objectives
Another strategy is to set an evaluation function for each constraint
(or group of constraints) in addition to the evaluationfitness(x) function
and then to tackle with a multi-objective approach.
This approach is particularly useful when just finding feasible
solutions is very difficult as this provides a smoother fitness
landscape for the heuristic search to operate.
It is important to choose appropriate scales for the different
objectives (maybe normalise them) so that the search is not biased.
Having several objectives then allows the application of MOO
techniques like: weighted aggregating functions, Pareto optimisation,
goal programming, etc.
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
13
What Makes a Constrained Problem Difficult?
One or several of the following aspects can make a constrained
optimisation problem difficult to tackle with heuristic search:
• Size of the problem in terms of the number of decision variables
• Number of constraints (linear, non-linear, equality, inequality, etc. )
• The size of the search space and ratio of the feasible part to the
whole.
• The fitness landscape induced by the evaluation function
• Number of local and global optima
• Etc.
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Shelf Space Allocation Problem
A block is a group of shelves
A shelf is a horizontal unit of space and can be: top level, eye-level or
bottom level
A shelf is (virtually) divided into 3 parts: left, middle and
right
Priorities are assigned to shelves and parts by the manager
Eye-level shelves and centre parts assigned the highest profitability
left middle right
top level
eye level
bottom level
14Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
For shelves and parts:
• Number
• Length
• Priority
What Data is Given?
For products:
• Length of a facing
• Maximum facings required
• Minimum facings required
• Number of available units
• Profit per unit
• Profitability according to location
Additional considerations:
• Product selection stage is not required
• Height and depth of a product unit are ignored
• Generally, all units of the same product are allocated in contiguous
space
• No elaborate product categorisation is used
15Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
A Simple Formulation
(5)and
(4)1for
(3)1for1
(2)1,1forsubject to
(1)Maximise
1 1
1 1
1
1 1 1

 
 

  









ijkijkiijkijk
i
m
j
p
k
ijki
m
j
p
k
ijk
n
i
jkijki
n
i
m
j
p
k
ijkijk
xyUxy
niUxL
niy
pkmjTxa
xZ




facingsmaximum:
facingsminimum:
facingoflength:
here)3(partsshelf:
availabeshelves:
allocatetoproducts:
i
i
i
U
L
a
pp
m
n

ityprofitabilestimated:
partshelfofpriority:
shelfofpriority:
unitperprofit:
?shelfofparttoallocatedfacings:
shelfofpartinfacings:
kjiijk
k
j
i
ijk
ijk
ρ
k
j
ρ
kjiy
kjix




16
University of Nottingham
School of Computer Science
A Tailored Heuristic Method
1. Preparatory Phase
Is there enough space to allocate all products?
  

m
j
p
k
jk
n
i
ii TaL
1 11
Product profit
Product size
Random choice
Existing arrangement
Swap
AdjustIn
MultiShift
AdjustInter
RemoveLeastProfitable
2. Allocation Phase
Produce an initial arrangement
3. Adjustment Phase
Iterative changes to improve overall profit
4. Termination Phase
Compute quality of solution and display planogram
ii aρ
ia
17Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
2. Allocation Phase
Prioritise
PS : sorted products,  order i/ai or  order ai or
random
SS : sorted shelf parts,  order of j and k
Allocate Minimum
Given: PS and SS produce arrangement 
Take next product i and next shelf part jk
Allocate Li units to shelf part jk
Allocate More
Given: PS and arrangement , improve 
Take next product i
Increment xijk by 1 ensuring feasibility (Ui and Tjk)
...
3
4
2
4
3
18Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
3. Adjustment Phase
Swap
All facings between products i1 and i2
located in different shelf parts j1k1 and j2k2
AdjustIn
For products i1 and i2 both in shelf part jk
make xi1jk = xi1jk+1 and xi2jk = xi2jk – 1
MultiShift
For products i1 and i2 both in shelf part jk
make xi1jk = xi1jk+1 and xi2jk = xi2jk – 2
3
4
2
43
443 542
3 22 5
19Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
AdjustInter
For products i1 and i2 both in shelf part j1k1 and
products i3 and i4 both in shelf part j2k2
either:
interchange i1 on shelf j1k1 with i3 on shelf j2k2
interchange i2 on shelf j1k1 with i4 on shelf j2k2
several checks made for the above interchanges
RemoveLeastProfitable
Choose a random shelf part jk and with probability
of 10%, find product i with xijk > Li contributing
least profit ijk and make xijk = xijk – 1
3
4
2
43
3
4
2
43 3
20Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Experiments and Results
Small Instance:
iUiiLtsmT
mtsapmn
i
m
j
p
k
jk
i


 
}11,,3,2{,1,33
11.0)(average,3,5,135
1 1

iUiiLtsmT
mtsapmn
i
m
j
p
k
jk
i


 
}13,,3,2{,1,248
13.0)(average,3,38,907
1 1

2. Allocation Phase Results
Current Profit Size Random
Small 78.64 77.11 (0.07) 71.36 (0.06) 71.80 (0.07)
Large 2463.05 2959.33 (3.55) 2574.38 (3.33) 2513.54 (4.07)
Large Instance:
21Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Small Instance
Current Profit Size Random
AdjustInter MultiShift MultiShift MultiShift
MultiShift AdjustIn AdjustInter AdjustInter
AdjustIn AdjustInter AdjustIn AdjustIn
Swap Swap Swap Swap
3. Adjustment Phase Results
For each initial arrangement  (current, profit, size, random)
Execute Given Move during 30 seconds x 30 times
Large Instance
Current Profit Size Random
AdjustInter AdjustIn AdjustIn MultiShift
MultiShift MultiShift MultiShift AdjustIn
AdjustIn AdjustInter AdjustInter AdjustInter
Swap Swap Swap Swap
Probabilities assigned
for the local search:
MultiShift : 35%
AdjustInter : 35%
AdjustIn : 15%
Swap : 15%
22Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Small Instance
Profit Increase Overall Profit
Mean Std.Dev. Initial Final
29.06 (37%) 0.77 78.64 107.71
30.93 (40%) 0.93 77.19 108.04
37.19 (52%) 0.83 71.36 108.55
36.25 (50%) 0.52 71.80 108.05
For each initial arrangement  (current, profit, size, random)
Execute Adjustment Phase for t seconds x 15 times
Large Instance
Profit Increase Overall Profit
Mean Std.Dev. Initial Final
2386.3 (97%) 51.1 2463.0 4849.3
1869.7 (63%) 27.5 2959.3 4829.1
2391.4 (93%) 23.9 2574.3 4965.8
2191.7 (8%) 36.0 2513.5 4705.2
23Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
We refer to nurse scheduling or nurse rostering as the process
of timetabling staff (allocating nurses to working shifts) over a
short period of time (typically few weeks).
Typically, the aim is to produce a roster for the ward over the
planning period, so that all hard constraints are satisfied and
the violation of soft constraints is minimised.
In particular, we aim to maximise satisfaction of individual
preferences.
THE QMC NURSE SCHEDULING PROBLEM
24Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Hard constraints:
– OneShiftADay
– MaxHours
– MasDaysOn
– MinDaysOn
– Succession
– HardRequest
Soft constraints:
– SoftRequest
– SingleNight
– WeekendBalance
– WeekendSplit
– Coverage
– Coverage Balance
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Ward Schedule = collection of n individual nurse schedules
NurseSchedule(i) = {s(i,j): 1  j  NoOfDays}
s(i,j)  {AnnualLeave, DayOff, Early, Late, Night}
Encoding(i) = Permutation{shift : 1  shift  3NoOfDays}
NursePreference(i) = {p(i,j): 1  j  NoOfDays}
p(i,j)  {AnnualLeave, Any, DayOff, Early, Late, Night}
26
University of Nottingham
School of Computer Science
Example of preference and constructed schedules
27
University of Nottingham
School of Computer Science
Day=(x−1) div 3 + 1, Shift=(x−1) mod 3
Early, Late, Night correspond to 0, 1, 2 respectively
For example, for x = 7:
D=(7 – 1) div 3 + 1 = 3 S=(7-1) mod 3 = 0
Then assign Early shift to day 3
Decoder
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
1. Assigning shift 4 (Early shift to day 2) violates the Succession constraint
2. High Soft-Request-Probability forces decoder to use preference schedule
3. Assigning Late shift to day 2 is allowed
4. Self-mutation to the current permutation list to swap shift 4 and shift 5
Self-mutation to deal with Succession hard constraint
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
1. Assigning shift 12 (Night shift to day 4) violates the Succession constraint
2. Low Soft-Request-Probability forces decoder to use permutation list
3. Search permutation list and assign shift 10 (Early shift to day 4) is allowed
4. Self-mutation to the current permutation list to swap shift 10 and shift 12
Self-mutation to deal with Succession hard constraint
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
The QMC nurse scheduling is certainly multi-criteria but should
it also be treated as a multi-objective problem?
E.g. in product design:
multiple criteria: cost, reliable, profitable, durable
is the above a 4-objective problem in the Pareto sense?
Hard constraints
- OneShiftADay
- MaxHours
- MaxDaysOn
- MinDaysOn
- Succession
- HardRequest
Soft constraints
- SoftRequest
- SingleNight
- WeekendBalance
- WeekendSplit
- Coverage
- Coverage Balance
work regulations
coverage demand
nurse preferences
31Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
March2001
0
300
600
900
1200
1500
0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000
Work Regulations
CoverageDemand
March2001
0
50
100
150
200
250
300
350
400
0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000
Work Regulations
NursePreferences
March2001
0
500
1000
1500
2000
2500
3000
3500
4000
4500
5000
0 100 200 300 400 500 600 700 800
Coverage Demand
WorkRegulations
March2001
0
50
100
150
200
250
300
350
0 100 200 300 400 500 600 700 800
Coverage Demand
NursePreferences
32Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Overall conflicting nature of criteria in the QMC problem
Group WR Group CD Group NP
Group WR ------ conflict conflict
Group CD independent ------
Group NP independent independent ------
Conflict, independence and harmony between criteria may
vary during the search
Hence, the search strategy can be adapted to this variation
33Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
Initial SWO SWO + CS
Mar-01 819 0 0
Apr-01 953 266 205
May-01 1875 618 577
Jun-01 1801 1468 1409
Jul-01 2005 1734 1473
Aug-01 786 330 40
Sep-01 1129 619 495
ND Group WR Group CD Group NP AverSimil
Mar-01 6.767 3.390 4.664 2.41 49.2%
Apr-01 7.700 3.027 8.219 2.25 51.6%
May-01 6.933 2.943 15.132 1.93 57.7%
Jun-01 3.933 0.892 38.615 2.50 62.0%
Jul-01 7.900 2.173 38.725 2.68 54.2%
Aug-01 7.200 3.555 7.528 1.90 53.7%
Sep-01 7.467 2.611 18.520 2.07 56.7%
Some results…
34Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
35
Additional Reading
Chapter 9 of (Michalewicz,2004) and Section 1.5 of (Talbi,2009).
D. Landa-Silva, K.N. Le (2008). A simple evolutionary algorithm with
self-adaptation for multi-objective optimisation. In: Cotta, C., S. M. &
Srensen, K. (eds.) Adaptive and multilevel metaheuristics, Series
'Studies in computational intelligence', Vol. 136, Springer, 133-155.
E. K. Burke, P. de Causmaecker, S. Petrovic, G. Vanden berghe (2001).
Fitness evaluation for nurse scheduling problems. Proceedings of the
2001 Congress on Evolutionary computation (CEC 2001), 1139-1146.
A. Viana, J.P. de Sousa, M.A. Matos (2003). GRASP with constraint
oriented neighbourhoods: an application to the unit commitment
problem. In: Proceedings of the 5th Metaheuristics International
Conference (MIC 2003), 78:1-78:8.
Heuristic Search Methods
Dr Dario Landa- Silva
University of Nottingham
School of Computer Science
36
Seminar Activity 6
The purpose of this seminar activity is to discuss the suitability of
constraint handling techniques for the GAP variant of Example 2.1.
Do the following:
1. Look at the instances of the GAP variant and estimate the
proportion of feasible and infeasible solutions.
2. Discuss the suitability of various constraint handling techniques in
the context of this problem, including:
a) Rejecting infeasible solutions
b) Enforcing feasibility using specialised moves
c) Repairing infeasibility using specialised strategies
d) Penalising infeasible solutions
e) Using constraint-oriented neighbourhoods
Heuristic Search Methods
Dr Dario Landa- Silva