Linear Programming Problems: Detecting Infeasibility, Methods, and Troubleshooting

How can you detect that a LPP has no feasible solution?

An LPP has no feasible solution when its set of constraints are contradictory, meaning there is no point in the solution space that satisfies all conditions simultaneously, rendering any optimization impossible.

Understanding Feasibility in Linear Programming Problems (LPPs)

Linear Programming Problems (LPPs) are mathematical models used to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. At its core, an LPP consists of an objective function to be optimized and a set of linear constraints that define the boundaries of the permissible solutions. The feasible region is the set of all points that satisfy every constraint of the LPP. If this region is empty, the LPP is said to have no feasible solution or to be infeasible. This indicates a fundamental flaw or contradiction in the problem's formulation.

Key Indicators and Methods for Detecting Infeasibility

Detecting an infeasible LPP is crucial for problem-solving, as it signals that the current model cannot be optimized. Various methods, depending on the complexity of the LPP, can reveal this condition.

Graphical Method (for Two Variables)

For LPPs with only two decision variables, the graphical method offers a clear visual way to detect infeasibility.

• Plotting Constraints: Each linear inequality constraint defines a half-plane. The intersection of all these half-planes forms the feasible region.
• Absence of an Overlap: If, after plotting all constraints, there is no common area where all shaded regions overlap, then the feasible region is empty, and the LPP has no feasible solution. This often appears as parallel constraints pushing away from each other, or constraints forming a "closed" region that is impossible to satisfy simultaneously.

Simplex Method (for Multiple Variables)

The Simplex method is an iterative algorithm used to solve LPPs with more than two variables. It systematically moves from one vertex of the feasible region to another, seeking the optimal solution. Infeasibility is detected through specific outcomes during this process:

• Artificial Variables: When setting up an LPP for the Simplex method, especially for "greater than or equal to" (≥) or equality (=) constraints, artificial variables are introduced. These variables are temporary placeholders that help initiate the Simplex algorithm.
• Positive Artificial Variables in Optimal Tableau: If, at the end of the Simplex algorithm (when all coefficients in the objective row are non-negative for a maximization problem, or non-positive for a minimization problem), one or more artificial variables remain positive in the basic solution, it indicates that the original constraints cannot be satisfied. The presence of positive artificial variables in the final basic solution signifies an infeasible problem.

Big M Method and Two-Phase Method

These are variations of the Simplex method specifically designed to handle LPPs requiring artificial variables. They provide systematic ways to detect infeasibility:

• Big M Method: In this method, a very large penalty (M) is assigned to artificial variables in the objective function. The algorithm attempts to drive these artificial variables to zero to minimize the penalty. If, in the optimal solution, any artificial variable remains in the basis with a positive value, the LPP is infeasible.
• Two-Phase Method: This method explicitly separates the process into two phases.
  • Phase I: The objective function is replaced with a new objective to minimize the sum of all artificial variables. If the minimum value of this sum is greater than zero at the end of Phase I, it means at least one artificial variable could not be driven to zero, indicating the LPP is infeasible.
  • Phase II: If Phase I yields a minimum sum of zero (meaning all artificial variables are zero), the original objective function is then optimized in Phase II.

Mathematical Intuition and Contradictory Constraints

Beyond algorithmic detection, recognizing the underlying mathematical structure can hint at infeasibility:

• Direct Contradiction: Some constraint sets are inherently contradictory. For example, if an LPP includes the constraints x ≤ 5 and x ≥ 10 simultaneously, there is no value of x that can satisfy both conditions, immediately indicating infeasibility.
• Conflicting Bounds: Similarly, constraints like x + y ≤ 10 and x + y ≥ 15 create an impossible scenario.

Implications and Troubleshooting

An infeasible LPP means that the real-world scenario it models cannot exist under the given parameters. When an LPP is found to be infeasible:

• Review Model Formulation: The first step is to carefully re-examine the problem's constraints. Are they correctly translated from the real-world problem into mathematical inequalities?
• Check Data Accuracy: Errors in data input (e.g., resource availability, demand limits) can lead to contradictory constraints.
• Evaluate Realism of Constraints: Are the constraints too restrictive or unrealistic? Perhaps certain conditions cannot physically or practically be met simultaneously.
• Consult Stakeholders: If the model represents a business or operational problem, discuss the infeasibility with domain experts. They may reveal overlooked factors or suggest adjustments to the constraints.

Detecting an infeasible LPP is not a failure of the method but a critical insight into the problem's underlying structure, prompting a necessary re-evaluation of its assumptions and constraints.