Consider the following linear programming problem:

LinearProgramming[-{10, -57, -9, -24}, -( {
     {0.5, -5.5, 2.5, 9},
     {0.5, -1.5, -.5, 1},
     {1, 0, 0, 0}
    } ), -{0, 0, 1}]
 (* {0., 0., 0., 0.} *)

Why is this answer being returned? Taking $\textbf{x}=\begin{pmatrix}1&0&1&0\end{pmatrix}^T$ satisfies $\textbf{x}\ge 0\land A\textbf{x}\ge \textbf{b}$, but the value of the objective function for this solution is $-1$, which is clearly smaller than $0$, the suggested "optimal" solution by Mathematica.

I would expect Mathematica to be able to solve such a small LP problem, even if it is degenerate. Am I doing something wrong here?


You need to look at what LinearProgramming does: it finds a vector x that minimizes the quantity c.x subject to the constraints m.x>=b and x>=0. For your candidate answer x={1,0,1,0}, the product m.x is equal to {-3., 0., -1.}, which is not greater than your b={0, 0, -1}. Hence this is not a valid solution. Indeed, x={0,0,0,0} is the best you can get given the constraints.

  • $\begingroup$ The issue was that I missed a sign when inputting the values $\endgroup$ – VF1 Feb 16 '14 at 4:25

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.