Computer Science 15

There are many ways we can create models to solve problems. The generalized process is as shown:
1) Start with an experiment in which we gather data.
2) Use computation to find and evaluate a model.
3) Use theory, analysis and computation to derive a consequence of the model.

Optimization Problems involve writing programs to optimize real-life scenarios. Each Optimization Problem consists of an Objective Function and a set of Constraints that has to be satisfied. The Objective Function is used to compare and find the optimal results, while Constraints are rules that must be obeyed (for example, in the case of navigation, Constraints can be in the form of limiting to only pedestrian routes).

Once we come up with these things, we can use computation to attack the problem. A way to solve seemingly new problems is to attempt to map these problems to classic problems that we already know how to solve. This is known as Problem Reduction.

Optimization Problems typically take a long time to solve. Often, there is no computationally efficient way to solve them. Therefore, it is common that we see "Best Effort" results.

A classic Optimization Problem is the Knapsack Problem. The problem is typically discussed in the context of a burglar. One of the problems a burglar must deal with is deciding what to steal. There is usually far more to steal than you can carry away. The Objective Function must optimize the value of what we steal, with the Constraint of the maximum weight or volume we can carry in the knapsack.

Suppose that the burglar has done his research on the house and finds out that these are the objects of interest:

Item	Value	Weight
Desktop	$1500	10Kg
Laptop	$1200	1.5Kg
LED TV	$1000	10Kg
Smartphone	$750	0.25Kg
Ring	$1000	0.01Kg
Piano	$6000	180Kg
HiFi Set	$500	5Kg
PSP	$300	0.5Kg

(Here I'm saying Weight in a general sense, don't tell me it should be Mass instead. I know :p)

One of the easiest solution is to implement a Greedy Algorithm. A Greedy Algorithm is iterative, and at each step, the locally optimal solution is picked. What we need to know is to find out what is considered "locally optimal". It can be the best price/weight ratio, or the highest raw value that can still fit into the bag, or the item with the least weight. There is no guarantee that each variable is the best. Therefore, the biggest problem with the Greedy Algorithm is that we have no single best "locally optimal" that would work most of the time for the 0/1 Knapsack Problem.

The term 0/1 refers to the fact that we can't take half an item. It's either the full item, or we don't take it. Greedy Algorithm, however, is the best for Continuous Knapsack Problem. Take for example, if we break into a smith shop and find barrels of gold, silver and other precious metals. We can then work by filling up with gold first, then silver, then the other metals, and when we finally run out of space, we can take a partial barrel. However, most problems in life are 0/1 Knapsack problems.

Let's create a quick object that allows us to define what an item is:

class Item(Object):
    def __init__(self, name, value, weight):
        self.name = name;
        self.value = float(value);
        self.weight = float(weight);

    def getName(self):
        return self.name

    def getValue(self):
        return self.value

    def getWeight(self):
        return self.weight

    def __str__(self):
        return str(self.name)+", $"+str(self.value)+", "+str(self.weight)+"Kg"

We then instantiate the items based on the above table:

def instantiateItems():
    names=["Desktop","Laptop","LED TV","Smartphone","Ring","Piano","HiFi Set","PSP"]
    values=[1500,1200,1000,750,1000,6000,500,300]
    weights=[10,1.5,10,0.25,0.01,180,5,0.5]
    items=[]
    for i in range(len(names)):
        items.append(Item(names[i],values[i],weights[i]))
    return items

At this point we should have a list of items ready for us to work with. We then come up with the greedy algorithm that does all these. The Greedy Algorithm should accept a list of items, the maximum weight that a person can carry, and the function used for comparison.

Here is the Greedy Algorithm:

def greedy(items, maxWeight, keyFunction):
    itemsSorted = sorted(items, key=keyFunction, reverse=True)
    knapsack=[]
    totalValue=0.0
    totalWeight=0.0
    for item in itemsSorted:
        if totalWeight+item.getWeight()<maxWeight:
           knapsack.append(item)
           totalValue+=item.getValue()
           totalWeight+=item.getWeight()
    return knapsack, totalValue, totalWeight

def value(item):
    return item.getValue()

def weight(item):
    return item.getWeight()

def vwRatio(item):
    return item.getValue()/item.getWeight()

A little explanation here about the formal parameter keyFunction. The Key Function is a function of 1 formal parameter that the sorted() function would use to compare the items in the list. value(), weight() and vwRatio() are examples of Key Functions. Using value() as the keyFunction, for example, would compare whatever is returned by the item.getValue() of all the items.

Let's test the Greedy Algorithm now:

def printResults(knapsack,totalValue,totalWeight):
    for item in knapsack:
        print(item)
    print("Total Value: $"+str(round(totalValue,2)))
    print("Total Weight: "+str(round(totalWeight,2))+"Kg")

def testGreedy():
    items=instantiateItems()
    knapsack,totalValue,totalWeight=greedy(items,22.5,value)
    print("Using value as the key function:")
    printResults(knapsack,totalValue,totalWeight)
    knapsack,totalValue,totalWeight=greedy(items,22.5,weight)
    print()
    print("Using weight as the key function:")
    printResults(knapsack,totalValue,totalWeight)
    knapsack,totalValue,totalWeight=greedy(items,22.5,vwRatio)
    print()
    print("Using vwRatio as the key function:")
    printResults(knapsack,totalValue,totalWeight)

Assuming our burglar has a knapsack that can carry only up to 22.5Kg of things, here's the results:

Using value as the key function:
Desktop, $1500.0, 10.0Kg
Laptop, $1200.0, 1.5Kg
LED TV, $1000.0, 10.0Kg
Ring, $1000.0, 0.01Kg
Smartphone, $750.0, 0.25Kg
PSP, $300.0, 0.5Kg
Total Value: $5750.0
Total Weight: 22.26Kg

Using weight as the key function:
Ring, $1000.0, 0.01Kg
Smartphone, $750.0, 0.25Kg
PSP, $300.0, 0.5Kg
Laptop, $1200.0, 1.5Kg
HiFi Set, $500.0, 5.0Kg
Desktop, $1500.0, 10.0Kg
Total Value: $5250.0
Total Weight: 17.26Kg

Using vwRatio as the key function:
Ring, $1000.0, 0.01Kg
Smartphone, $750.0, 0.25Kg
Laptop, $1200.0, 1.5Kg
PSP, $300.0, 0.5Kg
Desktop, $1500.0, 10.0Kg
LED TV, $1000.0, 10.0Kg
Total Value: $5750.0
Total Weight: 22.26Kg

As you can see, there is no single best Key Function that we can use. In the end it's all up to the situation and we must look at every single one to know what is the best. Since it's called Greedy Algorithm, there is definitely some sort of Order of Complexity associated with it.

The implemented algorithm is divided into two parts: Sorting, then Comparing.

We can assume that the sorting is some variant of the Merge Sort, of which we have:
O(len(items)*log(len(items))) or otherwise O(n log n)

The comparison part is just a for loop that runs a maximum of len(items) times. Therefore we have:
O(len(items)) or otherwise O(n)

Taking the worst case, the Order of Complexity of the algorithm is O(n log n).

However, it is important to note that what we have may not be the absolute optimal we can have.

If we formulate a problem well enough, it would definitely be apparent that it can be solved in a bruteforce way. The biggest trouble is whether it is feasible or not. Fortunately, bruteforce is feasible for small 0/1 Knapsack Problems.

Suppose that we have these 8 items. The maximum combination of items that we can take is:
2⁸ = 256

We can then run a bruteforce algorithm to go through every single possible combination to find out what is the maximum [Sum of Value] where [Sum of Weight] is below maximum weight. In other words:
Objective Function - Maximum [Sum of Value]
Constraint - [Sum of Weight] Below or Equal to Maximum Weight

The Order of Complexity for such an algorithm is:
O(len(items)**2) or O(n²)

Of course, if we're doing just 8 items, we have 256 different combinations. However, what if we have a list of 50 items. That would be 1125899906842624 item combinations. Even if the computer could generate a combination in a nanosecond, it would take 36 years to complete.

Just for kicks, here's the bruteforce algorithm to solve this:

def brange(integer):
    binary=bin(integer)[2:]
    brange=[]
    for i in range(len(binary)):
        if binary[len(binary)-i-1]=='1':
            brange.append(i)
    return brange
   
def bruteForceKnapsack(items,maxWeight):
    combinations=[]
    values=[]
    weights=[]
    maxValue=0.0
    for combination in range(2**len(items)):
        currentWeight=0.0
        currentValue=0.0
        for i in brange(combination):
            currentWeight+=items[i].getWeight()
            currentValue+=items[i].getValue()
        if currentWeight<=maxWeight:
            if maxValue<currentValue:
                combinations=[]
                values=[]
                weights=[]
                maxValue=currentValue               
                combinations.append(combination)
                values.append(currentValue)
                weights.append(currentWeight)
            elif maxValue==currentValue:
                combinations.append(combination)
                values.append(currentValue)
                weights.append(currentWeight)
    return combinations,values,weights

def testBruteForceKnapsack():
    items=instantiateItems()
    combinations,values,weights=bruteForceKnapsack(items,22.5)
    print("For a maxweight of 22.5:")
    for i in range(len(combinations)):
        for j in brange(combinations[i]):
            print(items[j])
        print("Total Value: $"+str(round(values[i],2)))
        print("Total Weight: "+str(round(weights[i],2))+"Kg")
        print()

The brange() function returns a list of 1's in an integer converted to binary. For example, 10 when converted to binary is 1010. It would return 1 and 3 which are the location of the 1's. This algorithm goes through all possible combinations. If there's a better combination than one it currently knows, it would replace all previous combinations. If there's a combination that gives the same value as the one it currently has, it would append it to the list. Here's some output:

For a maxweight of 22.5:
Desktop, $1500.0, 10.0Kg
Laptop, $1200.0, 1.5Kg
LED TV, $1000.0, 10.0Kg
Smartphone, $750.0, 0.25Kg
Ring, $1000.0, 0.01Kg
PSP, $300.0, 0.5Kg
Total Value: $5750.0
Total Weight: 22.26Kg

Here we see that the Greedy Algorithm got lucky. Its Best Effort results were correct! If we work with a different set of items the Greedy Algorithm results may not be as optimal, but the Brute Force it will definitely give you the best, or a set of best results.

Brute Force, of course, is unscalable. In the next article we will look at other ways we can find such results.

Here's graphically how much we can steal from the house:



As you can see, optimally 28Kg is minimum to steal mostly everything. You'll have to add more than 150Kg to your maximum load in order to start steal more.