1
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Flash_Steel Jun 14 '17 at 12:59
  • $\begingroup$ 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. $\endgroup$ – Peter Jun 14 '17 at 13:05
  • $\begingroup$ Great. That looks like it gives me a solid start as to solve it using linear programming now. $\endgroup$ – Flash_Steel Jun 14 '17 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.