In the ideal world, all models would return an optimal solution. Unfortunately, this is not the case. Sooner or later, you are bound to run across either an infeasible or unbounded model. This is particularly true in the development phase of a project when the model will tend to suffer from typographical errors.

Tracking down an error in a large model can prove to be a daunting task. The DEBUG command is useful in narrowing the search for problems in both infeasible and unbounded linear programs. A small portion of the original model is isolated as the source of the problem. This allows you to focus your attention on a subsection of the model in search of formulation or data entry errors.

The DEBUG command identifies two types of sets: sufficient and necessary. Removing any sufficient set object from the model is sufficient to fix the entire model. Not all models will have a sufficient set. In which case, they will have a necessary set with the property that removing any object from this set fixes the remaining objects within that set.

As an example, suppose you have an infeasible model. If the complete model would be feasible except for a bug in a single row, that row will be listed as part of the sufficient set. If the model has a necessary set, then, as long as all of them are present, the model will remain infeasible.

The following example illustrates. The coefficient .55 in ROW4 should have been 5.5:

: look all

 

MODEL:

 1][ROW1] Max = 3*X + 7*Y;

 2][ROW2] X + 2*Y <= 3;

 3][ROW3] 2*X + Y <= 2;

 4][ROW4] 0.55*X + Y >=4;

END

When we attempt to solve this formulation, we get the following error:

: go

[Error Code:   81]

No feasible solution found.

       Variable           Value        Reduced Cost

              X        50.00000            0.000000

              Y       -23.50000            0.000000

            Row    Slack or Surplus      Dual Price

           ROW1        0.000000           -1.000000

           ROW2        0.000000            8.500000

           ROW3       -74.50000            0.000000

           ROW4        0.000000           -10.00000

Next, if we run the DEBUG command, we are presented with the following report:

: debug

 Sufficient Rows:

 ROW4]  .55 X + Y >=   4

 Necessary Rows:

 ROW2]  X + 2 Y <=   3

 Necessary Variable Bounds:

 Y >=  0

The DEBUG command has correctly identified that the erroneous ROW4, when eliminated, is sufficient to make the entire model feasible.

The debug feature operates in a similar manner for unbounded models. In the following example, we introduced an error by placing a minus sign instead of a plus sign in front of variable Z3 in ROW3. A look at ROW3 reveals that Z3 can be increased indefinitely, leading to an unbounded objective.

: look all

MODEL:

  1][ROW1] Max = 12*X1 + 13*X2 + 22*Y1 + 23*Z1 +

  2]             28*Z2 + X3 + Y3 + Z3;

  3][ROW2] X1 + X2 + X3 <= 400;

  4][ROW3] Y1 + Y2 + Y3 - Z3 <= 500;

  5][ROW4] Z1 + Z2 <= 500;

END

The resulting model is unbounded and, when issuing the Solver|Solve command, we receive the unbounded error message:

: go

 

[Error Code:   82]

 

Unbounded solution.

Issuing the DEBUG command, we receive the following breakdown:

: debug

Sufficient Variables:

Z3

Necessary Variables:

Y1

The DEBUG command has successfully determined that bounding Z3 is sufficient to bound the entire model.

Typically, the DEBUG command helps to substantially reduce the search effort. The first version of this feature was implemented in response to a user who had an infeasible model. The user had spent a day searching for a bug in a model with 400 constraints. The debug feature quickly found a necessary set with 55 constraints, as well as one sufficient set constraint. The user immediately noticed that the right-hand side of the sufficient set constraint was incorrect.