OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.
A full list of the topics available in OR-Notes can be found here.
So far we have considered ways of solving IP's optimally. As mentioned previously it may be that we are not interested in the optimal solution:
In such cases we can use a heuristic algorithm - that is an algorithm that should hopefully find a feasible solution that, in objective function terms, is close to the optimal solution. In fact it is often the case that a well-designed heuristic algorithm can give good quality (near-optimal) results.
As an example consider the following problem: 3 men are to be assigned to 3 jobs - where the assignment cost is given by the matrix below:
Job
1 2 3
Man A 1 3 4
B 3 7 4
C 3 4 2
Only one man can be assigned to one job and all the men should be assigned. What would be a heuristic algorithm for this problem? (For a solution see below).
Note that this problem is called the assignment problem.
We should stress here that a heuristic algorithm should be capable of being applied to the problem even if the costs in the above matrix are changed (i.e. a heuristic algorithm is a set of general rules for solving the problem that are independent of the particular data case being considered).
The principal advantages of heuristic algorithms are that such algorithms are (often) conceptually simpler and (almost always) much cheaper computationally than optimal algorithms.
One (simple) heuristic for the assignment problem would be: choose a man and a job at random. Assign the chosen man to the chosen job. Delete the chosen man and the chosen job from the problem and repeat with this new (smaller) problem.
This heuristic does not use any of the cost information and so we would not expect it to give very good results.
Note however the idea of repetition. This is a common concept in heuristic algorithms (both because it eases the task of programming the heuristic, and because if a certain algorithmic step is a good idea then why not repeat it?).
A better heuristic might be: choose the smallest cost in the cost matrix (ties broken arbitrarily) and assign the corresponding man to the corresponding job - delete them from the problem and repeat with this new (smaller) problem.
This heuristic would give the solution:
Cost 1 Assign A to job 1 Cost 2 Assign C to job 3 Cost 7 Assign B to job 2 Total cost 10
This illustrates a problem that often occurs with heuristics in that by the third assignment (of B to job 2) we have been "painted into a corner" by previous assignments and have little or no choice left (with the result that we have to assign B to job 2 at relatively high cost).
Because of this problem a common idea with heuristics is the concept of interchange - the basic idea here is to juggle with the current solution to see if we can improve it e.g. with the solution above could we improve it by, for example, swapping the assignments of A and C thereby assigning A to job 3 and C to job 1? Here this swap is not worthwhile but some swaps (interchanges) are e.g. swap the assignments of A and B.
Heuristic algorithms for integer programming problems are widespread in the literature and applied quite widely in practice.
Note particularly here that we designed the above heuristic without ever having a mathematical formulation of the problem.
With regard to heuristics we have a number of generic approaches in the literature, for example:
By generic here we mean that there is a general framework/approach from which to build an algorithm. All of these generic approaches however must be tailored for the particular IP we are considering. In addition we can design heuristics purely for the particular problem we are considering (problem-specific heuristics).
Heuristics for IP's are widespread in the literature and applied quite widely in practice. Less has been reported though in terms of heuristics for MIP's.