# Feasibility region of LP

Consider the problem $$\text{ Find } y \text{ s.t. } \\ \exists \text{ } x \text{ solving} \text{ }Ax\leq b, Dx=e, \text{ and } y=cx$$ where $$y$$ is a $$2\times 1$$ vector of unknowns, $$x$$ is a $$10\times 1$$ vector of unknowns, $$A,D,b,c,e$$ are matrices and vectors of known values with appropriate dimensions.

My objective is to find (plot) the region of values of $$y$$ such that $$\exists \text{ } x \text{ solving} \text{ }Ax\leq b, Dx=e, \text{ and } y=cx$$

Let us call this region $$\mathcal{R}$$. I would like your help to investigate whether there is a way (with relative algorithm in any language) to reach my objective.

Let me also add that the region $$\mathcal{P}\equiv \{x: Ax\leq b, Dx=e\}$$ is bounded.

A naive way to go is to:

(1) rewrite the problem as a unique linear programming problem $$Ax\leq b\\ Dx=e\\ y=cx,$$

(2) find the feasibility region, and

(3) report only the feasible values of $$y$$.

The problem is that there is no algorithm that allows me to find (plot) the feasibility region of a $$12$$-dimensional linear programming. The available algorithms (for example, in Matlab) allows me to plot feasibility regions of 3 dimensions at most.

Hence, the question is: is there a simpler way to rewrite my problem in order to reach my objective?

• Let $P = \left\lbrace x \: : \: Ax \leq b \right\rbrace$ denote the polyhedron in your setup. One option is to calculate the set of all extreme points and extreme rays of $P$ (you can maybe hope to do this since $P$ is only ten-dimensional in your case), and then transform them using the matrix $c$ to get a description of the extreme points and extreme rays of the polyhedral region that corresponds to the set of possible $y$ – madnessweasley Aug 13 '19 at 18:28
• Thanks. Regarding $P$, do you know any algorithm that calculates the set of all extreme points and extreme rays? I found this in Matlab uk.mathworks.com/matlabcentral/fileexchange/… but it gives me lots of errors and the explanations contained in the code do not help. – TEX Aug 13 '19 at 18:48
• I've heard some folks talk about PORTA, but I haven't used it myself. Another option appears to be cddlib – madnessweasley Aug 13 '19 at 18:50
• This does not seem to have anything to do with coding-theory. – Jyrki Lahtonen Aug 14 '19 at 17:11

As you have noted, this (implicit) feasibility region on $$y$$ can be formulated as the projection (via $$y=cx$$) of an explicit feasibility region in $$x$$. I had to deal with this problem myself recently. One method, as people have commented, is to obtain the vertices from your half-space representation and then project these down; the convex hull of these projected points is the desired feasibility region. For your problem’s size, that’s probably the best way. I suggest using either SageMath’s polyhedral commands or the program ’polymake’ (both accessible online via the CoCalc cloud computation site).