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

<p>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$.  </p>

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

CC BY-SA 3.0
2011-09-14T19:43:54.547Z
2011-09-14T20:23:41.440Z
2011-09-14T20:23:41.440Z
Mike Spivey
<p>I guess that you want the set of optimal solutions of the LP as small as possible.  (Otherwise, <i>c</i>=0 certainly makes <i>x</i><sup>*</sup> one of the optimal solutions but probably that is not what you want.)</p>

<p>One way to obtain such <i>c</i> is as follows.  If <i>x</i><sup>*</sup><sub><i>i</i></sub>=0, then let <i>c</i><sub><i>i</i></sub> be any strictly negative number.  If <i>x</i><sup>*</sup><sub><i>i</i></sub>&gt;0, then let <i>c</i><sub><i>i</i></sub>=0.</p>

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

<p><em>Edit: Entirely rewritten in revision 2 to make it simpler.</em></p>

CC BY-SA 3.0
2011-09-14T19:13:23.473Z
@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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-14T20:22:58.413Z
My apologies.  I will delete my previous comment.
Mike Spivey
CC BY-SA 3.0
2011-09-01T01:16:20.687Z
2011-09-01T01:59:47.280Z
2011-09-01T01:59:47.280Z
Tsuyoshi Ito
<p>Say I have the following linear programming formulation in standard form:</p>

<p>\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*}</p>

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

<p>Are there any known methods for computing $\mathbf{c}$ ? </p>

CC BY-SA 3.0
2011-08-31T22:38:49.063Z
Clearly, c is not unique in general.  Do you want single c or do you want the complete description of all c?
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-31T22:40:34.293Z
Thanks @Tsuyoshi Ito, I'm interested in either a complete description of `c` or a method that outputs a satisfying `c`.
Amelio Vazquez-Reina
CC BY-SA 3.0
2011-08-31T22:46:08.060Z
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
Suresh Venkat
CC BY-SA 3.0
2011-08-31T22:58:12.953Z
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}$
Amelio Vazquez-Reina
CC BY-SA 3.0
2011-09-01T00:27:48.687Z
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$
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-01T00:33:47.667Z
@Artem: I fail to see how to use the solutions to those LPs to solve the current question.  But if I am not mistaken, we do not have to solve LP again for this problem.  (I tried to write it as an answer, but it turned out to be harder for me to explain it than I first thought, and I have not finished writing it as an answer.  I am happy if someone beats me.)
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-01T00:42:18.017Z
@Tsuyoshi: yeah, I think I might have made a mistake in my solution.
Artem Kaznatcheev
<ds.algorithms><optimization><linear-programming>
Inferring an LP cost vector from its solution
Amelio Vazquez-Reina
# Inferring an LP cost vector from its solution

(Asked by: username_0 on 2011-08-31)

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}$ ?

**Tags:** ds.algorithms, optimization, linear-programming

> **Comments:**
> **username_1**: Clearly, c is not unique in general.  Do you want single c or do you want the complete description of all c?  
> **username_0**: Thanks @username_1, I'm interested in either a complete description of `c` or a method that outputs a satisfying `c`.  
> **username_2**: 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  
> **username_0**: 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}$  
> **username_3**: 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$  
> **username_1**: @Artem: I fail to see how to use the solutions to those LPs to solve the current question.  But if I am not mistaken, we do not have to solve LP again for this problem.  (I tried to write it as an answer, but it turned out to be harder for me to explain it than I first thought, and I have not finished writing it as an answer.  I am happy if someone beats me.)  
> **username_3**: @Tsuyoshi: yeah, I think I might have made a mistake in my solution.  

---

## 2 answers

### Answer by username_1 on 2011-09-01. Score: 9 | Accepted answer

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

> **Comments:**
> **username_1**: @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.  
> **username_4**: My apologies.  I will delete my previous comment.  

---

### Answer by username_4 on 2011-09-14. Score: 5

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


---

