# Examples of problems that cannot be formulated as optimization problems

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.

• I’ve never seen the Goldbach conjecture formulated as an optimization problem. Maybe you’ll discover a way to do so? Best of luck! Commented Dec 26, 2021 at 20:08
• @Aruralreader That's actually pretty simple: $\max_{n\in\mathbb{N}} \min_{p,q \in \text{Primes}} |2(n+2)-p-q| = 0$. Commented Feb 9, 2023 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
Commented Feb 10, 2023 at 19:00

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.