<p>The answer is yes, and in fact one can even reduce to the decision problem of linear inequalities feasibility!</p>

<p>We are as input given a LP instance P:
$\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$. </p>

<p>We furthermore have access to an oracle that given a system of inequalities $S=\{Bz \leq d\}$ returns yes/no, whether the system is feasible.</p>

<p>The reduction now proceeds as follows:</p>

<ol>
<li>Test if $S_1=\{Ax \leq b\ ;\ x \geq 0\}$ is feasible. If not, we can report that P is INFEASIBLE.</li>
<li>Form the dual program D: $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$.</li>
<li>Test if $S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$ is feasible. If not, we can report that P is UNBOUNDED.</li>
<li>Iterate over the inequalities of $S_1$ and try to add them one-by-one as <em>equalities</em> (i.e. add the reverse inequality) to the system $S_2$. If the system remains feasible we keep the constraint in $S_2$, and otherwise remove it again. Let $S_3$ be the system of constraints (linear equalities) that gets added in this way. The system $S_3$  will now completely determine an optimal basic solution to P.</li>
<li>Using Gaussian Elimination on the system $S_3$ compute an optimal solution $x$ to P.</li>
</ol>

CC BY-SA 3.0
2017-02-19T07:39:34.320Z
The steps 4 and 5 are not needed. If $S_2$ is feasible, then we have obtained the optimal solution to $P$.
hengxin
CC BY-SA 3.0
2017-02-20T08:36:24.090Z
@hengxin. It write in the first line of my answer that the answer is yes _even_ when considering reducing to the decision problem. Below I obviously make that assumption, and hence steps 4 and 5 are required.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-03-07T20:12:59.517Z
Might you be willing to elaborate on why $S_3$ will necessarily fully determine an optimal basic solution to P?
D.W.
CC BY-SA 4.0
2021-03-07T21:15:39.613Z
Sure. Suppose that P as above is a LP in standard form with n variables and m constraints. When we have a linear program in standard form P we know that one of the following holds: (a) P is infeasible (b) P is unbounded (c) P has an optimal bfs. In step (1) we take care of case (a) and in step (3) we take care of case (b). Then when we get to step (4) we know that P has an optimal bfs. Any basic solution of P is the unique solution of a linear system in the $n$ variables obtained by selecting $n$ of the $n+m$ inequalities of $S_1$ and turning them into equalities.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-01-29T12:41:00.270Z
2014-01-29T13:06:07.920Z
2014-01-29T13:06:07.920Z
Kristoffer Arnsfelt Hansen
<p>One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the optimal solution and introduce it as a constraint via binary search. </p>

<p>Both of these reductions are polynomial, but not strongly polynomial (i.e they depend on the number of bits in the coefficients of the inequalities). </p>

<blockquote>
  <p>Is there a strongly polynomial reduction from LP optimization to LP
  feasibility ?</p>
</blockquote>

CC BY-SA 3.0
2014-01-24T23:43:04.060Z
Please make it more precise what you mean by "linear programming" or "LP optimization". By LP optimization, you could mean that given a system of linear inequalities and a linear function, determine if the system is feasible, and if so, determine if the function is bounded, and if so, find an optimal solution. If this would be your intention, the first step of LP optimization already solves LP feasibility. So, I guess you meant something different.
Yoshio Okamoto
CC BY-SA 3.0
2014-01-24T23:44:57.537Z
actually no. It is as you say. I realize that LP optimization solves LP feasibility. I'm asking for the opposite reduction.
Suresh Venkat
CC BY-SA 3.0
2014-01-24T23:51:09.870Z
Excuse me, I was confused by myself. Thank you very much.
Yoshio Okamoto
CC BY-SA 3.0
2014-01-25T06:53:55.397Z
Well, the output for optimization can have as many bits as "the number of bits in the coefficients", while feasibility is yes/no.  Thus, if by reduction you mean something "black-box"-ey then the answer must be negative.
Noam
CC BY-SA 3.0
2014-01-25T08:22:45.587Z
But, if the feasibility check does not only give a yes/no answer as discussed by Noam above, but rather in the case of feasibility provides a feasible solution, then the answer is yes, by LP duality.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-01-25T17:40:59.513Z
@KristofferArnsfeltHansen why is that ? if I combine the primal and dual LPs I still need a complementary slackness condition which isn't linear.
Suresh Venkat
CC BY-SA 3.0
2014-01-25T18:17:48.313Z
@SureshVenkat: Suppose the primal is a maximization program in variables $x$, with the dual then being a minimization program in variables $y$. Then form the system of inequalities in variables $x,y$, taking the constraints from both the primal and the dual, together with an inequality stating that the value of the primal solution is at least the value of the dual solution. The cases of the LP being infeasible and unbounded can also be dealt with.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-01-25T18:25:13.590Z
@KristofferArnsfeltHansen ah maybe this needs to be an answer ?
Suresh Venkat
CC BY-SA 3.0
2014-01-26T02:23:53.830Z
What about polytopes/polyhedra defined by implicit constraints?
Chandra Chekuri
CC BY-SA 3.0
2014-01-26T08:27:27.220Z
@ChandraChekuri what do you mean by that ?
Suresh Venkat
CC BY-SA 3.0
2014-01-26T18:54:59.203Z
@SureshVenkat I think Chandra Chekuri is referring to situations like the Held-Karp relaxation for TSP, where the number of constraints is exponential in n, but you can still optimize over it in polytime using the ellipsoid method and a separation oracle.
Austin Buchanan
CC BY-SA 3.0
2014-01-26T19:01:16.043Z
@SureshVenkat In that case, Hansen's approach is not polynomial
Austin Buchanan
CC BY-SA 3.0
2014-01-28T05:36:15.027Z
Probably I'm just confused, but I don't see why Kristoffer's approach is strongly polynomial. If we construct the dual system explicitly, the encoding length is not strongly polynomial but depends on the bit length of the input (the primal system).
Yoshio Okamoto
CC BY-SA 3.0
2014-01-28T06:26:02.717Z
One has to be careful here. Reading the input is also not "strongly polynomial". A reasonable interpretation is that constructing the dual takes time O(size of input) and that can be absorbed into the "reading the input" time.
Suresh Venkat
<ds.algorithms><linear-programming>
Equivalence of feasibility checking and optimization for linear systems
Suresh Venkat
# Equivalence of feasibility checking and optimization for linear systems

(Asked by: username_0 on 2014-01-24)

One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the optimal solution and introduce it as a constraint via binary search.

Both of these reductions are polynomial, but not strongly polynomial (i.e they depend on the number of bits in the coefficients of the inequalities).

> Is there a strongly polynomial reduction from LP optimization to LP
> feasibility ?

**Tags:** ds.algorithms, linear-programming

> **Comments:**
> **username_1**: Please make it more precise what you mean by "linear programming" or "LP optimization". By LP optimization, you could mean that given a system of linear inequalities and a linear function, determine if the system is feasible, and if so, determine if the function is bounded, and if so, find an optimal solution. If this would be your intention, the first step of LP optimization already solves LP feasibility. So, I guess you meant something different.  
> **username_0**: actually no. It is as you say. I realize that LP optimization solves LP feasibility. I'm asking for the opposite reduction.  
> **username_1**: Excuse me, I was confused by myself. Thank you very much.  
> **username_2**: Well, the output for optimization can have as many bits as "the number of bits in the coefficients", while feasibility is yes/no.  Thus, if by reduction you mean something "black-box"-ey then the answer must be negative.  
> **username_3**: But, if the feasibility check does not only give a yes/no answer as discussed by username_2 above, but rather in the case of feasibility provides a feasible solution, then the answer is yes, by LP duality.  
> **username_0**: @KristofferArnsfeltHansen why is that ? if I combine the primal and dual LPs I still need a complementary slackness condition which isn't linear.  
> **username_3**: @SureshVenkat: Suppose the primal is a maximization program in variables $x$, with the dual then being a minimization program in variables $y$. Then form the system of inequalities in variables $x,y$, taking the constraints from both the primal and the dual, together with an inequality stating that the value of the primal solution is at least the value of the dual solution. The cases of the LP being infeasible and unbounded can also be dealt with.  
> **username_0**: @KristofferArnsfeltHansen ah maybe this needs to be an answer ?  
> **username_4**: What about polytopes/polyhedra defined by implicit constraints?  
> **username_0**: @ChandraChekuri what do you mean by that ?  
> **username_5**: @SureshVenkat I think username_4 is referring to situations like the Held-Karp relaxation for TSP, where the number of constraints is exponential in n, but you can still optimize over it in polytime using the ellipsoid method and a separation oracle.  
> **username_5**: @SureshVenkat In that case, Hansen's approach is not polynomial  
> **username_1**: Probably I'm just confused, but I don't see why Kristoffer's approach is strongly polynomial. If we construct the dual system explicitly, the encoding length is not strongly polynomial but depends on the bit length of the input (the primal system).  
> **username_0**: One has to be careful here. Reading the input is also not "strongly polynomial". A reasonable interpretation is that constructing the dual takes time O(size of input) and that can be absorbed into the "reading the input" time.  

---

## 1 answers

### Answer by username_3 on 2014-01-29. Score: 10

The answer is yes, and in fact one can even reduce to the decision problem of linear inequalities feasibility!

We are as input given a LP instance P:
$\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$.

We furthermore have access to an oracle that given a system of inequalities $S=\{Bz \leq d\}$ returns yes/no, whether the system is feasible.

The reduction now proceeds as follows:

1. Test if $S\_1=\{Ax \leq b\ ;\ x \geq 0\}$ is feasible. If not, we can report that P is INFEASIBLE.
2. Form the dual program D: $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$.
3. Test if $S\_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$ is feasible. If not, we can report that P is UNBOUNDED.
4. Iterate over the inequalities of $S\_1$ and try to add them one-by-one as *equalities* (i.e. add the reverse inequality) to the system $S\_2$. If the system remains feasible we keep the constraint in $S\_2$, and otherwise remove it again. Let $S\_3$ be the system of constraints (linear equalities) that gets added in this way. The system $S\_3$ will now completely determine an optimal basic solution to P.
5. Using Gaussian Elimination on the system $S\_3$ compute an optimal solution $x$ to P.

> **Comments:**
> **username_6**: The steps 4 and 5 are not needed. If $S_2$ is feasible, then we have obtained the optimal solution to $P$.  
> **username_3**: @username_6. It write in the first line of my answer that the answer is yes _even_ when considering reducing to the decision problem. Below I obviously make that assumption, and hence steps 4 and 5 are required.  
> **username_7**: Might you be willing to elaborate on why $S_3$ will necessarily fully determine an optimal basic solution to P?  
> **username_3**: Sure. Suppose that P as above is a LP in standard form with n variables and m constraints. When we have a linear program in standard form P we know that one of the following holds: (a) P is infeasible (b) P is unbounded (c) P has an optimal bfs. In step (1) we take care of case (a) and in step (3) we take care of case (b). Then when we get to step (4) we know that P has an optimal bfs. Any basic solution of P is the unique solution of a linear system in the $n$ variables obtained by selecting $n$ of the $n+m$ inequalities of $S_1$ and turning them into equalities.  

---

