0
$\begingroup$

I have a linear programming problem, with $n$ variables and $a\leq x_{i} \leq b$ for each variable $x_{i}$, where the objective function is $\min \sum\limits_{i=1}^{n}{2^{i} x_{i}}$

Is it true that, given the problem is feasible, there is only one optimal solution of the problem?

EDIT: all the variables have coefficient $1$ or $-1$ in the constraints.

$\endgroup$
6
  • 1
    $\begingroup$ If $a\le x_i\le b$ is the only constraint then the minimum is achieved at $x_i=a\forall i$? $\endgroup$ – TheSimpliFire May 24 at 10:14
  • $\begingroup$ $a\leq x_{i} \leq b$ are not the only constraints, there are other linear constraints. $\endgroup$ – Mario Giambarioli May 24 at 10:51
  • 2
    $\begingroup$ No it depends on the other constraints (trivial example if you minimize $c^Tx$ and have a constraint $c^T\geq d$ which becomes active at optimality, then any $x$ satisfying $c^Tx=d$ is optimal. $\endgroup$ – Johan Löfberg May 24 at 12:06
  • $\begingroup$ @JohanLöfberg Do you mean $c^{T}x \geq d$? $\endgroup$ – Mario Giambarioli May 24 at 12:39
  • 2
    $\begingroup$ If each $x_i\in\{0,1\}$, it is true by uniqueness of binary expansion. $\endgroup$ – RobPratt May 24 at 13:48
2
$\begingroup$

The value of the global solution is unique, but depending on what your feasible region looks like you can have degeneracy, i.e., multiple solutions giving the same globally optimal value, so the answer is that it depends.

$\endgroup$
1
  • $\begingroup$ For a limited linear programming problem the optimal value is always unique. I asked if, in the case I described, the solution is unique too (i.e. there is only one value of each problem variable the gives the optimal value of the objective function). $\endgroup$ – Mario Giambarioli May 26 at 15:17

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.