Maximum feasibility problem for continuous linear inequalities with applications to fuzzy linear programming

Systems of linear inequalities are important tools to formulate optimization problems. However, the feasibility of the whole system was often presumed true in most models. Even if an infeasible system could be detected, it is in general not easy to tell which part of the system caused it. This motivates the study of continuous linear inequalities, given no information whether it is feasible or not, what is the largest possible portion of the system that can be remained in consistency? We first propose a bisection-based algorithm which comes with an auxiliary program to answer the question. For further accelerating the algorithm, several novel concepts, one called "constraint weighting" and the other called "shooting technique", are introduced to explore intrinsic problem structures. This new scheme eventually replaces the bisection method and its validity can be justified via a solid probabilistic analysis. Numerical examples and applications to fuzzy inequalities are reported to illustrate the robustness of our algorithm.