From GPWiki

Note that this article covers Combinatorial Optimisation problems that occur in Game Programming, and gives an abtract overview of algorithms to solve them - specific algorithms (like Genetic Algorithm) and their implementations are covered in separate articles.

Introduction

Combinatorial Optimisation (CO) is a field that covers a wide variety of mathematic problems, but, in summary, it deals with finding the best (or optimal) combination of choices from a given set of options. Within Computer Science, CO generally falls under the auspices of Artificial Intelligence, and is used to aid AI's in making decisions.

Example

If my AI has entered a shop and wishes to purchase some items, we must find an algorithm to choose the best combination of items to buy, given their cost, effective value, and so on.

Solution Vector

Our first task is to find a way to describe our choice - that is, a way of representing how many of which items our algorithm has chosen to buy. As we are shopping, the best way to do this would be a shopping list, so, if the shop contains items A, B & C, we could represent a given shopping list with the three-dimensional vector (that is, an array of length three), with one dimension for each item. If we chose to buy two of item A, no Bs and one C, our solution vector would be: (2,0,1)

Objective Function

Now, as we are trying to find the 'best' selection of items to buy, we need to define the concept of best, and we do this with a value function which takes our shopping list and returns a real number that signifies how valuable that shopping list is. Let's say that items A, B and C are healing potions - A is a large potion and heals 50HP, B is a medium and heals 20HP and C is a small potion that heals 5HP. If we say that the value of our shopping list is the total number of HP it can heal, then our value function (refered to as f()) is nice and simple. The value of our shopping list above is f((2,0,1)) = 2 * 50 + 0 * 20 + 1 * 5 = 105. If we remove a small potion (C) from that shopping list, the value drops to 100 - so we can say that the shopping list is better before removing the potion than after. Note that the value function is generally refered to as the objective function, though different problems may have a specific name for it.

Constraints

So far, things have been pretty simple - if we told our AI to go shopping with the problem we have so far, the best shopping list would be to buy all the potions in the shop, as that would be the most valuable. However, as neither life nor capitalism is that kind, we have to accept that there is a cost for each item we buy - therefore, the amount of money we have to spend acts as a constraint. If the cost of A is 50GP, B is 25GP, and C is 10GP, it is obvious that larger potions are better value for money - potion A gives 1HP per 1GP, whilst C gives 1HP per 2GP spent. If we then set our total gold to 100GP, the best shopping list is again obvious - (2,0,0), giving 100HP for 100GP. If, however, we reduce the gold available to 75, (2,0,0) becomes more than we can afford, and is thus infeasible. Instead, the optimal solution is (1,1,0), giving 70HP for our 75GP.

To be continued...