Suppose we have some procedure $F$ which takes any set of linear constraints and either returns either infeasible or returns a vector satisfying these constraints.
If we now take a linear program $L$, how can we solve it with only one call to $F$ (where the number of variables and constraints input to $F$ is polynomial in the number of variables and constraints in $L$)?
I was thinking there might be a way of using the dual of $L$ in combination with $L$ to form a new linear program which has a convex hull with essentially $0$ volume so that any call to $F$ will return the same feasible solution which by strong duality theorem must be the optimal one too.
Assume you have a linear program of the form
$\quad$ maximize $\mathbf{n}^T\mathbf{x}$ subject to $A\mathbf{x}\leq\mathbf{a}$.
The dual lp is
$\quad$ minimize $\mathbf{a}^T\mathbf{u}$ subject to $A^T\mathbf{u}=\mathbf{n}, \mathbf{u}\geq \mathbf{0}$.
By weak duality for any solution $\mathbf{x}_0$ of the primal lp and $\mathbf{u}_0$ of the dual lp it holds:
$\quad$ $\mathbf{n}^T\mathbf{x}_0 \leq \mathbf{a}^T\mathbf{u}_0$,
and by strong duality it holds
$\quad$ $\mathbf{n}^T\mathbf{x}_0 = \mathbf{a}^T\mathbf{u}_0$ if and only if $\mathbf{x}_0$ and $\mathbf{u}_0$ are optimal solutions.
Hence, any feasible solution $(\mathbf{x}_0,\mathbf{u}_0)$ of the system
$\quad$ $A\mathbf{x} \leq \mathbf{a}$, $A^T\mathbf{u} = \mathbf{n}$, $\mathbf{u}\geq\mathbf{0}$, $\mathbf{n}^T\mathbf{x} \geq \mathbf{a}^T\mathbf{u}$ $\quad$(*)
is an optimal solution of the primal (and also of the dual) lp.
Now, let (*) be the input of your procedure $F$, then any solution is an optimal solution of the primal (and also the dual) lp.