Inferring an LP cost vector from its solution

Question

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}} & \mathbf{c}^T\mathbf{x} \\ \mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \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}$ ?

Answer 1

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 c_i be any strictly negative number. If x^*_i>0, then let c_i=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 c^T. It is not hard to prove that no other vectors c satisfy the condition.

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

Answer 2

Here's another perspective that might be helpful. Suppose there are $n$ variables and $m$ constraints. If you write the simplex method in matrix form, the optimality condition for a minimization problem is $${\bf c}^T_N - {\bf c}^T_B B^{-1} N \geq {\bf 0},$$ where ${\bf c}_B$ and ${\bf c}_N$ are the cost vectors for the basic and nonbasic variables, and $B$ and $N$ are matrices consisting of the entries in $A$ that correspond to the basic and nonbasic variables.

Since you know ${\bf x}^*$, you can construct a basis for the optimal solution. You need $m$ variables to be in the basis. First, every nonzero $x_i$ goes in the basis. If there aren't $m$ nonzero $x_i$'s (there can't be more than $m$), then you will need to choose enough of the zero-valued $x_i$'s to be basic so that you have $m$ basic variables; it doesn't matter which ones. (If this happens it means the optimal solution is degenerate.) Once you have a basis you can determine $B$ and $N$.

Then the set of cost vectors ${\bf c}$ for which ${\bf x}^*$ is optimal is the solution set to the above vector inequality, which is just a set of $n-m$ linear inequalities in which you have $m$ free variables (the values for ${\bf c}_B$).