How to Select the Best Optimization Method for Your Problem

Every mathematician, industrial engineer, computer scientist or management scientist has at some point in their career been asked to solve a problem for optimization, i.e., achieve the best suitable solution under a set of conditions. Finding the right solution is the task at hand; however, selecting the method best suited to achieve an optimal solution is a concealed hard skill necessary for the resulting solution. Operations research (O.R.) methods cover several methods for the purpose of optimization, and extensive research has proved many more novel methods are being proposed every day. Thus, it is challenging to be aware of all possible methods and select the one most suitable to your problem. Here, we will share some guidelines to arrive at the best suited macroscopic method and then leave it to the reader to identify the most suitable method within.

First, let’s understand what optimization is at its core.

What is Optimization?

In simple terms, to “optimize” implies arriving at the best possible solution given a set of limitations or constraints. There is an objective that needs to be met with inputs that satisfy the constraints. Mathematically, this may either be a minimization or maximization problem that is defined as the objective function (e.g., minimizing costs or maximizing profits, minimizing waiting time or maximizing revenue); constraints may be a set of equalities or inequalities (conditions) with inputs to the objective function or decision variables (what basically goes into the objective function to achieve it).

There are many industrial applications of optimization, from strategic business decisions of maximizing profitability or minimizing costs to operational tasks of minimizing wait time and schedule planning or resource optimization with reference to capacity utilization. The applications are aplenty. Optimization or O.R. methods comprise even more methods to solve the problem, and most professionals are not aware of each and every method. So, how would one go about choosing the best possible method to ensure an optimal solution? As a doctoral researcher, I face this challenge as well on a daily basis while working on my thesis and thus have put together a step-by-step guide for the benefit of others facing a similar conundrum.

Step 1: Formulate the Problem

Formulate the problem by establishing the objective function, constraints and decision variables. This will give you an idea of the nature of the problem type. For instance, if you have more than one objective function, it may indeed be a multiobjective optimization problem and have several different methods tailormade for such a situation. In the event the decision variables are discrete (e.g., binary: 0/1) or finite values, then this is classed as a combinatorial optimization method, and discrete methods would need to be selected – also known as (mixed) integer or binary problems, depending on whether it takes an integer or binary value. You may be able to smoothen the discreteness of the function and have a linear or convex optimization problem (more on this later); thus, a branch-and-bound or branch-and-price method may be used.

Step 2: Assess for Linearity

When you have formulated your problem, you can assess for linearity or nonlinearity by plotting graphs of the constraints and objective function or by simply looking at the power of the equations. This will again be another input to decide the appropriate optimization method. This will let you decide whether a linear or nonlinear programming problem is required as a solution.

Step 3: Assess for Convexity

If unable to model the problem as a linear problem, then your best bet might be to formulate it as a convex problem. This means that for each point in an interval (a, b € I), the line segment between the points (a, f(a)) and (b, f(b)) are above or on the curve f. Depending on convexity, there are several different algorithms to select from.

This brings us to our next question: What are the different methods available and when do you select one over another?

Available Optimization Methods and When to Select

The types of methods can be broadly classified into two types: exact and heuristics. A third method that is a natural combination of the two would be called a hybrid methodology, which bases its foundations on the best of both exact and heuristics methods. The choice of method also depends on complexity. Exact methods are classical and usually offer a deterministic output, whereas heuristics offer an approximate and not necessarily the most optimal output. A recent trend has been observed that gravitates toward selecting heuristic approaches; however, the advice is to exhaust all options of exact methods before selecting a heuristic approach, because it only provides an approximate, and not optimal, solution after all – and we are solving for optimization here.

If you have a computationally difficult problem to solve and time is of paramount importance, then a heuristic method is suited over a discrete method.

For a first-level answer to our overarching question of which method to use, the decision tree from the textbook “Engineering Design Optimization” gives a good overview. (The book can be downloaded from https://mdobook.github.io for further reference.)

It is clear that there are innumerable applications of optimization in industry and otherwise. This article has made a small attempt to declutter the noise with reference to different methods that can be adopted while sifting through the problem and its respective characteristics. Although it may not be exhaustive, it is a first step toward bringing a method to this madness.