Optimization Model Basics

The optimization algorithms we have discussed so far are all unconstrained problems. The next three sections deal with constrained problems. Many of the constrained problems are derived from theoretical models where the solution is found by finding the configuration where a certain quantity reaches a maximum or a minimum.

In order to facilitate working with such models, the Extreme Optimization Numerical Libraries for .NET includes a framework for defining such models that allows for easier bookkeeping and managing the results.

All classes that implement optimization problems with constraints inherit from an abstract base class, OptimizationModel.

An optimization model has three main components:

1. An objective function. This is the function that needs to be optimized.

2. A collection of decision variables. The solution to the optimization problem is the set of values of the decision variables for which the objective function reaches its optimal value.

3. A collection of constraints that restrict the values of the decision variables.

The OptimizationModel class provides a common API for defining and accessing variables and constraints, as well as other properties of each model.

We will now discuss each of these components in more detail.

Optimization problems can be classified in terms of the nature of the objective function and the nature of the constraints. Special forms of the objective function and the constraints give rise to specialized algorithms that are more efficient. From this point of view, there are four types of optimization problems, of increasing complexity.

An Unconstrained optimization problem is an optimization problem where the objective function can be of any kind (linear or nonlinear) and there are no constraints. These types of problems are handled by the classes discussed in the earlier sections.

A linear program is an optimization problem with an objective function that is linear in the variables, and all constraints are also linear. Linear programs are implemented by the LinearProgram class.

A quadratic program is an optimization problem with an objective function that is quadratic in the variables (i.e. it may contain squares and cross products of the decision variables), and all constraints are linear. A quadratic program with no squares or cross products in the objective function is a linear program. Quadratic programs are implemented by the QuadraticProgram class.

A nonlinear program is an optimization problem with an objective function that is an arbitrary nonlinear function of the decision variables, and the constraints can be linear or nonlinear. Nonlinear programs are implemented by the NonlinearProgram class.

Finding the optimal values of the decision variables is the goal of solving an optimization model. In the optimization framework, variables are implemented by the DecisionVariable class.

Each variable has a Name, which may be generated automatically. The LowerBound and UpperBound properties specify lower and upper bounds for the values the variable can take. After the solution of the model has been computed, the Value property returns the value of the variable in the optimal solution.

DecisionVariable objects are created by calling one of the overloads of the optimization model's AddVariable method. In some cases, they may also be created automatically.

An optimization model's variables can be accessed through its Variables property. Individual variables can be accessed by name or by position. The variable's Position property returns the variable's index in the collection.

Specific models may have specialized versions of the decision variables. For example, both linear and quadratic programs use variables of type LinearProgramVariable, which inherits from DecisionVariable and has an extra Cost property that represents the coefficient of the variable in the linear portion of the objective function.

Constraints limit the possible values for the decision variables in an optimization model. There are several types of constraints. The classes that implement them all inherit from the Constraint class.

Each constraint also has a Name, which may again be generated automatically. The LowerBound and UpperBound properties specify lower and upper bounds for the value of the constraint. After the solution of the model has been computed, the Value property returns the value of the constraint in the optimal solution.

There are two types of constraints: linear and nonlinear.

Linear constraints express that a linear combination of the decision variables must lie within a certain range. They are implemented by the LinearConstraint class. The coefficients can be accessed through the Gradient property. LinearConstraint objects are created by calling one of the overloads of the optimization model's AddLinearConstraint method. In some cases, they may also be created automatically.

Nonlinear constraints express that the value of some arbitrary function of the decision variables must lie within a certain range. They are implemented by the NonlinearConstraint class. The constraint function can be accessed through the ConstraintFunction. The gradient of this function, which is needed during the optimization process, is the FastConstraintGradient If it is not supplied, a numerical approximation is used. NonlinearConstraint objects are created by calling one of the overloads of the optimization model's AddNonlinearConstraint method.

An optimization model's constraints can be accessed through its Constraints property. Individual constraints can be accessed by name or by position. The variable's Position property returns the constraint's index in the collection.

Reference

Other Resources