Knapsack (Binary Variables) - Handbook

Type: BIP (Binary Integer Programming)

This handbook explains the Knapsack sample problem in the LP Black Box platform.

This is one of the most famous optimization problems and demonstrates the use of Binary variables.

---

The Problem

Scenario

Select items to pack in a knapsack with a weight limit. Each item has a value and weight.

Item	Value ($)	Weight (kg)
Item 1	60	10
Item 2	100	20
Item 3	120	15
Item 4	80	8
Item 5	50	5

Weight Limit: 30 kg

Your Goal

Maximize total value while staying within weight limit.

The Key: Binary Variables

Each item is either:

• Selected (1) - put in the knapsack
• Not selected (0) - left behind

This is why we use Binary variable type - you can only choose 0 or 1, not partial quantities.

The Variables

Variable	Type	Meaning
item1	Binary (0 or 1)	Is item 1 selected?
item2	Binary (0 or 1)	Is item 2 selected?
item3	Binary (0 or 1)	Is item 3 selected?
item4	Binary (0 or 1)	Is item 4 selected?
item5	Binary (0 or 1)	Is item 5 selected?

The Constraints

1. Weight Limit: Total weight cannot exceed 30 kg

   Formula: 10×item1 + 20×item2 + 15×item3 + 8×item4 + 5×item5 ≤ 30

---

How to Use

Step 1: Load the Sample

Select Knapsack (Binary Variables) from the dropdown.

Step 2: Solve

The solver determines which items to select for maximum value within the weight limit.

Step 3: Interpret Results

The solution will show:

• item1 = 1 means item 1 is selected
• item2 = 0 means item 2 is not selected

---

Try It Yourself

• Change the weight limit to 25 kg
• Add a constraint that you must select at least 2 items

---

Why Binary Matters

Binary variables are used for yes/no decisions:

• Select or don't select an item
• Open or close a facility
• Hire or not hire an employee
• Include or exclude an investment

This makes LP capable of solving discrete optimization problems, not just continuous ones.

---

This demonstrates how Linear Programming with Binary variables can solve classic combinatorial optimization problems.