optimization problem

An optimization problem asks not just for a valid solution but for the best one. Many valid routes get you across town; the optimization problem wants the shortest. Many ways pack items into a bag; the optimization problem wants the most valuable that still fits. There is an objective — a number we are trying to make as small or as large as possible — and among all the allowed (feasible) solutions, we want one that hits the extreme value of that objective.

Precisely, an optimization problem has three parts: the feasible solutions (which candidates are even allowed), the objective function (the number we score each candidate by), and the direction (minimize or maximize). The answer is a feasible solution whose objective is optimal — no feasible solution does better. For the shortest-path problem, feasible solutions are all routes from A to B, the objective is total distance, the direction is minimize, and the answer is a route whose length is smallest. It is useful to separate the optimal value (the best score, say 42 km) from an optimal solution (a route achieving 42 km); sometimes you want one, sometimes the other, sometimes both.

Every optimization problem comes with a natural decision version — "is there a feasible solution with objective at most k?" — and this bridge is heavily used in theory and practice. If you can answer that yes/no question quickly for any k, a short search over k pins down the optimal value, and a bit more work usually recovers an optimal solution. A candid warning: optimization is often genuinely hard. For some problems we know fast exact methods (shortest paths, minimum spanning trees); for others, like packing a knapsack optimally, no fast exact method is known, and we fall back on approximation — accepting a solution provably close to the best instead of insisting on the very best.