4
$\begingroup$

An optimization problem has 3 main components: decision variables, constraints and an objective function. Such a problem can be mathematically modelled and solved using an optimization solver. For example, a SUDOKU puzzle can be modelled as such and solved using a solver.

What are examples of famous real-life problems or puzzles that cannot be modelled as optimization problems? I reviewed relevant literature, but could not find any discussion on problems that cannot be modelled as optimization problems.

$\endgroup$
3
$\begingroup$

It depends on the selected level of abstraction and chosen classification. The question would be in the usability of this abstraction and the chosen classification of problems.


If you are allowed to assume that an objective function can mean a boolean function that is true if and only if the found solution satisfies the given constraints (rules of the puzzle), – then any mathematical problem can be formulated in such a way.

Moreover, in first lecture notes of UC Berkely course CS278: Computational Complexity, Luca Trevisan says:

we will deal with four types of computational problems: decision problems, search problems, optimization problems, and counting problems. This distinction is useful and natural, but it is also arbitrary: in fact every problem can be seen as a search problem.

Now, I don't think that it would be an overextension to say that every search problem can be thought of as an optimization problem.

After writing this answer, I also found a discussion on Theoretical Computer Science. The additional piece there would be the mentioning of a sampling problem. However, even that is very arguable: This paper by Scott Aronsson draws an equivalence on sampling and searching.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.