15
$\begingroup$

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 ?

Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ actually no. It is as you say. I realize that LP optimization solves LP feasibility. I'm asking for the opposite reduction. $\endgroup$
    – Suresh Venkat
    Jan 24, 2014 at 23:44
  • 3
    $\begingroup$ 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. $\endgroup$
    – Noam
    Jan 25, 2014 at 6:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 25, 2014 at 8:22
  • 2
    $\begingroup$ @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. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Jan 25, 2014 at 18:17
  • 1
    $\begingroup$ What about polytopes/polyhedra defined by implicit constraints? $\endgroup$
    – Chandra Chekuri
    Jan 26, 2014 at 2:23

1 Answer 1

Reset to default
8
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.