Computational Models

• Computational models use computer programs to simulate and study complex systems.
• These models are used in physics, engineering, chemistry, biology, economics, psychology, cognitive science, and computer science.
• Computational models can augment or replace experiments, especially for systems too complex for analytical study.

Types of Computational Models

• Optimization models
• Statistical models
• Simulation models

Uses of Computational Models

• Model and understand past events such as modelling how the climate has changed over the last several millennia.
• Make predictions about the future such as predicting the future climate.

Optimization Problems

• Can be solved by mapping the problem onto an optimization problem.
• An optimization problem is used to find the best solution to a problem.
• "Best" solution can be defined as biggest, smallest, most, fewest, fastest, or least expensive.
• If one knows the solution to the optimization problem, it can be used to solve the original problem.
• Consist of two parts: an objective function and a set of constraints that must be satisfied.
• Objective function can be maximized or minimized.
  • Examples include minimizing travel time or airfare between two locations.
• Constraints are conditions that must be met.
  • Examples include having a maximum budget, needing a travel time of less than a set amount of hours, or having to arrive before a set time.
• Solved by services like Google Maps and Expedia.

Knapsack Problem

• Classic optimization problem involving a burglar with a knapsack.
• The burglar seeks to maximize the total value of stolen items.
• The house has items of greater value than the burglar can carry.
• The objective function is the total value of the stolen items.
• The constraint is that the stolen items must be able to be carried in the knapsack.

Knapsack Problem Variants

• 0/1 Knapsack: Burglar either takes an item entirely or leaves it.
• Fractional/Continuous Knapsack: Burglar can take any fraction of an item.

0/1 Knapsack Example

• A burglar's knapsack can hold at most 20 kilograms worth of items.
• House contains the following items: clock, painting, radio, vase, book, and computer.
• Their values, weights and value/weight ratios vary.
  • Clock : value of 175, weight of 10, ratio of 17.5
  • Painting: value of 90, weight of 9, ratio of 10
  • Radio: value of 20, weight of 4, ratio of 5
  • Vase: value of 50, weight of 2, ratio of 25
  • Book: value of 10, weight of 1, ratio of 10
  • Computer: value of 200, weight of 20, ratio of 10

Greedy Algorithms

• At each step, the best remaining move is made
• This is the simplest way to find an approximate solution to the knapsack problem.
• The burglar chooses the best item first, then the next best, until the knapsack is full or no other items are possible.
• "Best" item can be most valuable, least heavy, or highest value-to-weight ratio.
• Different definitions of "best" can yield different solutions.
• Solutions are not guaranteed to be optimal.

Greedy Algorithms according to Value

• If "best" is most valuable, only the computer is taken.
  • It has a value of $200 and weight of 20 kg, so there is no available weight.
  • Total value of stolen items is $200.

Greedy Algorithms according to Weight

• If "best" is least heavy, items will be taken in the following order - book, vase, radio, and painting.
  • The book has a value of $10 and weight of 1 kg leaving 19 kg of available weight.
  • The vase has a value of $50 and weight of 2 kg leaving 17 kg of available weight.
  • The radio has a value of $20 and weight of 4 kg leaving 13 kg of available weight.
  • The painting has a value of $90 and weight of 9 kg leaving 8 kg of available weight.
  • Total value of stolen items is $170.

Greedy Algorithms according to Value to Weight Ratio

• If "best" is highest value-to-weight ratio, items will be taken in the following order - vase, clock, book, and radio
  • The vase has a value of $50 and weight of 2 kg leaving 18 kg of available weight.
  • The clock has a has a value of $175 and weight of 10 kg leaving 8 kg of available weight.
  • The book has a has a value of $10 and weight of 1 kg leaving 7 kg of available weight.
  • The radio has a has a value of $20 and weight of 4 kg leaving 3 kg of available weight.
  • Total value of stolen items is $255.

Representing Items with Python Class

• Class name called Item(object)
• It will use the following def functions:
  • __init__(self, name, value, weight)
  • getName(self)
  • getValue(self)
  • getWeight(self)
  • __str__(self)

Representing Definitions of "Best" using Functions

• Uses Python, and includes:
  • def value(item)
  • def weightInverse(item)
  • def density(item)
• The smallest weight will have the largest inverse weight, similar to the largest value and largest value-to-weight ratio.

Implementing the Greedy Algorithm

• Can be implemented as follows in Python:
  • def greedy(items, maxWeight, keyFunction)
  • keyFunction maps elements of items to numbers
• The items are then sorted, and a result list and total values are assigned
• The keyFunction parameter allows for different definitions of "best" to be used

Algorithmic Complexity

• Python's sort is roughly O(n log n) where n is the length of items.
• The loop is O(n).
• The whole function is O(max(n log n, n)) = O(n log n).

Testing the Greedy Algorithm

• We can build the list of items in the house using the code below:
  • def buildItems():
  • Includes function defs for names, values, weights and the items in a list

Testing the Greedy Algorithm with Provided Item Ordering

• Test the greedy algorithm with a provided item
  • def testGreedy(items, constraint, keyFunction)

Measure of "Best" Algorithm

• Can test the greedy algorithm with each measure of "best" using the code below:
  • def testGreedys(maxWeight=20)

Brute Force Algorithm

• The 0/1 knapsack problem can be formalized by:
  • Representing each item by a pair, (value, weight).
  • The knapsack has a maximum weight capacity, w.
  • A vector, I, of length n, that represents the set of available items, where each element of the vector is an item.
  • A vector, V, of length n, is used to indicate which items are stolen by the burglar. -If V[i] = 1, then item I[i] is taken. -If V[i] = 0, then item I[i] is not taken.
• The goal is to find a V that maximizes the sum of V[i] * I[i].value.
• It needs to be subject to the constraint that the sum of V[i] * I[i].weight is less than or equal to w.

Brute Force Algorithms cont.

• Force solution tries all possible combinations of items to find the best one
• All possible combinations of items are generated as the power set of the set of items.
• Combinations of items whose total weight exceeds the allowed weight are removed.
• Returns the combination of items with the highest total value among the remaining combinations.
• The brute force algorithm guarantees the optimal solution, but is too slow for large sets due to 2^n possible combinations.
  • Represented using a bit string where 1 indicates element is in the subset, and 0 indicates element is not.
• We can obtain the bit string corresponding to a non-negative integer using the code below:
  • def getBinaryRep(n, numDigits)

Brute Force Algorithm Power Sets

• The power set of a set of items can be obtained
  • def genPowerset(L)

Best Combination of Items

• The best combination of items from the power set can be located with a set maximum weight:
  • def chooseBest(pset, maxWeight, getVal, getWeight)
  • getVal and getWeight parameters get the value and weight of items

Brute Force Algorithm cont.

• Given chooseBest(pset, maxWeight, getVal, getWeight) from before:

  • The outer loop is O(2^n) where n is the number of items, since the power set has 2^n elements.
  • The inner loop is O(n).
  • The whole function is O(n 2^n).

• Finds the optimal solution for a set of items :

  • def testBest(maxWeight = 20)

• The 0/1 knapsack problem is inherently exponential in the number of items, with the brute force algorithm presented as O(n 2^n).

Greedy Algorithms vs Brute Force Algorithms

• The greedy algorithm makes the "best" local choice at each step resulting in a locally optimal solution.
• This does not guarantee a solution that is globally optimal
• The brute force algorithm is guaranteed to find the globally optimal solution.
• Greedy algorithms are easier to implement and have shorter run times.
• Often greedy algorithms are used in practice when a "good enough" solution is acceptable.

Fractional Knapsack Problem

• A greedy algorithm is guaranteed to find an optimal solution.
• Take as much as possible of the item with the highest remaining value-to-weight ratio.
• The burglar should start with gold dust, then silver dust, then raisins until the knapsack is full.