3.4 A Technique for Model Documentation

Structure of the Formulation

We shall now set out a systematic structure for writing mathematical formulations so that they are readily comprehensible. A bonus is that in this form it becomes almost mechanical to translate the mathematical formulation into an algebraic modelling language such as XPRESS. The following notation, based on that developed by the late Martin Beale, is therefore recommended:

  1. Subscripts: Use lower case letters, typically towards the middle of the alphabet. These define the classes of objects in the model, e.g. components r and qualities q in the above example.
  2. Sets: These may be needed to give precise definitions of ranges of summation or the conditions under which a constraint, variable or constant is defined. Use capital letters.
  3. Constants: These are items whose values are known when the model is to be optimised. Note that their values may vary over time and they may be held in what are known as "variables" in a computer programming language. But they are fixed in the LP matrix and therefore stand distinct from the decision variables, whose values are to be determined. Use capital letters for the name of the constant together with lower case subscripts to show the combination of objects for which the constant may exist (possibly further restricted by a set).
  4. Variables: These are the decision variables of the model. Use lower case letters, typically towards the end of the alphabet, e.g. x, y together with lower case subscripts to show the combination of objects for which the decision variable may exist. As there are not sufficient letters for the number of distinct classes of decision variable, feel free to use upper case "literal subscripts" to distinguish decision variables, e.g. xBUYr, xMAKEr for the quantities of component r bought and made respectively.
  5. Constraints (including the objective function). List with the objective first.

Never use one letter to mean two different things. But feel free to develop composite letters by using capital letters as "literal subscripts" that never take numerical values. On the other hand, lower case subscripts always take numerical values.

There is no objection to quite long names for constants if you find them more mnemonic, though with some languages it is convenient to restrict them to 6 letters excluding genuine subscripts. Variable names should be shorter, since MPS format restricts the variable name including the subscripts to be at most 8 characters, and some subscripts may need more than one character.

Benefits of the Approach

This approach may seem less straightforward than starting with the constraints and then explaining the symbols that occur in them. But it is recommended for the following reasons.

  1. A definition of all subscripts defines the scope of the model. If the subscripts are used consistently, the definition of subscripted constants and variables become clearer and can be more compact, as illustrated in sections 3.6 - 3.8.
  2. Sets may not be needed on simple models. But they often provide the only compact way to record a precise definition of the domain of a summation, or the conditions for the existence of a variable or constraint. For example, in the simple blending problem some qualities may have only their maximum or their minimum values constrainted, not both. We might then define SQL for the set of qualities with a lower limit and SQU for the set of qualities with an upper limit. Then we specify that QMINq and the corresponding quality constraint only exist for q є SQL and similarly for qualities with an upper limit.
  3. The constants are part of the definition of the problem. So they logically precede the decision variables, which represent an approach to its solution.
  4. The notation should distinguish clearly between the constants, or assumed quantities, and the decision variables that are to be determined by the model. This distinction may not be clear from the context. For example, the amounts of each product to be made may be either data or variables. Possible confusion is avoided by always using capital letters for constants and lower case letters for decision variables.

This notation conflicts with that used in more theoretical work, where one has fewer types of constant and variable, and can reserve letters near the beginning of the alphabet for constants and letters near the end of the alphabet for variables. On the other hand, in applied mathematical programming there is not merit in using capital letters to denote matrices, since many constants and variables have three or more subscripts, and in any case their significance is clarified if the subscripts are written out explicitly.

In most computer programming languages we have only one alphabet but we may use names with two or more letters. This can be reconciled with conventional mathematical notation if all letters after the first are written as subscripts, but in capitals to distinguish them from subscripts that take numerical values.

previous contents next

Comments