How to solve a system of inequalities?

问题:

I've reduced my problem (table layout algorithm) to the following problem:

Imagine I have N variables X₁, X₂, ..., X_N. I also have some (undetermined) number of inequalities, like:

X₁ >= 2
x₂ + X₃ >= 13
etc.

Each inequalities is a sum of one or more variables, and it is always compared to a constant by using the >= operator. I cannot say in advance how many inequalities I will have each time, but all the variables have to be non-negative, so that's already one for each variable.

How to solve this system in such a way, that the values of the variables are as small as possible?

Added: Read the wikipedia article and realized that I forgot to mention that the variables have to be integers. Guess this makes it NP-hard, huh?

回答1:

Minimizing x1 + x2 + ... where the xi satisfy linear constraints is called Linear Programming. It's covered in some detail in Wikipedia

回答2:

What you have there is a pretty basic Linear Programming problem. You want to maximize the equation X_1 + ... + X_n subject to

X_1 >= 2
X_2 + X_3 >= 13
etc.

There are numerous algorithms to solve this type of problem. The most well known is the Simplex algorithm which will solve your equation (with certain caveats) quite efficiently in the average case, although there exist LP problems for which the Simplex algorithm will require exponentially many steps to solve (in the problem size).

Various implementations of LP solvers exist. For example LP_Solve should satisfy most of your requirements

回答3:

You may also post directly your linear model to NEOS platform (http://neos.mcs.anl.gov/neos/solvers/index.html) . What you simply have to do first is write your model in an algebraic language such as AMPL. Then NEOS will solve the model and returns the results by e-mail.

回答4:

Linear programming