1

Suppose that we are given a subroutine which, given a system of linear inequalities $Ax \leq b$, $x \in \mathbb{R}^n$ , either produces a solution or decides that no solution exists.

I would like to construct an algorithm that uses a single call of this subroutine and which returns an optimal solution (if it exists) to the following linear programming problem:

$\begin{array}{ccc} \text{minimize } & c^Tx & &\\ \text{subject to: } & Ax & = & b \\ & x & \ge & 0 \end{array}$

Well, I think I should take a look at the dual problem.

The dual is:

$\begin{array}{ccc} \text{maximize } & p^Tb & &\\ \text{subject to: } & A^Tp & \leq \ & c \\ \end{array}$

Then I would call the subroutine for the matrix $A^T$ and to the vector $c$ to find a dual feasible point $y$.

I tried to use complementary slackness to construct a primal solution and to decide if $y$ is optimal but it didn't work . That is where I get stuck, can somebody help me out?

Santos
  • 1,577

1 Answers1

1

Simply combine all your primal and dual constraints and let dual objective value be less than or equal to that of primal (only holds if solution is optimal). Solve the resulting system of equality and inequalities using the subroutine.

Reza Soleymanifar
  • 11