# A worked example

This section

The example in this section is adapted from McCarl ([McC98]), and is meant to demonstrate the tools that were discussed in the previous sections. The example model is used to illustrate the detection of infeasibility and unboundedness. In addition, the example is used to find the cause of an unrealistic solution.

## Model Formulation

A Farm planning model

The model considers a collection of farms. For each of these farms several decisions have to be made. These decisions are

the amount of cattle to keep,

the amount of land to grow a particular crop,

the amount of additional land to rent, and

the amount of inter-farm crop transport.

The objective of the farm model is to maximize a social welfare function, which is modeled as the total profit over all farms.

Notation

The following notation is used to describe the symbolic farm planning model.

Land requirement

The *land requirement* constraint makes sure that the total amount of
land needed to keep cattle and to grow crops does not exceed the amount
of available land (including rented land).

Upper bound on rental

The total amount of rented land on a farm cannot exceed its maximum.

Crop-on-hand

The *crop-on-hand* constraint is a crop balance. The total amount of
crop exported, crop sold, and crop that has been used to feed the cattle
cannot exceed the total amount of crop produced and crop imported.

Cattle requirement

The cattle requirement constraint ensures that every farm keeps at least a pre- specified amount of cattle.

Profit definition

The total profit is defined as the net profit from selling crops, minus crop transport cost, minus rental fees, plus the net profit of selling cattle.

The generated problem

Once the above farm model is solved, the math program inspector will display the variable and constraint tree plus the matrix block view as illustrated in Fig. 50. The solution of the particular farm model instance has already been presented in Fig. 51.

## Investigating Infeasibility

Introducing an infeasibility

In this section the math program inspector will be used to investigate an artificial infeasibility that is introduced into the example model instance. This infeasibility is introduced by increasing the land requirement for cattle from 0.5 to 10.

Locating infeasible constraints

By selecting the **Infeasible Constraints** command from the **Actions**
menu, all violated constraints as well as all variables that do not
satisfy their bound conditions, are bookmarked. Note, that the solution
values used to identify the infeasible constraints and variables are the
values returned by the solver after infeasibility has been concluded.
The exact results of this command may depend on the particular solver
and the particular choice of solution method (e.g. primal simplex or
dual simplex).

Substructure causing infeasibility

By selecting the **Substructure Causing Infeasibility** command from the
**Actions** menu a single constraint is bookmarked. In this example, one
artificial violation variable could not be reduced to zero by the solver
used, which resulted in a single infeasibility.
Fig. 52 indicates that this infeasibility can be
resolved by changing the right-hand-side of the ‘MinCattle’ constraint
for ‘Farm 1’. A closer investigation shows that when the minimum
requirement on cattle on ‘Farm 1’ is decreased from 50 to 30, the
infeasibility is resolved. This makes sense, because one way to resolve
the increased land requirement for cattle is to lower the requirements
for cattle.

Locating an IIS

By selecting the **Irreducible Inconsistent System** command from the
**Actions** menu, an IIS is identified that consists of the three
constraints ‘RentalLand’, ‘Land’ and ‘MinCattle’, all for ‘Farm 1’ (see
Fig. 53).

Resolving the infeasibility

The above IIS provides us with three possible model changes that together should resolve the infeasibility. These changes are

increase the availability of land for ‘Farm 1’,

change the land requirement for cattle on ‘Farm 1’, and/or

decrease the minimum requirement on cattle on ‘Farm 1’.

It is up to the producer of the model instance, to judge which changes are appropriate.

## Investigating Unboundedness

Introducing unboundedness

The example model is turned into an unbounded model by dropping the constraints on maximum rented land, and at the same time, by multiplying the price of cattle on ‘Farm 1’ by a factor 100 (representing a unit error). As a result, it will become infinitely profitable for ‘Farm 1’ to rent extra land to keep cattle.

Substructure causing unboundedness

By selecting the **Substructure Causing Unboundedness** command from the
**Actions** menu four individual variables are bookmarked, and all of
them are related to ‘Farm 1’. Together with all constraints that contain
two or more bookmarked variables these bookmarked variables form the
problem structure that is subject to closer investigation. From the
optimal solution of the auxiliary model it becomes clear that the
‘FeedCattle’ variable, the two ‘GrowCrops’ variables and the ‘LandRent’
variables tend to get very large, as illustrated in
Fig. 54.

Resolving the unboundedness

Resolving the unboundedness requires you to determine whether any of the variables in the problem structure should be given a finite bounds. In this case, specifying an upper bound on the ‘RentalLand’ variable for ‘Farm 1’ seems a natural choice. This choice turns out to be sufficient. In addition, when inspecting the bookmarked variables and constraints on the Matrix View tab, the red color of the objective function coefficient for the ‘FeedCattle’ variable for ‘Farm 1’ indicates a badly scaled value.

## Analyzing an Unrealistic Solution

Introducing an unrealistic solution

The example model is artificially turned into a model with an unrealistic solution by increasing the crop yield for corn on ‘Farm 2’ from 128 to 7168 (a mistake), and setting the minimum cattle requirement to zero. As a result, it will be unrealistically profitable to grow corn on ‘Farm 2’.

Inspecting the unrealistic solution

Once the changes from the previous paragraph have been applied, the solution of the model is shown in Fig. 55. From the Variable Solution tab it can indeed be seen that the profit is unrealistically large, because a large amount of corn is grown on ‘Farm 2’, moved to ‘Farm 1’ and sold on ‘Farm 1’. Other striking numbers are the large reduced cost values associated with the ‘FeedCattle’ variable on ‘Farm 2’ and the ‘GrowCrops’ variable for hay on ‘Farm 2’.

Badly scaled matrix coefficients

When investigating an unrealistic solution, an easy first step is to
look on the Matrix View tab to see whether there exist matrix
coefficients with unrealistic values. For this purpose, first open the
Matrix View tab in symbolic view. Blocks that are colored red indicate
the existence of badly scaled values. By double clicking on such a
block, you will zoom in to inspect the matrix coefficients at the
individual level. In our example, the symbolic block associated with the
‘GrowCrops’ variable and the ‘CropOnHand’ constraint is the red block
with the largest value. When you zoom in on this block, the data error
can be quickly identified (see Fig. 56). You
can also use the **Scale Model** command from the **Actions** menu to
let AIMMS calculate scaling factors that can be used to reduce the
amount of badly scaled values in the coefficient matrix.

Primal and dual contributions \(\ldots\)

A second possible approach to look into the cause of an unrealistic
solution is to focus on the individual terms of both the primal and dual
constraints. In a primal constraint each term is the multiplication of a
matrix coefficient by the value of the corresponding variable. In the
Math Program Inspector such a term is referred to as the *primal
contribution*. Similarly, in a dual constraint each term is the
multiplication of a matrix coefficient by the value of the corresponding
shadow price (i.e. the dual variable). In the Math Program Inspector
such a term is referred to as the *dual contribution*.

\(\ldots\) can be unrealistic

Whenever primal and/or dual contributions are large, they may indicate
that either the corresponding coefficient or the corresponding variable
value is unrealistic. You can discover such values by following an
iterative process that switches between the Variable Solution tab and
the Constraint Solution tab by using either the **Variable Statistics**
or the **Constraint Statistics** command from the right-mouse popup
menu.

Procedure to resolve unrealistic solutions

The following iterative procedure can be followed to resolve an unrealistic solution.

Sort the variable values retrieved through the Variable Solution tab.

Select any unrealistic value or reduced cost, and use the right-mouse popup menu to switch to the Variable Statistics tab.

Find a constraint with an unrealistic dual contribution.

If no unrealistic dual contribution is present, select one of the constraints that is likely to reveal some information about the construction of the current variable (i.e. most probably a binding constraint).

Use the right-mouse popup menu to open the Constraint Statistics tab for the selected constraint.

Again, focus on unrealistic primal contributions and if these are not present, continue the investigation with one of the variables that plays an important role in determining the level value of the constraint.

Repeat this iterative process until an unrealistic matrix coefficient has been found.

You may then correct the error and re-solve the model.

Inspecting primal contributions

In the example, the ‘Profit’ definition constraint indicates that the profit is extremely high, mainly due to the amount of corn that is sold on ‘Farm 1’. Only two constraints are using this variable, of which one is the ‘Profit’ definition itself. When inspecting the other constraint, the ‘CropOnHand’ balance, it shows that the corn that is sold on ‘Farm 1’ is transported from ‘Farm 2’ to ‘Farm 1’. This provides us with a reason to look into the ‘CropOnHand’ balance for corn on ‘Farm 2’. When inspecting the primal contributions for this constraint the data error becomes immediately clear (see Fig. 57).

Inspecting dual contributions

The same mistake can be found by starting from an unrealistic reduced cost. Based on the large reduced cost for the ‘FeedCattle’ variable on ‘Farm 2’, the dual contributions indicate that the unrealistic value is mainly caused by an unrealistic value of the shadow price associated with the ‘Land’ constraint on ‘Farm 2’. While investigating this constraint you will notice that the shadow price is rather high, because the ‘GrowCrops’ variable for corn on ‘Farm 2’ is larger than expected. The dual contribution table for this variable shows a very large coefficient for the ‘CropOnHand’ constraint for corn on ‘Farm 2’, indicating the data error (see Fig. 58).

Combining primal and dual investigation

The above two paragraphs illustrate the use of just primal contributions or just dual contributions. In practice you may very well want to switch focus during the investigation of the cause of an unrealistic solution. In general, the Math Program Inspector has been designed to give you the utmost flexibility throughout the analysis of both the input and output of a mathematical program.