0

Let $w$ be a given feasible solution to the standard LP:
$\min\{c^T x:Ax=b,x\geq 0\}$;
Then how can I verify whether $w$ is an optimal solution without solving the LP at all?
I know $w$ is optimal if and only if there exists a multiplier $\lambda$ such that the KKT conditions are satisfied. But the problem is that when I don't know the value of $\lambda$, can I quickly verify the optimality of $w$ without solving the LP at all?

RobPratt
  • 45,619
Yunfei
  • 135
  • 1
    Find a dual feasible point that has equal cost. – copper.hat Aug 30 '23 at 02:24
  • 2
    Look up: complementary slackness. – Robert Israel Aug 30 '23 at 02:42
  • I know all these. But finding a corresponding dual point is as difficult as solving the LP. What i am looking for is a quick and simple way to verify the optimality. As simple as verifying an equality without unknown varibles. I wonder whether there is a such method. – Yunfei Aug 30 '23 at 04:00
  • 1
    With complementary slackness, you typically just have a set of linear equations to solve. It should be easier than linear programming. – Robert Israel Aug 30 '23 at 04:37

0 Answers0