Inferring an LP cost vector from its solution Say I have the following linear programming formulation in standard form:

\begin{equation*}
\begin{array}{rl}
    \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}}        &amp; \mathbf{c}^T\mathbf{x} \\
    \mbox{s.t.} &amp; \mathbf{A}\mathbf{x} = \mathbf{b} \\
                &amp; \mathbf{x} \ge 0,
    \end{array}
\end{equation*}

with $\mathbf{x}^*$, $\mathbf{A}$ and $\mathbf{b}$ known, but $\mathbf{c}$ unknown.

Are there any known methods for computing $\mathbf{c}$ ?
I guess that you want the set of optimal solutions of the LP as small as possible.  (Otherwise, c=0 certainly makes x* one of the optimal solutions but probably that is not what you want.)

One way to obtain such c is as follows.  If x*i=0, then let ci be any strictly negative number.  If x*i&gt;0, then let ci=0.

If you want to know all the vectors c with the required property, you can add any linear combination of rows of matrix A to cT.  It is not hard to prove that no other vectors c satisfy the condition.

Edit: Entirely rewritten in revision 2 to make it simpler.