0
$\begingroup$

Most normal linear programming problems look like this: normal linear programming We choose some point in the double shaded area that solves our optimizer and we're good to go.

However, I've come across a problem where it's fairly common to get a lp problem like this (infeasible): weird linear programming

I'd like to employ some metric such that the solution given reduces the errors between the closest possible solutions in any equation it does not fulfill such that it would be on the line right between the 2 solutions (something like reduce OLS or LAD).

Is there any formal algorithm for this or common way this is done?

$\endgroup$
1
$\begingroup$

One approach: replace each inequality $a_1 x_1 + \dots + a_n x_n \le b$ by $a_1 x_1 + \dots + a_n x_n \le b + t$, replace each inequality $a_1 x_1 + \dots + a_n x_n \ge b$ by $a_1 x_1 + \dots + a_n x_n \ge b - t$ (using the same $t$ for all of them), and then minimize $t$.

$\endgroup$
4
  • $\begingroup$ If using the same $y$ for each, wouldn't it result in the same "open space" for each? For example, the equations in graph 2 were $y=x$ and $y=x-1$. If I were to use another "shift variable" it would result in $y=x-s$ and $y=x-s-1$ which would leave the same amount of open space between the 2 lines. Perhaps you mean give an $s_i$ to every equation and minimize $\sum s_i^2$? $\endgroup$
    – user760900
    Nov 28 '20 at 21:12
  • $\begingroup$ @user760900, no, your inequalities were $y \ge x$ (blue region) and $y \le x-1$ (red region). After my transformation, they become $y \ge x-t$ and $y \le x-1+t$, and when we minimize $t$, the smallest $t$ where both can hold is $t=1/2$ along with any $x,y$ where $y = x-1/2$. (I edited my answer to change the variable I add, to avoid confusion with the $y$ on the $y$-axis.) $\endgroup$
    – D.W.
    Nov 28 '20 at 21:34
  • $\begingroup$ Ah yes, you're right about the inequalities. How would I scale this up to many variables? Would it be $-t$ for all inequalities of the form $y \le \dots -t$ and $+t$ where the inequality is of the form $y \ge \dots +t$? $\endgroup$
    – user760900
    Nov 29 '20 at 21:32
  • 1
    $\begingroup$ @user760900, see edited answer, which specifies how to do it for both $\le$ and $\ge$. $\endgroup$
    – D.W.
    Nov 29 '20 at 23:48
1
$\begingroup$

Have a look at the Simplex algorithm. It works in two phases: In phase one, it tries to find an extreme point that is a feasible (but usually non-optimal) solution, and in phase two, starting with a feasible solution, it tries to find an optimal solution.

In phase 1, for every equation $\sum a_{ij}x_i = b_i$, we introduce another variable $y_i$ and change the equation to $\sum a_{ij}x_i +y_i= b_i$, with the obvious starting solution $x_i = 0$, $y_i = b_i$. Then we minimise $\sum y_i$. If we can achieve $\sum y_i = 0$ then we remove all variables $y_i$ and have a feasible solution for the original problem. If we can't reduce $\sum y_i$ to zero, then the original problem has no feasible solution. And that is exactly your situation.

So at this point your problem is solved, kind of. You found a point closest to a feasible solution in terms of the original equations. But different equations may have different scaling. If you multiply one of the equations by 1,000, it doesn't change anything when you find a feasible solution, but minimising $\sum y_i$ will try much harder to get the $y_i$ for that particular equation as small as possible. So you want to look at all your equations and make sure they are scaled in a similar way.

$\endgroup$
1
  • $\begingroup$ So essentially, if I put in an infeasible system into simplex, you're saying that it will already try to preform LAD and give me a solution as close as possible? I don't have to put in the $t$ values that D.W. suggested as simplex already does that? $\endgroup$
    – user760900
    Dec 4 '20 at 21:22

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.