Combinatorial Optimisation
Optimisation of smooth linear well-behaved functions and
systems is relatively straightforward using calculus or
standard numerical techniques, such as gradient descent.
However, most combinatorial optimisation problems are
highly variable, non-linear, poorly-behaved and suffer from
combinatorial explosion in the search space, basically the
number of permutations or ways of arranging the solution is
factorial in the number of elements. Poorly-behaved, in
this case, means that one small change to the arrangement
in a good solution, can result in a very poor solution;
there is no guarantee of similarity of solutions in a
neighbourhood of the search space, so conventional linear
optimisation approaches generally are not applicable.
Well known, easily stated, easily visualised geometrically,
but difficult to solve optimally (NP), examples include:
Travelling Salesman Problems and variations.
Knapsack, Bin-Packing & Set-Partitioning,
Stock-cutting, container-loading and scheduling Problems
Steiner Minimum Tree Problems
Various approaches to obtain optimal solutions, but at
great computational cost include
- branch & bound - basically a combinatorial search
within strictly controlled upper and lower bounds;
- cutting plane methods which model or constrain the
problem as an integer programming problem and solve it
using applicable methods.
However alternative methods exist.
Heuristics which give good solutions quickly, and it's
probably not worth the effort to get a better one;
Genetic algorithms - which perform a
progressively selective less randomised search;
Cellular automata / agents - where
distributed partly intelligent optimisation approaches
are attempted.
Swarm intelligence, which effectively
attempt a globally optimal combination of locally
optimal solutions
Neural networks have also been used to
as optimisers either as pattern classifiers or
intrinsically through their minimising the error
function.
Some results from information theory also provide good
guidelines for developing optimal algorithms.
Projects.
Optimisation problems themselves present a worthy and
challenging project category. Some of the more common
problems and techniques are mentioned above, but others can
be attempted.
Additionally, optimisation pervades most computer
application areas and can be a component of many of the
other project categories. Additionally, optimisation
techniques are applicable to the efficient allocation of
time and space resourcs for fast execution of code on a
computer, whether at instruction or program level.
Even a simple appointments booking system may require some
degree of optimisation in the space and time (scheduling)
allocation.
Obviously, one can attempt to use optimising techniques
themselves in the generation of optimising algorithms, but
can expect mixed results.