Which optimization problem to use when I want to explain the concept of optimization to a layman?

Question

I am looking some problem, which would be:

1. Easy to understand
2. Hard to solve intuitively
3. Touch our everyday lives

---

I am doing research in optimization using evolutionary computation. When people ask me what I do, I have no problem to explain evolutionary computation, but it is hard to get across the idea of optimization. It seems that optimization has many meanings in the real world, such as "optimize your daily routine", "optimize the landing page"... and these meaning are very different from the formal concept of mathematical optimization.

I think I could get my point across better if I used some example from the real world. Something that has real impact on the lives of people and something that they are in contact with every day. One such example is the optimization of the shape of the nose of the Shinkansen bullet train. The nose has a very complicated shape that tries to optimize several aerodynamic criteria. The problem is that to explain this problem I would have to explain how a shape can be parametrized and converted to numbers. And again I would have to explain how the aerodynamic properties of a given shape are tested using physics simulations.

I thought about the Travelling salesman problem, but this sounds like a toy problem, since there are no more travelling salesmen. I am aware that TSP has many industrial applications, but explaining those applications takes us away from everyday life.

Similarly the Knapsack problem seems to be a toy problem, since when we are packing to go somewhere usually we can solve the problem very nicely using our intuition. Moreover, when we pack for a vacation, we do not follow the maximization of utility procedure, but a more complicated mental process. Also, someone always finds the solution of just inserting the item with the highest value/mass ratio, until we reach the mass limit and it is hard to persuade the person, that this is not necessarily optimal.

Answer 1

It depends on what you are aiming for.

For an easy, toy example you could take the Steiner tree problem. It's easy to describe and you have a very simple, but not-that-intuitive case when the set of terminals is a square:

For a more practical thing, there is a lot of optimization going on in medicine and pharmacology. To give some concrete example, when we use bacteria or yeast to produce something, you have to optimize the food you give to the organism to improve the speed of production or cost or purity of the output, etc. I don't know the details, but if I recall correctly, synthetic insulin is (or was, there was some research to use plants for this) produced this way.

I hope this helps $\ddot\smile$

Answer 2

Give them a lecture as follows:

1. You are interacting with a certain natural, technical, economical, $\ldots$, "system".
2. You are allowed to make some decisions how to interfer with this "system".
3. In principle you know exactly what the effects of your decisions are; so there are no unforeseeable customer reactions, etc.
4. There is a (one!) certain quantity $\Phi$, like profit, cost, volume, material consumption, waste, $\ldots$, that you want to maximize, resp., minimize by clever action.

We are confronted with such situations everyday, and usually we resolve them freehandedly using our "experience in the field". Now what is "mathematical optimization"?

5. In the first place we have to set up a mathematical model of the system at hand. Such a model is a conceptual description of our system in terms of formulas and figures, a "virtual machine" that simulates the behavior of the real system in a "spiritual" way. Our "experience in the field" is all important in setting up this model. It leads us in deciding which details of the real system should be "mapped" into the model (making it more complicated), and which ones may safely be neglected.

Example: When four villages shall be connected by sewage lines, as in @dtldarek 's answer, one may decide to neglect existing rivers, mountains, or railway lines, and just consider the geometric layout of the four villages.

6. When the model is set up the quantity $\Phi$ which we want to maximize, appears as an "algorithm" which allows to compute for any allowed "action" $x$ the resulting output $\Phi$. If we are lucky this algorithm is just a simple formula, like $$\Phi(x)=7x^2-13x +9\ .$$ We then choose $x$ such that $\Phi$ gets minimal. In other cases the "action" might consist in choosing a most favorable wing shape. Of course this is a much more complicated unknown than a simple number $x$, but mathematics has tools for finding the optimal shape.

Example: What shape of given surface area encloses the largest volume? (Of course we all know the answer in this simple case.)

There are also problems with a combinatorial flavor. This is already apparent in the above sewage ("Steiner tree") example; and everyone has heard of the TSP.

Only after a sermon along these lines start with a very simple example (e.g., making a coverless box of maximal volume from a rectangular cardboard), and treat this example to the end. It helps when the optimal $x$, call it $x_*$, is not $=2$, but $=\sqrt{17}$.

There are also general principles to be learnt in this context, among them the following two:

• You don't loose much if you don't hit the optimal $x$ exactly.

• A small change in the problem data does not change the optimal value of $\Phi$ much, but it may induce a radical change of the optimal action $x$.

And on, and on.