An empirical analysis of infeasibility diagnosis for instances of linear programming blending models

This study reports empirical findings for applying three methods of diagnosing infeasibility, based on: (1) Phase I price aggregation, (2) irreducible infeasible subsystems, and (3) successive bounding. The problem class is the blending problem, most notably used in the petrochemical industry. Three variations of the blending problem are considered, distinguished by levels of complexity. The simplest case is static, ignores quality constraints, sharply divides raw feed and blend stocks, and is not regional. The second variation is multiregional. The third variation is a refinery model that removes all of the simplifications. The experimental design consists of generating infeasible instances from base cases, where each instance for each of the base cases is a different source of infeasibility. The three methods are applied to each instance, usually requiring some additional analysis effort. The methods are evaluated by two criteria: (1) how much analysis effort is needed to go from the information provided to a diagnosis of the cause; and, (2) the quality of the final diagnosis.