Solving an inequality for minimum value

Question

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.

Answer 1

On a casual glance, it looks like this problem would have multiple solutions.

Can you give some actual data to look at?

Answer 2

It looks like this is a linear programming problem.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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:

• GNU Linear Programming Kit
• IBM article on GLPK