Solver Tutorial - What Makes a Model Hard to Solve?What Makes a Model Hard to Solve?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. |
Risk Solver Platform is an integrated superset of Premium Solver Platform and Risk Solver with best-of-breed simulation, best-of-breed optimization, and new stochastic programming and robust optimization capabilities you can't get anywhere else. Premium Solver Platform, our premier tool for conventional optimization, uses new PSI Technology to automatically analyze and transform your Excel model. It solves every type and size of problem, using built-in and plug-in Solver Engines. Premium Solver, our basic upgrade for the Excel Solver, solves up to 10X larger problems at much higher speed, and solves new kinds of problems with our Evolutionary Solver.
Risk Solver Platform is an integrated superset of Premium Solver Platform and Risk Solver with best-of-breed simulation, best-of-breed optimization, and new stochastic programming and robust optimization capabilities you can't get anywhere else. Risk Solver Premium integrates all the features of Premium Solver and Risk Solver, with far superior optimization and higher performance, easier to use simulation, for about the same price as competitive products for Monte Carlo simulation. Risk Solver is the easiest and fastest tool available for risk analysis of your Excel models, using Monte Carlo simulation. Evaluate thousands of scenarios in seconds, and see instantly updated charts and statistics, each time you ask "what if". Software Developer Tools: Solver Platform SDK makes it easy to solve any type or size of optimization problem in your Visual Basic, VB.NET, C/C++, C#, Java, or MATLAB program. And it's easy to deploy your application with our flexible licensing for software vendors and corporate developers. |
Solver.com
From Frontline Systems, developers of the Excel Solver.
|
||
Solver tutorials
Learn to use optimization for resource allocation, and Monte Carlo simulation for risk analysis of your model.
Copyright © 2010 Frontline Systems, Inc.