Model Entities

Introduction

Model entities are the basic building blocks used to implement an optimization model. There are five types of model entities that are present in almost all AMPL programs:

  • Sets — set
  • Parameters — param
  • Variables — var
  • Objective Functions — minimize or maximize
  • Constraints — subject to or s.t.

NOTE: There are other less common model entities, such as Arcs and Nodes, but we'll talk about them in another place.

Sets and parameters are data entities that hold values supplied by the modeler. Variables are also data entities, but usually the modeler does not assign any value to them, rather, it leaves that task to the solver. One exception is when the modeler wants to set a starting solution before calling the solver.

Objective functions and constraints are mathematical entities that hold math expressions or formulas. They are used to represent the mathematical relations present in given optimization problem formulation. A typical mathematical program will have only one objective function that the modeler wants to optimize (minimize/maximize), and multiple constraints.

There is a direct correspondence between AMPL model entities and the typical objects of algebraic formulations. The example below shows how a simple algebraic formulation for the bin packing problem can be translated into AMPL using the five entities above.

\textbf{Bin Packing Problem}\\ \text{Let $I$ be the set of available items}\\ \text{Let $W$ be the bin capacity}\\ \text{Let $v_i$ be the value of item $i \in I$}\\ \text{Let $w_i$ be the weight of item $i \in I$}\\ \text{}\\ \text{The decision variables are:}\\ x_i = \begin{cases} \text{1, if item $i \in I$ is selected} \\ \text{0, otherwise} \end{cases}\\ \text{}\\ \text{The objective is to maximize $\displaystyle z = \sum_{i \in I} v_i x_i$}\\ \text{Subject to:}\\ \displaystyle \sum_{i \in I} w_i x_i \le W \\ x_i \in \{0,1\} # Bin Packing Problem set I; param W; param v{I}; param w{I}; # Decision variables var x{I} binary; # Objective maximize z: sum{i in I} v[i]*x[i]; subject to CT: sum{i in I} w[i]*x[i] <= W;

Usually, the first thing that we do in an AMPL program is to declare all the model entities that compose the model we are implementing (see Program Structure).

Declaring Sets, Parameters and Variables

The declaration statements of sets, parameters and variables have similar syntaxes:

set I ; param W ; var cost ;

We often want to associate each member of a set with a specific value. For instance, in the bin packing problem, each item has its own weight, so we want to declare a parameter collection in which each of its members is associated with a specific item of set I:

param w {I} ;

The indexing expression indicates (1) how many members are in that collection and (2) how can each member be accessed or refered to. In the example above, we indicate that the parameter collection w will have the same number of members that are in set I, each associated with a specific member of that set.

We can have collections of any type of model entity, and all collections are declared in a similar way, using indexing expressions.

When declaring sets, parameters and variables we have the option to give them special attributes. Attributes are properties that we want to ensure that our entities have. For instance, in the bin packing formulation above, we have used attributes to restrict the domain of our x variable collection to the binary set (0 or 1):

var x {I} binary ;

Declaring Objective Functions and Constraints

The declaration statements of objective functions and constraints have similar syntaxes:

maximize z : sum{i in I} v[i]*x[i] ; s.t. CT : sum{i in I} w[i]*x[i] <= W ;

Objective functions hold math expressions whose value we want to maximize/minimize. Constraints hold the math formulas (equalities and inequalities) that we use to model our optimization problem. The s.t. keyword is the abbreviation of the subject to keyword. They can be used interchangeably in constraint declarations.

We often want to declare one constraint for each member of a given set. This is the case whenever we have a for all\forall — symbol in a constraint collection that we want to implement, such as:

\displaystyle \sum_{i \in I} y_{ij} = 1 \forall j \in J

We can declare this constraint collection by using indexing expressions, similarly to how we have used them in the previous section to declare a collection of variables:

s.t. CT {j in J} : sum{i in I} y[i,j] = 1 ;