Linear Programming with UPPER AND LOWER bounds

I have a problem very similar to regular linear programming problems.

Given a known integer coefficient matrix $A$, vectors $\mathbf{a}$, $\mathbf{b}$ and vector of variables $\mathbf{x}$, I want to find possible solutions to the inequalities:

(1) $\mathbf{a} \leq A\mathbf{x} \leq \mathbf{b}$ and all elements of $\mathbf{a},\mathbf{b}$ and $\mathbf{x} \geq 0$

I don't really care about optimising a solution. All solutions to the inequality are equally good. As I understand it, linear programming finds optimised solutions to a given equation, using known coefficients $\mathbf{c}$, within the feasible region defined by:

(2) Maximise $\mathbf{c}^T \mathbf{x}$ where $A \mathbf{x} \leq \mathbf{b}$ and all elements of $\mathbf{a},\mathbf{b},\mathbf{c}$ and $\mathbf{x} \geq 0$

Can linear programming be applied to find $\mathbf{x}$ satisfying (1)?

If not, do I need to reformulate (1) to fit with the second form? I know that constraints in (2) definitely form a convex n-polytope and think that the same holds true for (1), in which case could I just pick an arbitrary point inside the polytope to optimise towards?

Note: This has been heavily edited to make the question clearer

• What does $(a,b,x) \geq 0$ mean? – Paul Jun 14 '17 at 9:05
• Sorry, that's supposed to mean that all elements of a, b and x are greater than or equal to 0. – Flash_Steel Jun 14 '17 at 9:11
• I hope the edit is clearer. – Flash_Steel Jun 14 '17 at 9:14

You want to formulate (1) in terms of (2). I assume that the formulation (2) is of the form

For $\mathbf{b}, \mathbf{c} \geq 0$, maximize $\mathbf{c}^T\mathbf{x}$, such that $A\mathbf{x} \leq \mathbf{b}$ and $\mathbf{x} \geq 0$. In particular, $A$ can contain negative entries.

First select $e := \max(\mathbf{a})$, the largest elements of all $\mathbf{a}$s. Then, solve the following linear program

Maximise $\begin{bmatrix}\mathbf{0} & 1\end{bmatrix}\begin{bmatrix}\mathbf{x} \\ y\end{bmatrix}$ where $\begin{bmatrix}-A & 1\\ A & 1\end{bmatrix}\begin{bmatrix}\mathbf{x} \\ y \end{bmatrix} \leq \begin{bmatrix}-\mathbf{a}+e \\ \mathbf{b}+e \end{bmatrix}$ and $\mathbf{x},y \geq 0$.

Here, $\mathbf{0}$ is a row vector of appropriate length, and $-\mathbf{a}+e$ adds $e$ to each component of $-\mathbf{a}$. Note that $-\mathbf{a}+e \geq 0$, so the linear program is in the right form.

How does that help?

This linear program is equivalent to

Maximize $y$ where $\mathbf{a} + y \leq A \mathbf{x}+e$ and $A\mathbf{x}+y \leq \mathbf{b}+e$ and $\mathbf{x},y \geq 0$

Consider a solution $(\mathbf{x},y)$ to this linear program. If $y \geq e$, then $\mathbf{x}$ is a solution to the original problem (easy to check). If $y < e$, there is no solution to the original problem. To prove this, assume there is a solution $\mathbf{x}$ to the original problem. Then, select $y=e$ and you get a better solution to the linear program.

• Thanks. Sorry, I may be a little slow here. Is $\mathbf{0}$ a row vector of all 0's? If so why is it written "Maximise $\begin{bmatrix}\mathbf{0} & 1\end{bmatrix}\begin{bmatrix}\mathbf{x} \\ y\end{bmatrix}$" and not just "Maximise y"? – Flash_Steel Jun 14 '17 at 12:59
• Yes, precisely. I wrote $\begin{bmatrix} \mathbf{0} & 1 \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ y \end{bmatrix}$ to show how to involve all variables (your format for linear programs seemed to require this). Maximizing $y$ would be equivalent. – Peter Jun 14 '17 at 13:05
• Great. That looks like it gives me a solid start as to solve it using linear programming now. – Flash_Steel Jun 14 '17 at 13:08