Optimization searches for the best solution among many valid possibilities. Each solution differs in how well it satisfies a goal and its constraints. section 1.9
Optimization is useful whenever a complex problem has historical data or a large search space. The best nearby solution may not be the best overall: a local best can hide a global best. section 1.24 section 1.9
Optimization problems commonly involve:
- Many valid solutions, with some more effective than others. section 4.2
- Constraints that rule out otherwise attractive choices. section 1.9
- Search traps called local optima, where a single searcher can stop too early. section 4.2
- Trade-offs between solution quality and computational expense. section 4.2
A constrained knapsack
A knapsack holds at most 9 kg. Among eight items, choose a combination that maximizes value without exceeding that limit. Items 1, 3, and 7 weigh 9 kg and are worth $14; items 2, 3, and 6 are worth $15 but weigh 15 kg, so they violate the constraint. The example contains 256 possible choices, illustrating how possibilities grow as the number of items increases. section 4.2
Figure 4.4 A simple example Knapsack Problem
Use the simple knapsack diagram to see how capacity, item selection, weight, and value define an optimization problem. section 4.2
