Do you want to solve a non-linear optimization problem? Have you doubts about what solver is the best? Then, you are in the correct place! =) Continue reading and have a look at this repo.
This repository aims to perform a comparison of several of the available non linear solvers. Such a comparison is made in terms of the objective value and the computational time.
To do this, some non linear optimization problems of different nature are modelled using Pyomo, and run with different solvers. The results are saved and analyse below to get conclusions.
It is important to note that the conclusions draw here cannot be extended to all the existing optimization problems. This repo just serves as a guide for your decisions, but it is not an universal truth. Please take this into account when deciding which solver is more suitable in your case.
In this section, we explain the strategy applied to compare the different solvers. Let us consider the following list of non linear solvers used in our examples to compare their performance:
We are interested not only in comparing the performance of each solver but also the differences between using them with or without calling the Neos Server, as well as to compare the efficiency of using them through AMPL. Hence, three lists of solvers are created from the previous one.
The first list is formed by the solvers whose executable file are included in the AMPL license:
List solvers AMPL:
The solvers of the second list are open source and the executable files can be downloaded here. Thus, it is not necessary to use them via the Neos Server:
List solvers without Neos
Finally, the third list is composed by those solvers that require license for their use. In order to avoid such an issue, we run them with the help of the Neos Server:
List solver with Neos
The next step consists of running the optimization problem for the different solvers enumerated in the previous three lists. Since the optimization problems we are considering in this repo are (highly) non linear, they may stuck at local optimal. Hence, a multistart approach is applied in which the same problem is run several times starting from different initial solutions, randomly chosen from the feasible region. The number of runs at the multistart is defined by the user.
The objective value and the computational time will be used as measure of performance. Particularly, we provide the average, the maximum and minimum of all the objective values obtained after running the multistart, as well as the average, the maximum and minimum value of the computational time. The results of each optimization problem are summarized in a table which, apart of the performance values previously mentioned, includes extra information such as the name of the problem, if the Neos Server or AMPL is used or not, the solver utilized, the number of variables and constraints involved, and also the sense of the optimization problem, i.e., if the objective is to minimize or maximize certain objective function. An example of the results is given below:
problem | neos | ampl | solver | #variables | #constraints | sense | mean obj. val. | max obj. val. | min obj. val. | mean comp. time | max comp. time | min comp. time |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Problem 1 | yes | no | conopt | 100 | 200 | min | 1.2 | 5.7 | 0.23 | 180 | 300 | 50 |
The whole computational experience is executed on a laptop with 8Gb of RAM memory at 1.80 GHz, running Windows 10.
This section briefly explains the organization of the examples used here. This repo contains one folder per optimization problem.
Each folder contains three new folders and a script called main_name_of_the_problem.py
. Such a script is the only one that should be executed
when running the experiments. Moreover, the first folder, entitled model_pdf
contains the document with the model formulation. The second folder, optimization_problem_utils
is formed
by the scripts which solves the optimization problem, so be careful when modifying it. Do not hesitate to contact the person who has written this code.
Finally, the third folder entitled results_name_of_the_problem
includes the results obtained in all the runs of the multistart, and a
summary of them, called summary_results.csv
.
The following table provides the optimization problems which have been used for the non linear solvers comparison. This table includes the name of the problem, the problem formulation and the folder with the obtained results.
# | Name | Model Formulation | Folder results |
---|---|---|---|
1 | M2SVM_Optimal_Weights | M2SVM_Optimal_Weights Model Formulation | M2SVM_Optimal_Weights Results |
2 | MINLP_Trigonometric_Functions | MINLP_Trigonometric_Functions Model Formulation | MINLP_Trigonometric_Functions Results |
More details about the results obtained in each example are given in next sections.
The aim of the optimization problem formulated here is to seek the optimal weights in the Gaussian kernel in order to obtain a good classification with the Support Vector Machine. Since the problem is based on a toy example, the size of this optimization problem is small. Particularly, it is formed by 15 continuous variables and 36 constraints.
A multistart approach with 1000 runs is run for the different solvers as explained in previous section. A summary of the results obtained can be seen in the following table. If further information is necessary, we suggest the reader to download the summary here or to have a look at the results of the different runs in this folder.
problem | neos | ampl | solver | #variables | #constraints | sense | mean obj. val. | max obj. val. | min obj. val. | mean comp. time | max comp. time | min comp. time |
---|---|---|---|---|---|---|---|---|---|---|---|---|
m2svm_optimal_weights | no | yes | conopt | 15 | 36 | min | -6.46E-14 | 1.45E-15 | -3.61E-13 | 0.15 | 0.35 | 0.07 |
m2svm_optimal_weights | no | yes | loqo | 15 | 36 | min | -1.37E+12 | 9.00E+03 | -3.07E+12 | 0.30 | 1.45 | 0.11 |
m2svm_optimal_weights | no | yes | minos | 15 | 36 | min | -2.79E-14 | 0.00E+00 | -8.56E-14 | 0.11 | 0.49 | 0.06 |
m2svm_optimal_weights | no | yes | snopt | 15 | 36 | min | -1.05E-14 | 4.44E-16 | -5.81E-14 | 0.10 | 0.20 | 0.06 |
m2svm_optimal_weights | no | no | ipopt | 15 | 36 | min | -7.50E-08 | -7.49E-08 | -7.50E-08 | 0.11 | 0.30 | 0.10 |
m2svm_optimal_weights | no | no | bonmin | 15 | 36 | min | -9.97E-08 | -9.38E-08 | -9.99E-08 | 0.12 | 0.34 | 0.07 |
m2svm_optimal_weights | no | no | couenne | 15 | 36 | min | -2.88E-13 | -2.88E-13 | -2.88E-13 | 0.67 | 14.98 | 0.18 |
m2svm_optimal_weights | yes | no | conopt | 15 | 36 | min | -6.46E-14 | 1.45E-15 | -3.61E-13 | 18.05 | 73.97 | 2.38 |
m2svm_optimal_weights | yes | no | ipopt | 15 | 36 | min | -7.50E-08 | -7.49E-08 | -7.50E-08 | 17.31 | 38.74 | 2.38 |
m2svm_optimal_weights | yes | no | filter | 15 | 36 | min | -1.74E-13 | 0.00E+00 | -2.86E-13 | 18.51 | 29.40 | 2.59 |
m2svm_optimal_weights | yes | no | knitro | 15 | 36 | min | 1.87E-07 | 4.85E-06 | -9.89E-10 | 18.11 | 66.91 | 2.41 |
m2svm_optimal_weights | yes | no | loqo | 15 | 36 | min | -1.13E+12 | 1.89E+04 | -2.98E+12 | 17.85 | 66.01 | 2.47 |
m2svm_optimal_weights | yes | no | minos | 15 | 36 | min | -2.79E-14 | 0.00E+00 | -8.56E-14 | 18.15 | 38.81 | 2.78 |
m2svm_optimal_weights | yes | no | mosek | 15 | 36 | min | 3.33E-09 | 3.37E-09 | 3.33E-09 | 17.41 | 82.82 | 2.39 |
m2svm_optimal_weights | yes | no | snopt | 15 | 36 | min | -1.05E-14 | 4.44E-16 | -5.81E-14 | 18.16 | 39.06 | 2.41 |
m2svm_optimal_weights | yes | no | bonmin | 15 | 36 | min | -9.97E-08 | -9.38E-08 | -9.99E-08 | 18.04 | 41.91 | 2.60 |
m2svm_optimal_weights | yes | no | couenne | 15 | 36 | min | -2.88E-13 | -2.88E-13 | -2.88E-13 | 17.72 | 76.28 | 2.55 |
m2svm_optimal_weights | yes | no | filmint | 15 | 36 | min | -2.77E-13 | -2.77E-13 | -2.77E-13 | 17.21 | 66.69 | 2.56 |
In spite of the small size of the problem, the results allow us to get conclusions about the different solvers.
Regarding the objective values, we observe that in all the cases a mean value close to zero is obtained, except in the loqo
solver, which
at first sight seems to be the best one. However, the optimal solution obtained with loqo
(which can be downloaded here and here)
is numerically unstable, since values of order 1E+25 are obtained. Therefore, loqo
is not a good solver for our problem, but
any of the remaining ones can be used.
With respect to the computational time, we see that there is a difference mean of three order of magnitude between using the solvers through the Neos server
or directly using the executable files. The reason of this issue is that solving an optimization problem via Neos not
only includes the computational cost associating to the problem resolution but also the calls to the server which significantly increase the total elapsed time.
Looking at that solvers that have been used without Neos, we check that couenne
is the one that spent most time solving the problem, and then is not advisable to use.
Thus, taking into account the previous comments, for this particular optimization problem, we suggest to use any of the following solvers without Neos: conopt
,
minos
, snopt
, ipopt
and bonmin
.
In this example, we solve a Mixed Integer Non Linear Programming (MINLP) problem with trigonometric functions involved. Contrary to the Example 1, this problem is of medium size, since it is formed by 300 variables (150 integer and 150 continuous) and 153 constraints.
The results of the different solvers after solving the multistart with 100 runs are shown in the following table. For more details the reader is referred to this file and this folder:
problem | neos | ampl | solver | #variables | #constraints | sense | mean obj. val. | max obj. val. | min obj. val. | mean comp. time | max comp. time | min comp. time |
---|---|---|---|---|---|---|---|---|---|---|---|---|
MINLP_trigonometric_functions | no | yes | conopt | 300 | 153 | min | 24.63 | 122.80 | -165.20 | 8.28 | 24.72 | 0.99 |
MINLP_trigonometric_functions | no | yes | loqo | 300 | 153 | min | -7.63 | 4.33 | -22.19 | 3.45 | 14.33 | 1.77 |
MINLP_trigonometric_functions | no | yes | minos | 300 | 153 | min | 39.47 | 463.60 | -417.00 | 1.74 | 3.13 | 0.73 |
MINLP_trigonometric_functions | no | yes | snopt | 300 | 153 | min | 30.89 | 463.60 | -228.50 | 3.16 | 9.51 | 0.54 |
MINLP_trigonometric_functions | no | no | ipopt | 300 | 153 | min | 3.27 | 64.99 | -92.47 | 57.32 | 198.60 | 15.01 |
MINLP_trigonometric_functions | no | no | bonmin | 300 | 153 | min | 8.08 | 196.60 | -9.60 | 89.60 | 327.60 | 10.15 |
MINLP_trigonometric_functions | no | no | couenne | 300 | 153 | min | - | - | - | max time reached | - | - |
MINLP_trigonometric_functions | yes | no | conopt | 300 | 153 | min | 24.43 | 87.75 | -200.60 | 19.14 | 25.74 | 9.51 |
MINLP_trigonometric_functions | yes | no | ipopt | 300 | 153 | min | 6.24 | 64.99 | -9.12 | 22.11 | 57.23 | 9.91 |
MINLP_trigonometric_functions | yes | no | filter | 300 | 153 | min | 27.43 | 62.73 | -9.65 | 19.68 | 38.31 | 15.17 |
MINLP_trigonometric_functions | yes | no | knitro | 300 | 153 | min | -4.54 | 62.66 | -9.26 | 19.54 | 43.99 | 7.20 |
MINLP_trigonometric_functions | yes | no | loqo | 300 | 153 | min | -7.16 | -0.23 | -9.50 | 19.77 | 39.89 | 9.05 |
MINLP_trigonometric_functions | yes | no | minos | 300 | 153 | min | 39.47 | 463.60 | -417.00 | 18.92 | 28.98 | 8.31 |
MINLP_trigonometric_functions | yes | no | mosek | 300 | 153 | min | 0.00 | 0.00 | 0.00 | 18.51 | 23.19 | 4.77 |
MINLP_trigonometric_functions | yes | no | snopt | 300 | 153 | min | 31.40 | 299.30 | -22.19 | 19.49 | 37.79 | 5.63 |
MINLP_trigonometric_functions | yes | no | bonmin | 300 | 153 | min | 7.13 | 64.26 | -9.72 | 22.33 | 48.24 | 6.62 |
MINLP_trigonometric_functions | yes | no | couenne | 300 | 153 | min | - | - | - | max time reached | - | - |
MINLP_trigonometric_functions | yes | no | filmint | 300 | 153 | min | - | - | - | Neos error | - | - |
It is important to note that not all the solvers tested are designed for handling optimization problems with integer variables.
Particularly, only bonmin
, couenne
, filmint
and mosek
are able to treated such variables. However, looking at the
table of results, we see that couenne
and filmint
cannot be used because of different reasons. On the other hand,
mosek
only solves problems with a conic structure. Unfortunately, our problem does not have such a structure. Therefore, it just
remains bonmin
for the resolution. Similar results in terms of the objective values are obtained when comparing the average
obtained with and without Neos. Nevertheless, contrary to what happened in Example 1, the computational time decreases when solving the problem
through Neos server. In other words, when a medium-size non linear optimization problem (with integer variables)is considered, it is better to run the problem
in a server than in a standard laptop.
When the numerical numerical experiments of the rest of the solvers are performed, the integrity of the variables is simply ommited.
In other words, those solvers which do not handle problems with integer variables just omit this constraint. With respect to
the average of the objective values, we state that knitro
is the best choice. Moreover, the results in terms of the computational time
are acceptable (around 20 seconds). Note that we have ignored the results of loqo
for the
very same reason as in Example 1. Regarding the computational times, the best choice is to use minos
through AMPL. However, the
mean of objective values has a very bad performance.
Hence, to solve the optimization problem of this example with integer variables we suggest to use bonmin
, and if the integrality constraint
is omitted, then it is better to use knitro
.
As previously mentioned at the beginning of this repo, the conclusions obtained here are not an universal truth, and therefore, they have to be use just as a guide. However, we can state that:
loqo
is not a good solver due to the unstable results that it provides.couenne
has more difficulties to find a local optimum solution than other solvers, e.g.bonmin
.- For small-size problems, all the solvers are equivalent in terms of the objective values. However, there exists differences of three orders of magnitude when running locally or via Neos.
- Running a medium-size optimization problem in a local computer is equivalent to run it on the Neos server, in terms of the computational time.
- For the optimization problems tested, the best solvers are
conopt
,minos
,snopt
,ipopt
andbonmin
in the first case andbonmin
,knitro
andipopt
in the second case.
This section explains the steps to follow if a comparison of the solvers want to be performed on a new optimization problem.
First, a folder with the name of the optimization problem should be created. This folder should contain three subfolders and
a main
file. The role of each of the folders is explained in the Examples section. Then, a script named main_name_of_the_problem.py
is built. This script should contain the preamble with the following information which delete the possible variables which are saved in the
environment and automatically change the directory:
from __future__ import division
for name in dir():
if not name.startswith('_'):
del globals()[name]
import os
directory_path = os.path.dirname(os.path.abspath(__file__))
os.chdir(os.path.join(directory_path, os.path.pardir))
import comparison_utils as cu
os.chdir(directory_path)
Then, the parameters of the new problem should be defined. An example of the values of these parameters is given below:
problem = 'new_problem'
number_of_variables = 500
number_of_constraints = 200
sense_opt_problem = 'max'
maximum_number_iterations_multistart = 1000
folder_results = 'results_' + problem + '/'
csv_file_name_multistart = 'results_multistart'
csv_file_summary_results = 'summary_results'
The next lines of the script are formed the lists of the solvers used for the comparison. They are divided according to their use through AMPL and Neos. The lists below are the ones used in the previous examples. This choice is flexible and can be modified according to the user requirements.
solvers_list_ampl = ['conopt',
'loqo',
'minos',
'snopt']
solvers_list_neos_flag_false = ['ipopt',
'bonmin',
'couenne']
solvers_list_neos_flag_true = ['conopt',
'ipopt',
'filter',
'knitro',
'loqo',
'minos',
'mosek',
'snopt',
'bonmin',
'couenne',
'filmint']
Finally, the optimization problem is solved for each element in the list using the function run_optimization_problem_given_solver
.
Here you can see an example:
for solver in solvers_list_neos_flag_true:
neos_flag = True
ampl_flag = False
print(solver)
cu.run_optimization_problem_given_solver(solver = solver,
problem = problem,
neos_flag = neos_flag,
number_of_variables = number_of_variables,
number_of_constraints = number_of_constraints,
sense_opt_problem = sense_opt_problem,
maximum_number_iterations_multistart = maximum_number_iterations_multistart,
folder_results = folder_results,
csv_file_name_multistart = csv_file_name_multistart,
ampl_flag = ampl_flag)
Apart from the parameters previously mentioned, this function has two extra parameters called neos_flag
and ampl_flag
indicating if the Neos server or the AMPL are used or not. The value of each parameter is given in next lines depending on
the list used:
solvers_list_ampl
neos_flag = False
ampl_flag = True
solvers_list_neos_flag_false
neos_flag = False
ampl_flag = False
solvers_list_neos_flag_true
neos_flag = False
ampl_flag = False
The function run_optimization_problem_given_solver
is defined in the script comparison_utils.py
. When a new optimization
problem is to be compared for different solvers, then an if
structure should be added, which is True
if the problem
parameter is equal
to the name of the new problem, and which runs the optimization problem which has been previously coded. An example of the
new structure can be seen here:
if problem == "new_problem":
run_new_problem(solver = solver,
problem = problem,
neos_flag = neos_flag,
number_of_variables = number_of_variables,
number_of_constraints = number_of_constraints,
sense_opt_problem = sense_opt_problem,
maximum_number_iterations_multistart = maximum_number_iterations_multistart,
folder_results = folder_results,
csv_file_name_multistart = csv_file_name_multistart,
ampl_flag = ampl_flag)
Moreover, the function run_new_problem
includes the model definition as well as the resolution. We suggest to include
in the call to the solver, an if
structure which varies depending if the Neos server is used or not. The code structure should be similar to this one:
solver_name = 'conopt'
if neos_flag:
solver = pe.SolverManagerFactory("neos")
else:
solver = pe.SolverFactory(solver_name)
if neos_flag:
results_solver = solver.solve(multistart_model,
tee = True,
opt = solver_name)
else:
results_solver = solver.solve(multistart_model,
tee = True)
Finally, we suggest to save the output results of the multistart in a binary .pydata
file or similar, as well as to save
the objective value and computational times (or any other performance measure) for each of the runs of the multistart. Morever, it will be nice to
have a summary of the results. An example
of the function which write the results can be seen in the function write_results_minlp_trigonometric_functions
in the
comparison_utils.py file.
Please, do it. Any feedback is welcome, so feel free to ask or comment anything you want via a Pull Request in this repo.
(Please add your name here if you have contributed to the repo)
##License