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	Upper Bound
x1	1	0.75	INFINITY
x2	3	1.75	INFINITY
x3	2	0	INFINITY
x4	4	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.