Optimal Solutions and Optimal Values

"The best is 480" and "the best plan is six benches and two stools" answer different questions. One of them can be unique while the other is not.

Exam answers lose marks here more often than anywhere else in the subject, because the two are reported in the same sentence and the question usually asks for only one of them.

Two different things come out of an optimization problem.

The optimal solution is a choice: which quantities to set, and to what. It is a point.

The optimal value is what that choice scores: the number the objective returns there. It is a single number.

Asking what should we do? wants the first. Asking how much can we make? wants the second. They can come apart: several different choices may score exactly the same best number, so there can be many optimal solutions but never more than one optimal value.

For a problem minimizing $f$ over a feasible set $F$:

A point $x^{\star }\in F$ is an optimal solution if $f(x^{\star })\le f(x)$ for every $x\in F$.

The optimal value is the number $f(x^{\star })$, written $\underset{x\in F}{min}f(x)$.

The set of all optimal solutions is the optimal set, $\arg \underset{x\in F}{min}f(x)$. It may contain one point, many points, or none at all.

The optimal value is unique whenever it exists: if $x^{\star }$ and $y^{\star }$ are both optimal, then $f(x^{\star })\le f(y^{\star })$ and $f(y^{\star })\le f(x^{\star })$, so $f(x^{\star })=f(y^{\star })$. The two choices differ; the number they score cannot.

One optimal solution. Minimise $x$ subject to $x\ge 2$. The optimal solution is $x=2$; the optimal value is 2. Here they happen to be the same number, which is exactly why this case teaches the distinction badly on its own.

Many optimal solutions, one optimal value. Maximise $x+y$ subject to $x+y\le 4$, $x,y\ge 0$. Every point on the segment from $(4,0)$ to $(0,4)$ is optimal, infinitely many optimal solutions. The optimal value is 4 for all of them.

No optimal solution, though feasible points exist. Minimise $x$ subject to . Every feasible point has a smaller feasible point below it, so no choice attains a minimum. The greatest lower bound is 0, but 0 is not feasible: there is no optimal solution and no optimal value.

How to report. What should we produce? answers with a point: 4 chairs and 0 tables. What is the maximum profit? answers with a number: 160. Giving a point where a number was asked, or a number where a point was asked, does not answer the question.

Maximise $3x_1+3x_2$ subject to $x_1+x_2\le 10$, $x_1,x_2\ge 0$.

Not a complete answer. The optimum is 30.

This gives the value and calls it the optimum. If the question asked what to produce, it has not been answered, and it hides that the answer is not a single choice.

Not a correct answer. The optimal solution is 30.

30 is a number, not a point. No choice of $x_1$ and $x_2$ has been named.

A complete answer. Every point with $x_1+x_2=10$ and $x_1,x_2\ge 0$ is an optimal solution, for instance $(10,0)$, $(0,10)$, or $(5,5)$. The optimal value is 30.

The test: a solution is something you could act on, and a value is something you could put in a budget. If your answer to what should we do is a number, you have reported the wrong object.