Consider the following original LP: $\mathit{min}$ c'$x$ s.t: $Ax=0 \wedge 0\le x\le 1$ . This is my original LP which has to be solved.

Now, using some reductions, I reduced the original LP to the following converted LP: $\mathit{min}$ d'$y$ s.t: $By=0 \wedge 0\le y\le 1$. Using some relations between $x$ and $y$, I proved that these two LP are equivalent. This means the optimal solution for one of them gives the optimal solution for the other and visa verse. For optimal solutions the objective values are the same as well.

Now, the converted LP cannot be solved exactly. Now, I have got an approximate optimal solution vector for the converted LP, in which values for each pairs of variables are within some $\epsilon$ of each other. This solution is not feasible for the original LP but still is optimal based on the variable transformation rules that I have used to show the equivalence of these two LP's.

My problem is how to push this solution to be feasible by not ruining the objective value too much. How can I find the best lower bound?

  • $\begingroup$ What do you exactly mean by "each pair of variables"? Each value of a original and a corresponding variable is close to each other? And what do you mean by "still optimal ... based on transformation rules? I thought the converted lp could not be solved explicitely? $\endgroup$ – Martin Feb 7 '12 at 16:11
  • $\begingroup$ My converted LP has some classes of variables and the optimal amount of variables in each class should be equal. Now, Because of some barriers, I could not solve the converted LP exactly. However, using an approximation algorithm, I got a solution which values of the variables in each class are within a factor of $\epsilon$ of each other. Based on the conversion rule, the amount of the original LP is equal to the amount of the converted LP for given approximate solutions. Therefore, it is optimal (maybe more precisely, it is the best lower bound for the original LP). $\endgroup$ – Star Feb 7 '12 at 16:48
  • $\begingroup$ I am trying to solve the problem using more efficient algorithms, i.e., faster than well-known simplex or interior point methods. $\endgroup$ – Star Feb 7 '12 at 16:50
  • $\begingroup$ What do you mean by "not running the objective value too much"? Also, how can an infeasible solution be optimal? $\endgroup$ – Geoff Oxberry Feb 7 '12 at 17:34
  • $\begingroup$ It was a typo. I meant ruining the objective value. I think I put it in a bit wrong way. Consider instead of optimal, the best lower bound. $\endgroup$ – Star Feb 7 '12 at 18:24

(i) Just look at the activities of your approximate transformedsolution, and solve the associated linear system. if the approximation was reasonable, you should get the optimal solution of the original system in thisway.

(ii) Why don't you solve directly the original problem?


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.