0
$\begingroup$

I recently discovered linear programming and it seemed perfect for a CS problem I wanted to solve a few months ago. This task involved solving a large quantity of inequalities at once.

For example, one such system could be

X1,X2,X3,X4 >= 0
X1 >= X3 + 3.0 or X1 < X3 - 7.2
X2 >= X4 + 5
X2 >= X3 + 3.0 or X2 < X3 - 5.3
X2 >= X1 + 7.2 or X2 < X1 - 5.3

And then some reasonably complex objective function in terms of X1, X2, X3, X4. In fact, the function mostly just needs to aim to reduce the spread of the variables, whilst finding a solution.

(Optimally, the program would aim to find a solution that meets as many inequalities as possible, to allow it to find a "close enough" solution when there is no actual solution)

I can't find anyone else talking about the limitations of linear programming, but I understand these inequalities are only "kinda" linear. If anyone out there, perhaps with a formal higher CS education, I'd much appreciate it.

If this is not possible with normal linear programming algorithms, any leads into possible solutions would be much appreciated.

Thanks all in advance!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

First off, a couple of observations.

If you allow three inequalities in each "compound inequality", then the problem of finding a feasible solution is NP-complete, since any 3-SAT problem can be recast as this problem.

The problem in parentheses, where you try to fit the maximum number of constraints, is NP-hard, for essentially the same reason: MAX-2-SAT is NP-hard.

OK, with that out of the way, this is called disjunctive programming, and the usual way to solve problems of this form is to introduce boolean variables to handle the disjunction, which turns it into a mixed-integer linear programming problem which is, again, NP-complete in general.

The feasibility problem (as opposed to the optimisation problem) can be directly implemented as a SMT problem and also has a natural expression in CLP(R).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much Pseudonym, you've given me lots to research. First of all is to learn what NP-hard actually means! In reality I am not nearly educated enough in CS to write an algorithm to solve this problem myself, so hopefully I can learn what pre-existing algorithm suits this problem! $\endgroup$
    – Ed_Silver
    Aug 3 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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