Abstract
We consider linear systems of equations A(p) x = b(p), where the parameters p are linearly dependent and come from prescribed boxes, and the sets of solutions (defined in various ways) which have linear boundary. One fundamental problem is to compute a box being inside a parametric solution set.
We first consider parametric tolerable solution sets (being convex polyhedrons). For such solution sets we prove that finding a maximal inner box is an NP-hard problem.
This justifies our exponential linear programming methods for computing maximal inner boxes. We also propose a polynomial heuristic that yields a large, but not necessarily the maximal, inner box.
Next, we discuss how to apply the presented linear programming methods for finding large inner estimations of general parametric AE-solution sets with linear shape. Numerical examples illustrate the properties of the methods and their application.