1
$\begingroup$

AFAIK, Interior Point method for solving a system of linear inequations is polynomial in the number of variables and constraints. Probably there are others. I don't need to optimize any function (neither maximize, not even minimize), but I need a solution to the system of inequalities from the Linear Programming method that is polynomial in the number of variables, constraints and the bitlength of the real numbers that it operates on. Here's why it's needed: https://algoextreme.com/2024/04/27/pnp-a-reduction-of-bsat-problem-to-linear-programming-and-long-arithmetic/

Can you suggest any such algorithm, or if it's the Interior Point method, confirm it's not exponential in the bitlength of the real numbers it operates?

Improve this question
$\endgroup$
5
  • $\begingroup$ There is no such thing as “bitlength of real numbers”. Real numbers cannot be represented by finite bitstrings. Bitlength makes only sense for integers or rationals. $\endgroup$ Commented Apr 29, 2024 at 8:42
  • $\begingroup$ @EmilJeřábek every programmer knows that everything in a computer has bitlength. Real numbers are currently approximated with fixed-point or floating-point data types of L bits, every programmer knows most often L=32 (single precision) or 64 (double precision). And when you aim to understand rather than criticize, it's easy to realize what I meant by bitlength of real numbers. Otherwise, if you are more mathematician than programmer, I have to disappoint you that there is no infinity - you just imagine it the way you imagine complex numbers. No offense, find me in messengers and we can talk. $\endgroup$ Commented Apr 29, 2024 at 9:48
  • 1
    $\begingroup$ Floating point numbers are a particular set of rational numbers. My intention is not to criticize, but to help you use standard terminology in the question. $\endgroup$ Commented Apr 29, 2024 at 10:20
  • $\begingroup$ @EmilJeřábek, thanks, you are right that to speak exactly mathematically we need to call them so, but then programmers won't understand the article, unfortunately, because many programming languages even have "REAL" data type, while what's meant indeed is what you said - a set of rational numbers. $\endgroup$ Commented Apr 29, 2024 at 14:04
  • $\begingroup$ You can call them floating point numbers. This is both mathematically accurate and understandable by programmers. $\endgroup$ Commented Apr 29, 2024 at 14:24

2 Answers 2

Reset to default
2
$\begingroup$

Interior-point methods such as Khachiyan’s and Karmarkar’s are, indeed, polynomial in the size of the input, i.e., in the number of variables, constraints, and the bitlength of the coeficients. This is why they were such a breakthrough when they were discovered. E.g., as noted in the linked article, if there are $n$ variables, $m$ constraints, and the total bitlength of the coefficients (say, integer or rational) is $l$, then Karmarkar’s algorithm takes $O(n^2m^{1.5}l)$ operations on $O(l)$-bit numbers, thus with total running time $O(n^2m^{1.5}l^2(\log l)^{O(1)})$.

Improve this answer
$\endgroup$
1
0
$\begingroup$

One possible way is to write a dummy objective function, such as $$maximize: \sum x_i$$ and let any good LP solver take care of the rest. The same is also suggested here.

Improve this answer
$\endgroup$
1
  • $\begingroup$ But is this polynomial in the number of variables, constraints and the bitlength of the real numbers that it operates on? I don't see any reason to believe it would be, for the solvers I am aware of. This answer seems to miss the point of the question. $\endgroup$ Commented Apr 28, 2024 at 4:15

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.