What Makes a Model Hard to Solve?

Some optimization models are easy to solve, others are hard. "Hard" models may require a lot 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:

  1. The mathematical relationships between the objective and constraints, and the decision variables.
  2. The size of the model (number of decision variables and constraints) and its sparsity.
  3. The use of integer variables - memory and solution time may rise exponentially as you add more integer variables.

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 obtained solution is optimal.  These relationships also have a direct bearing on the maximum size of models that can be solved.

A model that consists of mostly linear relationships but a few nonlinear relationships generally must be solved with more "computationally expensive" nonlinear optimization methods.  The same is true of models with mostly linear or smooth nonlinear relationships, but a few nonsmooth relationships.  So even a single IF( ) or CHOOSE( ) function that depends on the decision variables can turn an otherwise 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.

Problem Size and Solution Time

Below are some general statements about problem size and 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 the objective and constriants are linear functions of the decision variables (and hence convex) can be solved with 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 with 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 necessarily globally optimal.

Nonsmooth optimization problems -- where the relationships include functions like IF(), CHOOSE(), LOOKUP() -- can be solved with up to 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.