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


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.

  • 2
    $\begingroup$ This is something like zero-one linear programming which in general is NP-complete. $\endgroup$ – Qiaochu Yuan Dec 9 '13 at 20:43
  • 2
    $\begingroup$ In particular, this is the partition problem: en.wikipedia.org/wiki/Partition_problem $\endgroup$ – Yoav Kallus Dec 9 '13 at 21:22
  • $\begingroup$ You probably want to read the answers to this closely related question: mathoverflow.net/questions/123670/… $\endgroup$ – Yoav Kallus Dec 9 '13 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 Dec 9 '13 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 Dec 10 '13 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.