18

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 ?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 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. – Yoshio Okamoto Jan 24 '14 at 23:43
  • 1
    actually no. It is as you say. I realize that LP optimization solves LP feasibility. I'm asking for the opposite reduction. – Suresh Venkat Jan 24 '14 at 23:44
  • 1
    Excuse me, I was confused by myself. Thank you very much. – Yoshio Okamoto Jan 24 '14 at 23:51
  • 3
    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 Jan 25 '14 at 06:53
  • 1
    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 Jan 25 '14 at 08:22
  • 1
    @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 Jan 25 '14 at 17:40
  • 2
    @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 Jan 25 '14 at 18:17
  • @KristofferArnsfeltHansen ah maybe this needs to be an answer ? – Suresh Venkat Jan 25 '14 at 18:25
  • 1
    What about polytopes/polyhedra defined by implicit constraints? – Chandra Chekuri Jan 26 '14 at 02:23
  • @ChandraChekuri what do you mean by that ? – Suresh Venkat Jan 26 '14 at 08:27
  • 1
    @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 Jan 26 '14 at 18:54
  • 1
    @SureshVenkat In that case, Hansen's approach is not polynomial – Austin Buchanan Jan 26 '14 at 19:01
  • 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 Jan 28 '14 at 05:36
  • 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 Jan 28 '14 at 06:26

1 Answers1

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.
Kristoffer Arnsfelt Hansen
  • 4,159
  • 2
  • 26
  • 36
  • The steps 4 and 5 are not needed. If $S_2$ is feasible, then we have obtained the optimal solution to $P$. – hengxin Feb 19 '17 at 07:39
  • @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 Feb 20 '17 at 08:36
  • Might you be willing to elaborate on why $S_3$ will necessarily fully determine an optimal basic solution to P? – D.W. Mar 07 '21 at 20:12
  • 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 Mar 07 '21 at 21:15