6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Clearly, c is not unique in general. Do you want single c or do you want the complete description of all c? $\endgroup$ – Tsuyoshi Ito Aug 31 '11 at 22:38
  • $\begingroup$ Thanks @Tsuyoshi Ito, I'm interested in either a complete description of c or a method that outputs a satisfying c. $\endgroup$ – Amelio Vazquez-Reina Aug 31 '11 at 22:40
  • $\begingroup$ 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 $\endgroup$ – Suresh Venkat Aug 31 '11 at 22:46
  • $\begingroup$ 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}$ $\endgroup$ – Amelio Vazquez-Reina Aug 31 '11 at 22:58
  • $\begingroup$ 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$ $\endgroup$ – Artem Kaznatcheev Sep 1 '11 at 0:27
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Sep 14 '11 at 19:13
  • $\begingroup$ My apologies. I will delete my previous comment. $\endgroup$ – Mike Spivey Sep 14 '11 at 20:22
5
$\begingroup$

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

$\endgroup$

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.