
Kos Nimkar
Nov 17, 2026
Optimization is all about solving a set of constraints with a certain objective, either to maximize or minimize a variable quantity like profit or cost for example.
When the objective isn’t present or in other words when the objective is simply a constant, the optimization problem reduces to a constraint satisfaction problem. The constraint satisfaction problem has some deep applications in another area of computer science called Formal Verification.
Formal Verification is all about proving correctness of software or hardware systems and providing a counterexample if correctness cannot be proven. Such counterexamples usually represent bugs in software or hardware systems and it’s extremely valuable to catch such bugs early.
The goal of this article is to explain the strong connection between Mathematical Optimization and Formal Verification.
Consider a simple Java program below.
L1: int foo(int x, int y, int z) throws Exception {
L2: y = 3 * y;
L3: x = 2 * x + y;
L4: if (x > 5)
L5: x = x - 1;
L6: else
L7: x = x + 1;
L8: if (x == 0)
L9: throw new Exception("About to encounter divide by 0 error");
L10: return z / x;
L11: }
Fig. 1 - A simple Java program
Method foo in the program above does some arithmetic calculations with integer variables x and y and then on line 10 it returns the result of z divided by x.
However for the division to be safe the value of x must not be 0. This is captured by the Exception on line 9.
Can we prove that the exception on Line 9 in Fig. 1 is never thrown? If not, is there a counterexample?
Let’s see how formal verification can help in this context.
Consider the modified version of the same program in Fig. 2 where a new variable is introduced for every new assignment. This transformation is referred to as the static single assignment form (SSA). Line 9 in Fig. 2 is interesting because depending on whether the if condition on Line 5 evaluates to true, variable 𝑥₄ can take either the value of 𝑥₂ or the value of 𝑥₃.
Thus we need to introduce a conditional operator or line 9 in Fig. 2.
L1: int foo(int x₀, int y₀, int z₀) throws Exception {
L2: int x₁ = 0, y₁ = 0, x₂ = 0, x₃ = 0, x₄ = 0;
L3: y₁ = 3 * y₀;
L4: x₁ = 2 * x₀ + y₁;
L5: if (x₁ > 5)
L6: x₂ = x₁ − 1;
L7: else
L8: x₃ = x₁ + 1;
L9: x₄ = x₁ > 5 ? x₂ : x₃;
L10: if (x₄ == 0)
L11: throw new Exception(“About to encounter divide by 0 error”);
L12: return z₀ / x₄;
L13: }
Fig. 2 - Modified Java program with static single assignment
To reach Line 11 in Fig. 2, there are only two valid paths in this program.
Path 1: L1 -> L2 -> L3 -> L4 -> L5 -> L6 -> L9 -> L10 -> L11
Path 2: L1 -> L2 -> L3 -> L4 -> L5 -> L7 -> L8 -> L9 -> L10 -> L11
Let’s analyze path 2. The execution of this path can be represented mathematically by a first order logic formula below, where all variables are integers. The ∧ symbol represents the logical AND operation.
(𝑦₁ = 3𝑦₀) ∧ (𝑥₁ = 2𝑥₀ + 𝑦₁) ∧ (𝑥₁ ≤ 5) ∧ (𝑥₃ = 𝑥₁ + 1) ∧ (𝑥₄ = 𝑥₃) ∧ (𝑥₄ = 0)
You can see how the SSA form in Fig. 2 helps us build the mathematical formula that represents execution of Path 2. (Note that assignments on line 2 in Fig. 2 can be ignored as these are overwritten later in the program.)
We are interested in finding if Path 2 can indeed lead to the exception being thrown on line 11 in Fig. 2. Mathematically this means whether the formula above is satisfiable i.e. are there any values of 𝑥0, 𝑥1, 𝑥3, 𝑥4, 𝑦0, 𝑦1 which makes this formula evaluate to true?
If we can find such values for all variables, we have essentially proven that line 11 in Fig. 2 is indeed reachable and the exception will be thrown.
Modern solvers that can answer such questions are called Satisfiability Modulo Theories (SMT) Solvers. If you ask an SMT solver if the formula above is satisfiable, it will immediately tell you that it is indeed satisfiable and it will return the following solution giving assignments to all variables.
𝑥₀ = 4, 𝑦₀ = −3, 𝑦₁ = −9, 𝑥₁ = −1, 𝑥₃ = 0, 𝑥₄ = 0.
Going back to Fig. 1, you can easily trace the execution of method foo by passing x = 4 and y= -3 and can see that the exception will indeed be thrown.
We have just proven that there exists a path in our program that leads to the exception and our program has a bug. A potential fix might be to only allow unsigned integer values for the variables x and y in Fig. 1 by using one of the Java helper methods. The exception won’t be thrown in this case. (Try it!)
You can immediately see that the satisfiability problem above is the same as the optimization problem below.
Minimize (a constant objective function)
Subject to
𝑦₁ = 3𝑦₀
𝑥₁ = 2𝑥₀ + 𝑦₁
𝑥₁ ≤ 5
𝑥₃ = 𝑥₁ + 1
𝑥₄ = 𝑥₃
𝑥₄ = 0
In other words we are simply asking if the integer optimization problem above has a feasible region. You can see the connection between Optimization and Formal Verification. In fact the most popular algorithm for optimization - the Simplex algorithm is often used as a core component of Modern SMT Solvers.
Rather than evaluating paths 1 and 2 separately, we can in fact combine them and get a single formula. When we analyze programs like this, the resulting formula can be very large with complex boolean structures (a combination of logical OR and AND operators).
SMT Solvers can handle such large complex formulas, but whenever they need help solving pure arithmetic problems they ask for help from the Simplex algorithm.
One thing to highlight which is interesting is that in Optimization infeasibility is often an undesirable outcome stating the optimization problem cannot be solved. However in Formal Verification infeasibility is often desirable because it means non-existence of undesirable executions or bugs.
Hopefully this connection between Mathematical Optimization and Formal Verification sparks some exciting ideas in the minds of the readers.
References:
A Fast Linear-Arithmetic Solver for DPLL(T) - Bruno Dutertre and Leonardo de Moura. CAV 2006.
A Tool for Checking ANSI-C Programs - Edmund Clarke, Daniel Kroening, and Flavio Lerda. TACAS 2004
More Articles For You

The difference between academia and industry?
Dr. Andreas Emil Feldmann
(Academia vs Industry)


What's on the Menu? Solving the Product Mix Problem for Hydra's Pastry Pop-Up
Chahira Mourad
(Applied Scientist)


From Flour to Fortune: The Dual Role of Resources in Optimization
Chahira Mourad
(Mathematics in Real Life)


Pastries with a Plan: Where Will Hydra Open Her Bakery?
Chahira Mourad
(Mathematics in Real Life)
