The LP Procedure

## Example 5.9 An Infeasible Problem

This is an example of the Infeasible Information Summary that is displayed when an infeasible problem is encountered. Consider the following problem:

Examination of this problem reveals that it is unsolvable. Consequently, PROC LP identifies it as infeasible. The following program attempts to solve it.

```data infeas;
format _id_ \$6.;
input _id_ \$ x1-x4 _type_ \$ _rhs_;
datalines;
profit   1    1    1    1    max  .
const1   1    3    2    4    le   5
const2   3    1    2    1    le   4
const3   5    3    3    3    eq   9
;
```

The results are shown in Output 5.9.1.

Output 5.9.1 The Solution of an Infeasible Problem
The LP Procedure

Problem Summary
Objective Function Max profit
Rhs Variable _rhs_
Type Variable _type_
Problem Density (%) 77.78

Variables Number

Non-negative 4
Slack 2

Total 6

Constraints Number

LE 2
EQ 1
Objective 1

Total 4

```ERROR: Infeasible problem. Note the constraints in the constraint summary
that are identified as infeasible. If none of the constraints are
flagged then check the implicit bounds on the variables.
```

The LP Procedure

Solution Summary

Infeasible Problem
Objective Value 2.5

Phase 1 Iterations 2
Phase 2 Iterations 0
Phase 3 Iterations 0
Integer Iterations 0
Integer Solutions 0
Initial Basic Feasible Variables 5
Time Used (seconds) 0
Number of Inversions 2

Epsilon 1E-8
Infinity 1.797693E308
Maximum Phase 1 Iterations 100
Maximum Phase 2 Iterations 100
Maximum Phase 3 Iterations 99999999
Maximum Integer Iterations 100
Time Limit (seconds) 120

The LP Procedure

Variable Summary
Col Variable Name Status Type Price Activity Reduced Cost
1 x1 BASIC NON-NEG 1 0.75 0
2 x2 BASIC NON-NEG 1 1.75 0
3 x3   NON-NEG 1 0 0.5
4 x4   NON-NEG 1 0 0
*INF* const1 BASIC SLACK 0 -1 0
6 const2   SLACK 0 0 0.5

The LP Procedure

Constraint Summary
Row Constraint
Name
Type S/S Col Rhs Activity Dual Activity
1 profit OBJECTVE . 0 2.5 .
*INF* const1 LE 5 5 6 0
3 const2 LE 6 4 4 -0.5
4 const3 EQ . 9 9 0.5

The LP Procedure

Infeasible Information Summary
Infeasible Row const1
Constraint Activity 6
Row Type LE
Rhs Data 5

Variable Coefficient Activity Lower Bound Upper Bound
x1 1 0.75 0 INFINITY
x2 3 1.75 0 INFINITY
x3 2 0 0 INFINITY
x4 4 0 0 INFINITY

Note the information given in the Infeasible Information Summary for the infeasible row CONST1. It shows that the inequality row CONST1 with right-hand side 5 was found to be infeasible with activity 6. The summary also shows each variable that has a nonzero coefficient in that row and its activity level at the infeasibility. Examination of these model parameters might give you a clue as to the cause of infeasibility, such as an incorrectly entered coefficient or right-hand-side value.

 Previous Page | Next Page | Top of Page