0
$\begingroup$

I need to find a solution to the following system of linear inequalities:

\begin{align} x_1-x_2 &\le 1\\ x_1-x_4 &\le -4 \\ x_2-x_3 &\le 2 \\ x_2-x_5 &\le 7 \\ x_2-x_6 &\le 5 \\ x_3-x_6 &\le 10 \\ x_4-x_2 &\le 2 \\ x_5-x_1 &\le -1 \\ x_5-x_4 &\le 3 \\ x_6-x_3 &\le -8 \end{align}

In contrast to my previous question there should be a solution for this system. Is there any systematic way to find a solution?

$\endgroup$
  • 3
    $\begingroup$ Linear programming is designed for this. $\endgroup$ – Don Thousand Nov 26 at 22:49
  • 1
    $\begingroup$ @DonThousand On the contrary, linear programming doesn't find the solution to the inequalities, This would require finding all the vertices of the simplex, rather than just one at which the optimum of the objective function (lacking here) is attained. $\endgroup$ – saulspatz Nov 26 at 22:54
  • 1
    $\begingroup$ @saulspatz True, I just meant the general style of problem. $\endgroup$ – Don Thousand Nov 26 at 22:56
  • 1
    $\begingroup$ What do you mean by a solution? The solution set is a region in $6$-dimensional space, formed by the intersection of $10$ closed half-spaces. What form do you expect a solution to take that is simpler than what is given? If the solution set turns out to be bounded, it's the convex hull of a finite number of points. Is that what you want? What if the solution set isn't bounded? $\endgroup$ – saulspatz Nov 26 at 23:03
  • 1
    $\begingroup$ Any one of the infinitely many solutions will do? $\endgroup$ – saulspatz Nov 26 at 23:11
1
$\begingroup$

Using linear programming (LP) with a constant zero objective, I found the following feasible solution: $$x=(-6, 0, 2, 8, -7, 0).$$

By the way, this LP is the dual of a network LP, hence the constraint matrix is totally unimodular.

$\endgroup$
1
$\begingroup$

This is a linear program without an objective. Algorithms for solving linear programs include the simplex algorithm (Phase I is enough when there is no objective), the ellipsoid algorithm, and many others. https://en.wikipedia.org/wiki/Simplex_algorithm

$\endgroup$

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.