|
|
|
|
|
 |
Frontline Systems, Inc. |
||||||||||||||||||
|
|||||||||||||||||||
|
Solver models can be easy or hard to solve. "Hard" models may require a great deal of CPU time and random-access memory (RAM) to solve -- if they can be solved at all. The good news is that, with today's very fast PCs and advanced optimization software from Frontline Systems, a very broad range of models can be solved. Three major factors interact to determine how difficult it will be to find an optimal solution to a solver model:
Mathematical Relationships
The types of mathematical relationships in a model (for example, linear or nonlinear, and especially convex or non-convex) determine how hard it is to solve, and the confidence you can have that the solution is truly optimal. These relationships also have a direct bearing on the maximum size of models that can be realistically solved. A model that consists of mostly linear relationships but a few nonlinear relationships generally must be solved with more "expensive" nonlinear optimization methods. The same is true of models with mostly linear or smooth nonlinear relationships, but a few nonsmooth relationships. Hence, a single IF or CHOOSE function that depends on the variables can turn a simple linear model into an extremely difficult or even unsolvable nonsmooth model. A few advanced solvers can break down a problem into linear, smooth nonlinear and nonsmooth parts and apply the most appropriate method to each part -- but in general, you should try to keep the mathematical relationships in a model as simple (i.e. close to linear) as possible. Below are some general statements about solution times on modern Windows PCs (with, say, 2GHz CPUs and 512MB of RAM), for problems without integer variables. To learn more about the types of problems described below, click on Optimization Problem Types. Linear programming problems -- where all of the relationships are linear, and hence convex -- can be solved up to hundreds of thousands of variables and constraints, given enough memory and time. Models with tens of thousands of variables and constraints can be solved in minutes (sometimes in seconds) on modern PCs. You can have very high confidence that the solutions obtained are globally optimal. Smooth nonlinear optimization problems -- where all of the relationships are smooth functions (i.e. functions whose derivatives are continuous) -- can be solved up to tens of thousands of variables and constraints, given enough memory and time. Models with thousands of variables and constraints can often be solved in minutes on modern PCs. If the problem is convex, you can have very high confidence that the solutions obtained are globally optimal. If the problem is non-convex, you can have reasonable confidence that the solutions obtained are locally optimal, but not globally optimal. Global optimization problems -- smooth nonlinear, non-convex optimization problems where a globally optimal solution is sought -- can often be solved up to a few hundred variables and constraints, given enough memory and time. Depending on the solution method, you can have reasonably high confidence that the solutions obtained are globally optimal. Nonsmooth optimization problems -- where the relationships may include functions like IF, CHOOSE, LOOKUP and the like -- can be solved up to scores, and occasionally up to hundreds of variables and constraints, given enough memory and time. You can only have confidence that the solutions obtained are "good" (i.e. better than many alternative solutions) -- they are not guaranteed to be globally or even locally optimal. |
|
||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||
 |
|
|
