3

I'm working on a programming problem which boils down to a set of an equation and inequality:

x[0]*a[0] + x[1]*a[1] + ... x[n]*a[n] >= D
x[0]*b[0] + x[1]*b[1] + ... x[n]*b[n] =  C

I want to solve for the values of X that will give the absolute minimum of C, given the input D and lists and A and B consisting of a[0 - n] and b[0 - n ].

I'm doing the problem at the moment in Python, but the problem in general is language-agnostic.

CLARIFICATION UPDATE: the coefficients x[0 - n] are restricted to the set of non-negative integers.

Improve this question
7
  • On a casual glance, it looks like this problem would have multiple solutions. Can you give some actual data to look at? Commented Oct 22, 2008 at 19:51
  • Have x[0] ... x[n] to be greater than or equal to zero? Commented Oct 22, 2008 at 20:48
  • Yes, they do. Thanks for the clarifying question. Commented Oct 22, 2008 at 21:18
  • Hmm, then I would also stick with linear programming... Commented Oct 22, 2008 at 21:22
  • INTEGERS! Then it is an integer programming problem (much more difficult), branch&bound and all the like will do. Commented Oct 22, 2008 at 21:24

5 Answers 5

Reset to default
11

This looks like a linear programming problem. The Simplex algorithm normally gives good results. It basically walks the boundaries of the subspace delimited by the inequalities, looking for the optimum.

Think of it visually: each inequality denotes a half-space, a plane in n-dimensional space that you have to be on the right side of. Your utility function is what you're trying to optimize. If the space is closed, the optimum is going to be at one of the apexes of the closed space; if it's open, it's possible that the optimum is infinite.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

Have a look at the wikipedia entry on linear programming. The integer programming section is what you're searching for (the constraint of the x[i] being integers is not an easy one).

Search python libraries for branch&bound, branch&cut and the like (I don't think they have been implemented in scipy yet).

Other interesting links:

Improve this answer

Comments

2

It looks like this is a linear programming problem.

Improve this answer

Comments

1

You might want to use Matlab or Mathematica or look at code from Numerical Recipes in C for ideas on how to implement minimization functions. The link provided is to the 1992 version of the book. Newer versions are available at Amazon.

Improve this answer

Comments

0

This company has a tool to do that sort of thing.

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.