8
$\begingroup$

I have a simple linear programming problem min $c^{T}x$ subject to $Ax\leq b$. That gives me the solution I am looking for when solving in maple. My only problem is that I do not know how to check, with maple, whether or not this solution is unique. I have read MANY threads about this topic and no one seems to be able to provide a simple way to check with a computational program such as maple whether or not the solution is unique.

Any sort of for all $q\in \mathbb{R}^{n}$ check that there exists an $\epsilon$ such that the solution maximizes the perturbed problem is useless for me as I need a definite answer and obviously can't check for all $q\in \mathbb{R}^{n}$.

I have read this paper www.jstor.org/stable/822972.

But, I cannot understand how to implement this algorithm based on the way it is presented, if anyone could simply phrase this algorithm I think it would be beneficial for future reference to others.

It is simple enough to provide my exact problem here:

$$ \min_{x\in \mathbb{R}^{8}} 36x_{1}+30x_{2}+50x_{3}+51x_{4}+36x_{5}+55x_{6}+33x_{7}+30x_{8} $$ s.t \begin{cases} x_{1}+x_{5}\leq 2x_{6}\\ 2x_{8}\leq x_{3}+x_{7}\\ 2x_{1}+x_{7}\leq3x_{5}\\ 3x_{6}+3x_{7}\leq 2x_{2}+4x_{8}\\ 2x_{2}\leq x_{1}+x_{3}\\ x_{5}+x_{7}\leq 2x_{6}\\ 40x_{1}+80x_{2}+60x_{5}+60x_{7}+80x_{8}\leq 40\\ \sum_{i=1}^{8}x_{i}=1,\;\;\;\; x_{i}\geq 0\;\; i=1,...,8\\ \end{cases}

The solution is $x^{*}=(0,\frac{1}{4},\frac{1}{2},0,0,0,0,\frac{1}{4})$ which is exactly what my counter example requires, but I need uniqueness.

$\endgroup$
1
  • 1
    $\begingroup$ The paper I reference in the question claims to provide a "simple" way to check for uniqueness or find another solution to the LP in question, I just cannot understand exactly what the algorithm requires and, given that it is constructed with out proof, whether or not I can trust it. $\endgroup$
    – h4nusGT
    Commented Jan 31, 2014 at 13:44

1 Answer 1

3
$\begingroup$

There is a very simple (while not that efficient) way to check this.

Note that your solution yields the function value $c^T x^*=\frac{30}{4}+\frac{50}{2}+\frac{30}{4}=40$.

Now consider the linear program

$$\max_{x\in \mathbb{R}^{8}} 1x_{1}$$

s.t.

$$\begin{cases} 36x_{1}+30x_{2}+50x_{3}+51x_{4}+36x_{5}+55x_{6}+33x_{7}+30x_{8}=40\\ x_{1}+x_{5}\leq 2x_{6}\\ 2x_{8}\leq x_{3}+x_{7}\\ 2x_{1}+x_{7}\leq3x_{5}\\ 3x_{6}+3x_{7}\leq 2x_{2}+4x_{8}\\ 2x_{2}\leq x_{1}+x_{3}\\ x_{5}+x_{7}\leq 2x_{6}\\ 40x_{1}+80x_{2}+60x_{5}+60x_{7}+80x_{8}\leq 40\\ \sum_{i=1}^{8}x_{i}=1,\;\;\;\; x_{i}\geq 0\;\; i=1,...,8\\ \end{cases}$$

The first constraint will say that you are searching a different optimal solution (same function value). But the new function you maximize, namely $x_1$ means that you are looking for an optimal solution with maximal $x_1$ value.

You can do that twice for each coordinate to see if your solution is unique. In your case your solution is not optimal, in fact there is a solution with $x_1\approx0.1363636 $.

$\endgroup$
6
  • 1
    $\begingroup$ Ok, that makes sense. But, still I am constructing a counter example so I can play with the numbers a bit. So suppose I find an example where for each $x_{i}$(i=1,4,5,6,7), I get the $max x_{i}$ solution to be my original solution $x^{*}$. Does this imply uniqueness and if so why? $\endgroup$
    – h4nusGT
    Commented Jan 31, 2014 at 14:10
  • $\begingroup$ When you say twice for each coordinate, do you mean once for $\min x_i$ and once for $\max x_i$? $\endgroup$ Commented Jan 31, 2014 at 14:56
  • $\begingroup$ @AnonSubmitter85 yes. $\endgroup$
    – Listing
    Commented Jan 31, 2014 at 15:06
  • $\begingroup$ @ThomasJRivera The solution is unique if and only if both $\min x_i$ and $\max x_i$ return the same solution for all $i$. $\endgroup$
    – Listing
    Commented Jan 31, 2014 at 15:06
  • 1
    $\begingroup$ @Listing Is there a more efficient test? $\endgroup$
    – a06e
    Commented May 14, 2016 at 19:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .