Determining range of extreme points with linear constraints

Question

I have a set defined by a lot of linear constraints. Namely, $\mathcal{X}=\{x:Ax\leq b\}$, where $x$ is a $j$- dimensional vector (each component can be either positive or negative). I want to know for each component $j$, $\bar x_j=\max_{x\in \mathcal{X}} x_j$ and $\underline x_j=\min_{x\in \mathcal{X}} x_j$. I know that if I can enumerate all vertices, then I can simply take the minimum and maximum. But I wonder if there are better ways. Any hint is appreciated! Thank you.

Answer 1

Enumeration can be extremely expensive, so unless there is some particular structure in your case, the most efficient way is in general to solve $2j$ linear programs where you maximize and minimize along all directions.

Answer 2

By Solving Just one LP you can find those lower and upper bounds

$$ \begin{align} \max & \sum_{j} (\bar{y}^j _{j} - \underline y_{j} ^j)\\ &\text{subject to} \\ & \bar{y}^j \in \mathcal{X} &j=1,2...,n \\ & \underline y_{} ^j \in \mathcal{X} &j=1,2...,n \end{align} $$

DONE.

PS. The optimal solution of this problem is

$$ (\bar x_1, \bar x_2,...\bar x_n, \underline x_1, \underline x_2,...,\underline x_n ) \in \mathcal{X} ^2 $$