# Heuristics¶

The mathematical problem described in Mathematical model can be solved
using linear programming which is guaranteed to give the optimal solution. This
can be computationally expensive, thus `conference_scheduler`

includes the
ability to search the solution space in an efficient manner to obtain if not the
best solution: a very good one.

A good overview of the main ideas behind these types of algorithms can be found in [Aarts1997].

One subset of these types of algorithms is called neighbourhood searches. This
involves defining a neighbourhood of a candidate solution. In
`conference_scheduler`

, the neighbourhood of a matrix \(X\) is defined
as the matrix that corresponds to moving a single event to another slot. If the
new slot is currently being used by another event the two events are swapped.

The general format of a neighbourhood search is to randomly select an element in the neighbourhood of \(X\) and either accept it or not as the new current solution according to a given criteria.

## Hill climbing¶

The Hill climbing algorithm has the most elementary acceptance criteria for a new solution. If the new solution has a better score then it is accepted.

The downside to this greedy approach is that by immediately accepting the better solution the algorithm can arrive at a local optimal: a hill top that is not the highest hill.

Note that the objective functions used in `conference_scheduler`

are
minimised. Whilst, mathematically this is equivalent, the analogy of finding the
highest hill through hill climbing fails and we are in fact looking for the
lowest valley.

## Simulated annealing¶

This algorithm will accept a worse solution with a given probability. However this probability will decrease over time. Thus, the algorithm spends time at the beginning exploring the search space before beginning to hone in to a better solution. The name of this algorithm comes from the concept of annealing in metallurgy. A good overview of this is given in [Henderson2003].

This in essence allows our search to “jump” away from local optima.