Discrete Optimization

Wed 23 May 2018

What is it?

NP-Hard problems or problems that have no algorithm to efficiently find an optimal solution.

The Knapsack Problem

Here the goal is to fit as many items in a knapsack as possible and optimize the value of the total items in the knapsack. For instance if the knapsack holds 20kg and there are items $10@10kg, $20@20kg which combination of items will give us the optimized value constrained by the size of the knapsack?

Greedy Algorithms

Take items according to a single metric and in order. For example take items according to weight until the knapsack is full, take items according to value until full or take items by a new metric, value per kg, until full.

Greedy Algorithms is fast and gives a baseline, or a solution to try and beat when exploring other methods.

Optimization Model

  • Decision Variables
  • Variable Constraints
  • Objective Function