A mathematical model is a representation of real life complex combinatorial model in terms of mathematical equation and objective function. Mathematical equations are composed of various variables, coefficients, and equality types. Based on multiple variable types, variable degree and solving methodology models are mainly classified into the following types.
- Linear Programming Models
- Integer programming Models.
- Mixed Integer Programming Models.
- Non-Linear Programming Models.
- Constraint Programming Models.
Based on the model type, we can do a fundamental analysis of the complexity of our model. Liner programming models are less complex compared to other types of model and quick solvable. But when we talk about integer programming and mixed-integer programming, these models are more problematic as it works on the relaxed solution of the linear programming model. Therefore, its complexity increases exponentially with respect to the number of integer variables.
Non-linear programming models is a very big class of models as it has n degree variables. Some of the nonlinear variables can be transferred into linear equations to solve them efficiently. There are many limitations in solving nonlinear models like the model scalability issue; generally, we avoid it.
Constraint programming is a special class of operations research problem. Its main goal is to get a feasible solution in much faster way. It is also called as constraint satisfaction problem. Sometimes in real scenarios, we want only feasible solutions like in the case of scheduling problem, n-queens problem. In such cases, constraint programming is effective in solving quickly.
Solvers
Mathematical modeling can be defined as using mathematics to explain and describe the events in real life, test ideas, and make estimations about real-life events. A math programming solver is a computational engine that reads the optimization model and then delivers an optimal feasible solution. Math-Model is a combined form of sets, parameters, decision variables, objective function, and constraints. Solvers help us to find optimal values of our decision variables that follow all the business rules. There are various solvers available in the market. In this article, we try to share information about commonly used solvers.
Based on financials, we divided solvers into two types.
- Open-Source Solver
- Commercial Solver
Based on the model category, we divided solvers into three types.
- Linear Programming, Mixed Integer Linear programming, OR Integer Programming Solvers.
- Constraint Programming Solvers.
- Non-Linear Programming Solvers.
Open-Source Solver:
These are solvers which are available as a standard package. These solvers solve optimization models up to a certain extent efficiently. These solvers are available freely and updated from time to time by the open-source community. Following are some examples of generally used open-source solvers.
- CBC (COIN-OR Branch and Cut):
- open-source mixed-integer program (MIP) solver
- written in C++
- CBC supports Python-based modeling languages, Spreadsheet modeling, Commercial modeling languages, Mathematica, MATLAB, R, Sage, Julia, etc.
- GLPK ( GNU Linear Programming Kit ) :
- Solves large-scale solving large-scale linear (LP), mixed-integer (MIP), and related optimization problems (LP)
- written in C
- Comparison between CBC and GLPK :
- CBC performs well as compared to GLPK as per the benchmark instances given in the below link.
- In most instances, CBC performs well, and in very few cases, GLPK performs well. The performance of the solver is dependent on various factors.
- Those factors are highly dependent on problem definition, the scale of the problem, etc.
Commercial Solvers:
These solvers are very much faster than open-source solvers. It uses advanced techniques to solve the problem.
- GUROBI:
- Linear and quadratic optimization problems are having continuous, binary, and integer variables.
- Uses advance algorithms to arrive at an optimal solution as fast as possible.
- Special features include parameter tuning, solving the multi-objective problem, Shared-memory parallel processing, Streamlined access to cloud services, etc.
- Clients/Customers:
- Developer version:
- Gurobi allows you to try a free, full-featured, commercial evaluation license for 30 days
- Free benchmarking services
- Free model tuning services
- Access to Gurobi’s technical support
- Two free hours of one-on-one consulting services
- 20 free hours of the Gurobi Cloud
- CPLEX:
- Linear and quadratic optimization problems are having continuous, binary, and integer variables.
- This solver also supports constraint programming problems.
- For continuous problems, primal and dual simplex, interior-point (barrier); advanced branch-and-bound with presolve, feasibility heuristics, and cut generators for integer problems. For continuous problems comprised mostly or entirely of linear network flow constraints, network simplex.
- Shared-memory parallel processing for the barrier, branch-and-bound. Concurrent optimization by several methods to determine the best choice. Special facilities for parameter tuning and infeasibility diagnosis.
- Developer version:
- Charges $199 per authorized user per month
- Contains all features of Commercial Edition
- Unlimited variables and constraints
- Support access included with an active subscription
- Available for Windows64, Linux64, and macOS
- Free edition:
- Free to use
- Full features but limited to 1000 variables and 1000 constraints
- Use Optimization Programming Language (OPL) with the IDE
- It also supports modeling with API’s in C, C++, Java, C#, or Python
- Compatible with SPSS Modeler deployment facilities
- Contains advanced solver functionality
- Available for Windows64, Linux64, and macOS
- FICO Xpress:
- linear, mixed-integer, nonlinear, and constraint programming optimization solvers.
- For continuous problems, primal and dual simplex, interior-point (barrier); advanced branch-and-bound with presolve, feasibility heuristics, and cut generators for integer problems.
- It solves linear as well as nonlinear problems.
- Solver supports multi-threaded parallel processing out of the box, engaging multiple CPU cores to rapidly and efficiently solve
- Clients/Customer:
- Developer version:
- It allows you to try a free, full-featured, commercial evaluation license for 60 days
- It also provides complete technical support.
Comparison of Commercial Solver over Open-Source Solver :
| Sr.No | Commercial Solver | Open-Source Solver |
| 1 | Cost is very high compared to open-source solvers | Cheaper than commercial solvers |
| 2 | User friendly | Not so much user friendly |
| 3 | Source code is not accessible | Source code is accessible |
| 4 | It comes with extensive support | No support exists |
| 5 | Parameter tuning is available | Parameter tuning is absent |
| 6 | Speed is very high and supports more than 10x problem size | Efficient for small-scale problems. |
Optimal Trade-offs
- No approved budget to buy a commercial solver.
- Problem size is small and quickly solved by an open-source solver.
- The time required to solve by an open-source solver is less.
- Solving time is not a constraint.
- Profit earned using a commercial solver is more significant than buying a solver and its maintenance cost.
Constraint Programming Solvers:
The benchmark instances are provided to compare the CP solvers. In the case of solving real-world operational planning and scheduling problems, CP models can perform better. In some real-life problems, it’s tough to linearize some constraints in such a scenario where CP is used. Following are the most widely used constraint programming solvers.
- CP-SAT solver
- CP Optimizer solver
- Gecode solver
Benchmarks
Benchmarks for optimization software given by Hans D Mittelmann from School of Math & Stats Arizona State University. It created benchmark instances to compare the performance of solvers. In this section, we discuss the results of the benchmark instances of various solvers.
GUROBI:
CPLEX:
http://www.optimizationdirect.com/data/191016_amazingresults.pdf
Benchmarking Optimization Software:
http://plato.asu.edu/talks/euro2019.pdf
Benchmarking for Constraint Programming Solvers: