Discrete Optimization

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