fbpx

The Value of a Feasible Solution

feasible
3 min read

The most important part of solving a problem is finding a solution. More importantly, a solution you can work with.

In this post, we will outline:

A feasible vs a global solution
The solving process
What it means to have a feasible solution

Feasible vs Global

Optimisation problems require a solver to return a solution quickly. The reliability of that solution is paramount. In general, solution quality can be categorised as follows:

imageedit_226_2490592897

Octeract Engine is a deterministic global optimisation solver. This means that it specialises in locating global solutions to optimisation problems with a theoretical guarantee that the returned solution is, in fact, the global one. As shown above, this is the best possible solution.

A feasible solution, on the other hand, is a solution that satisfies the problem’s constraints and is valuable, in terms of its usability. This type of solution falls into the Level 2 category. In the Engine’s case, the feasible solution is sometimes the global solution. Once the problem has timed out, we can prove this. Either way, the Engine will return a reliable solution that the user can implement.

The Solving Process

Octeract Engine is a solver the makes finding a globally optimal solution its main mission. To ensure global optimality, the Engine has implementations of algorithms that guarantee convergence to a global optimum in a finite time. This process involves the use of factorable and non-linear relaxations of the problem. In its quest to find a global solution, the Engine can return a feasible solution in a short amount of time. How short? In our benchmark, we used problems from the literature as well as problems designed to break solvers in different ways. The Engine produced the following results.

Minutes to Solve

30 (timeout)

Feasible Solutions

88%

Number of CPUs

1

Within a half an hour timeout, the Engine found feasible solutions to some of the hardest problems we could find.

The Meaning of Feasibility

It is in a Deterministic Global Optimisation solver’s nature to automatically pursue a global optimal solution and continue this search until one is found. Octeract Engine employs the branch and bound framework to do this. As seen above, this process allows the solver to find feasible solutions. What does this mean for the user? The value of a feasible solution cannot be emphasised enough. These are the solutions that are on the money and that users can actually work with. As mentioned, there are cases where a feasible solution is, in fact, also the global solution.

This is much better than a solution produced by a local solver. Having a feasible solution to a complex problem is worth more than no solution or some solution. How much more? A feasible solution is one that steers the direction of decision making towards success. This is where the real worth of a global optimisation solver lies.

Leave a Reply