I've formulated my linear/nonlinear/integer/mixed-integer optimization problem in algebraic form (possibly with the help of the folks on this site).
Now what? How do I solve it?
$\begingroup$
$\endgroup$
2
asked Sep 21, 2019 at 1:08
-
3$\begingroup$ I wrote this Q&A to help people who ask about a formulation but then need some guidance about how to implement and solve the resulting formulation. I'm thinking especially about questions from people who might be new to OR but are aware that OR is good at solving certain types of problems. They post here, we help them formulate their problem, and then they realize that they don't know how to solve it. $\endgroup$– LarrySnyder610Commented Sep 21, 2019 at 1:08
-
1$\begingroup$ Examples include this one and this one. I welcome your feedback; feel free to post comments or make suggested edits to my answer. Or to post your own. $\endgroup$– LarrySnyder610Commented Sep 21, 2019 at 1:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You need to send your model to a solver. Let's discuss the "solver" part and the "send" part separately.
The "solver" part:
A solver is a piece of software that implements a general-purpose algorithm for solving optimization problems. Solvers implement algorithms like the simplex method, interior point methods, branch-and-bound, and branch-and-cut. Their goal is to be able to solve any problem, within certain classes (linear, integer, nonlinear, convex, etc.), that you can dream up.
(That's the goal. A solver's ability to solve your actual problem depends on the structure of your problem, the size of your instance, and many other factors.)
A (very non-exhaustive) list of commercial solvers includes CPLEX, Gurobi, and Mosek. A (similarly non-exhaustive) list of open-source solvers includes OpenSolver for Excel, as well as the large suite of solvers in the COIN-OR project.
There are many factors to consider when choosing a solver, including performance, cost, reliability, and the type of problems it is capable of solving (linear, integer, quadratic, second-order cone, etc.).
More about solvers on OR.SE:
- Where can I find open source LP solvers?
- How to evaluate the performance of open source solver?
- How to select a Constraint Programming Solver
- Stochastic programming MIP solvers
The "send" part:
For the sake of simplicity, let's assume that your problem is a linear program (LP), which you have formulated algebraically as something like this: \begin{alignat*}{2} \text{minimize} \quad & \sum_{j=1}^n c_jx_j \\ \text{subject to} \quad & \sum_{j=1}^n a_{ij}x_j \le b_i &\qquad& \forall i=1,\ldots,m \\ & x_j \ge 0 && \forall j=1,\ldots,n \end{alignat*} Or, in matrix form: \begin{align*} \text{minimize} \quad & \mathbf{cx} \\ \text{subject to} \quad & \mathbf{Ax} \le {\mathbf b} \\ & {\mathbf x} \ge {\mathbf 0} \end{align*} The solver needs to know the matrix $\mathbf{A}$ and the vectors $\mathbf{c}$ and $\mathbf{b}$, as well as some other information like the sense of the objective function (min/max), bounds on the decision variables, etc.
The naive way to approach this is to build the matrix and vectors explicitly and then pass them to the solver. This is possible—for example, MATLAB's linprog function works like this—but it is extremely tedious and error-prone if your model is anything other than a tiny, toy model.
An easier and much more flexible approach is to use a modeling language, or modeling package in a language of your choice. Modeling languages/packages will do the tedious work of translating your algebraic model into one that a solver can understand, and the reverse work of translating the solver's output into formats that you can understand.
Modeling languages include AMPL, GAMS, and OPL. They are standalone programming languages specialized for mathematical optimization, with their own syntax, commands, etc. Some are free, others are not, and some have free trial versions or free licenses for academia or other special uses.
Modeling packages are meant to be used within another programming language. These include PuLP and Pyomo for Python, JuMP for Julia, and YALMIP for MATLAB. For the most part these packages are free.
In addition, some commercial solvers offer their own modeling packages. These include gurobipy for Gurobi + Python, docplex for CPLEX + Python, and CPLEX Concert Technologies for CPLEX + C++, Java, or C#. In the special case of Excel's Solver and OpenSolver, Excel plays the role of the modeling language.
More about modeling languages/packages on OR.SE:
answered Sep 21, 2019 at 1:08