# 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}} & \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}$ ?

• Clearly, c is not unique in general. Do you want single c or do you want the complete description of all c? Aug 31 '11 at 22:38
• Thanks @Tsuyoshi Ito, I'm interested in either a complete description of c or a method that outputs a satisfying c. Aug 31 '11 at 22:40
• I guess you don't have access to the dual ? that would give you a basis of constraints that you could use to generate candidate $c$'s Aug 31 '11 at 22:46
• Thanks @Suresh. Do you mean if I know the solution to the dual? or the cost vector of the dual? I would just say that all I know is $\mathbf{x}^*$, $\mathbf{A}$ and $\mathbf{b}$ Aug 31 '11 at 22:58
• Are you looking for something simpler than just running an LP-solver again? Because if you are fine with using LP again, then you can just solve the following two LPs: $\arg \max_c 1^{T}c \;\text{s.t.}\; x^{*T}c = 1$ and $\arg \max_c 1^{T}c \;\text{s.t.}\; x^{*T}c = 0$ Sep 1 '11 at 0:27

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>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.

• @Mike: Thank you for the comment, but I think that the current answer is correct as it is. Note that in the question, the constraints are given in the standard form (Ax=b, x≥0). Maybe the first revision of my answer had misled you; sorry if that is the case. Sep 14 '11 at 19:13
• My apologies. I will delete my previous comment. Sep 14 '11 at 20:22

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$).