1
$\begingroup$

For a program I am writing, I would find it useful to find the least possible positive solution to a linear equation, using only -1 and 1 for roots.

For example...

0.25a + 0.5b + 0.75c + 1d + 2e = 0

When

a = -1, b = 1, c = 1, d = 1, e = -1

However, if we take the example

3a + 1b + 5c

It is still beneficial to know that

a = -1, b = -1, c = 1

Provides the least possible positive solution (1)

How can I algorithmically find these solutions? I would rather not use a brute force technique, my goal is to optimize the program by finding the solutions.

Forgive me for the lack of tags, I have no idea what kind of math this relates to, if any at all.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ This is something like zero-one linear programming which in general is NP-complete. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 9, 2013 at 20:43
  • 2
    $\begingroup$ In particular, this is the partition problem: en.wikipedia.org/wiki/Partition_problem $\endgroup$
    – Yoav Kallus
    Commented Dec 9, 2013 at 21:22
  • $\begingroup$ You probably want to read the answers to this closely related question: mathoverflow.net/questions/123670/… $\endgroup$
    – Yoav Kallus
    Commented Dec 9, 2013 at 21:33
  • 1
    $\begingroup$ What do you mean by "positive" solution, when you allow the variables to take on the value $-1$? $\endgroup$
    – Gerry Myerson
    Commented Dec 9, 2013 at 23:01
  • 1
    $\begingroup$ @GerryMyerson: judging by OP's example, they mean the least positive value that the left-hand side can take. $\endgroup$
    – Yoav Kallus
    Commented Dec 10, 2013 at 0:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .