7

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.

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94
progammer
  • 171
  • 3
  • I’ve never seen the Goldbach conjecture formulated as an optimization problem. Maybe you’ll discover a way to do so? Best of luck! – A rural reader Dec 26 '21 at 20:08
  • 1
    @Aruralreader That's actually pretty simple: $\max_{n\in\mathbb{N}} \min_{p,q \in \text{Primes}} |2(n+2)-p-q| = 0$. – Federico Poloni Feb 09 '23 at 20:02
  • Perhaps you have in mind the part of an optimization problems that asks whether the constraints can be satisfied (consistency) or the feasibility subprogram. It is common to approach such problems by adding an objective of no independent interest, thus converting the feasibility question into an optimization problem. – hardmath Feb 10 '23 at 19:00

1 Answers1

7

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 the 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.

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94