The LP Procedure

Example 4.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:

\[ \begin{array}{ll} \max & x+y+z+w \\ \mr{subject\ to} & x+3y+2z+4w \le 5 \\ & 3x+y+2z+w \le 4 \\ & 5x+3y+3z+3w = 9 \\ & x,\, y, \, z, \, w \ge 0 \\ \end{array} \]

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 4.9.1.

Output 4.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.