This NEOS Optimization Guide provides information about the field of optimization and many of its sub-disciplines. The focus of the content is on the resources available for solving optimization problems, including the solvers available on the NEOS Server.
Optimization is an important tool in making decisions and in analyzing physical systems. In mathematical terms, an optimization problem is the problem of finding the best solution from among the set of all feasible solutions.
Constructing a Model
The first step in the optimization process is constructing an appropriate model; modeling is the process of identifying and expressing in mathematical terms the objective, the variables, and the constraints of the problem.
- An objective is a quantitative measure of the performance of the system that we want to minimize or maximize. In manufacturing, we may want to maximize the profits or minimize the cost of production, whereas in fitting experimental data to a model, we may want to minimize the total deviation of the observed data from the predicted data.
- The variables or the unknowns are the components of the system for which we want to find values. In manufacturing, the variables may be the amount of each resource consumed or the time spent on each activity, whereas in data fitting, the variables would be the parameters of the model.
- The constraints are the functions that describe the relationships among the variables and that define the allowable values for the variables. In manufacturing, the amount of a resource consumed cannot exceed the available amount.
Determining the Problem Type
The second step in the optimization process is determining in which category of optimization your model belongs. The page Types of Optimization Problems provides some guidance to help you classify your optimization model; for the various optimization problem types, there is a linked page with some basic information, links to algorithms and software, and online and print resources.
Selecting Software
The third step in the optimization process is selecting software appropriate for the type of optimization problem that you are solving. Optimization software comes in two related but very different kinds of packages:
- Solver software is concerned with finding a solution to a specific instance of an optimization model. The solver takes an instance of a model as input, applies one or more solution methods, and returns the results.
- Modeling software is designed to help people formulate optimization models and analyze their solutions. A modeling system takes as input a description of an optimization problem in a symbolic form and allows the solution output to be viewed in similar terms; conversion to the forms required by the algorithm(s) is done internally. Modeling systems vary in the extent to which they support importing data, invoking solvers, processing results, and integrating with larger applications. Modeling systems are typically built around a modeling language for representing the problem in symbolic form. The modeling language may be specific to the system or adapted from an existing programming or scripting language.
Most modeling systems support a variety of solvers, while the more popular solvers can be used with many different modeling systems. Because packages of the two kinds are often bundled for convenience of marketing or operation, the distinction between them is sometimes obscured, but it is important to keep in mind when attempting to sort through the many alternatives available.
Commercial vs. Open Source Solvers
Commercial solvers are developed with considerable effort and, while usually more robust and reliable, they often are quite expensive. Some commercial systems are available for free under reasonable conditions for educational purposes and academic research. Many offer free size-limited student (or demo) versions for experimentation with small problem instances. Open source solvers make their source code freely available under one of the standard open source licenses; many of these are available through the COIN-OR repository (www.coin-org.org). Many of the open-source solvers are also available as precompiled binaries for the more popular platforms.
NEOS Solvers
If you do not have access to the solver that you need at your institution and you prefer not to download a demo version or a free solver, you can access for free a number of commercial and freely available solvers on the NEOS Server. The available solvers are listed by problem type and solver name.