Using set covering with item sampling to analyze the infeasibility of linear programming test assembly models

This article shows how set covering with item sampling (SCIS) methods can be used in the analysis and preanalysis of linear programming models for test assembly (LPTA). LPTA models can construct tests, fulfilling a set of constraints set by the test assembler. Sometimes, no solution to the LPTA model exists. The model is then said to be infeasible. Causes of infeasibility can be difficult to find. A method is proposed that constitutes a helpful tool for test assemblers to detect infeasibility beforehand and, in the case of infeasibility, give insight into its causes. This method is based on SCIS. Although SCIS can help to detect feasibility or infeasibility, its power lies in pinpointing causes of infeasibility such as irreducible infeasible sets of constraints. Methods to resolve infeasibility are also given, minimizing the model deviations. A simulation study is presented, offering a guide to test assemblers to analyze and solve infeasibility. Index terms: mathematical programming, linear programming, infeasibility, optimal test assembly, test assembly, test design, set covering, item sampling.