Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm a programmer and I came a across an interesting problem. I'm sure there is a mathematical method or an algorithm to solve it, but I don't know where to start with the search nor which literature to read. If anyone can please tell me what method to use to solve this kind of problem, I would appreciate it much.

Here's a simplified example:

a + b + c >= 100
d + e + f >= 50
g + h >= 30
x = 1
y = 1
z = 1
5xa + 8yb + 5zc + 3xd + 2ye + 2zf + 6xg + 7yh = w.

I need to find the values for a, b, c, d, e, f, g and h that minimize w.

Of course, those numbers are just thought-off; the real numbers are input into my computer program by the user, and number of variables (a,b,c...) might be different for each run.

This was the simple case. In step 2, I also need to add rules like this:

if (8yb + 2ye + 7yh > 620) then y = 0.8 else y = 1.0
if (d > 35) then x = 0.9 else x = 1.0
etc.

I understand I could write a set of formulas for each rules (by replacing the value for x, y or z and adding another (in)equation), however those rules are such that they might be met, but not necessary - it is only important to minimize W, and only those rules that can "help" should be "activated". I wonder if there is some way to write "if" in mathematics?

I believe I've seen this kind of problem when I was in grad school, but that was some 10 years ago and I can't remember, so I don't even know what to look for, and I also don't know how to classify this problem. Please re-tag.

share|improve this question
3  
You are looking for the simplex method (see en.wikipedia.org/wiki/Simplex_algorithm and en.wikipedia.org/wiki/Linear_programming). –  Harald Hanche-Olsen Mar 16 '10 at 11:18
add comment

3 Answers

up vote 2 down vote accepted

If you really have equations like

$ 5xa + 8yb + 5zc + 3xd + 2ye + 2zf + 6xg + 7yh \leq w $

and all of the letters above are variables, then in the most general case you have an instance of Multivariate Quadratic Equations, which is $NP$-complete. (Even without the "if...then" rules.) The hardness is really independent of the domain of the variables. As long as each variable domain takes on at least two distinct possible values, you are in the land of $NP$-hard. Note you can always force a variable $x$ to take on exactly two of the possible values $v_1$, $v_2$ by imposing that

$(x-v_1)(x-v_2) = 0$.

As mentioned in other comments, a tractable special case would be if $x$, $y$, $z$ are fixed and $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ vary over the rationals. In this case your problem is an instance of Linear Programming, known to be solvable in polynomial time (and efficiently in practice; note these two properties do not always coincide!).

Another potentially tractable case (in practice, not in theory) is when $x$, $y$, $z$ are fixed and some of the $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ can only be $0$ or $1$. (Typically this condition can be translated to: some variables in the range $a$ through $g$ can only take on one of two possible values such as $a=0.9$ or $a=1$, through a linear transformation.) This case is called Integer Linear Programming. Although it is also $NP$-complete, there is software available that can sometimes solve instances of these fairly efficiently. Moreover, depending on the "if...then" rules you have, you may be able to cleverly translate them into integer linear programming constraints. (Note an "if...then" rule has one of two possible outcomes for a variable, and similarly an integer-valued variable will have one of two possible outcomes.)

Here's a simple example of what I mean, though I don't think this example will help you directly. Suppose $x$ is a variable that's either 0 or 1 and $d$ is a coefficient. You want to translate: "if ($d \geq 35$) then $x=0$ else $x=1$". Look at the inequalities $d \geq (d-35)x + 35$, $d \leq (34.999-d)x+d$. When $x=0$, we have $d \geq 35$, $d \leq d$. When $x=1$, we have $d \geq d$, $d \leq 34.999$.

To get any more specific about things, I would need to know more properties of the problems you are trying to solve. Hopefully by searching for the names of the above problems you can find more relevant references. Good luck!

share|improve this answer
    
Thanks Ryan. X, Y and Z are really coefficients, but they vary depending on some values of a, b, c, d, ..., h and this needs to be taken into account when searching for minimal w. There is a fixed set of possible values for x, y, z, but more than two. For example, X can have 2, Y can have 5, Z can have only one. It depends on user input. And a, b, c, ... have to be integers. Looking into some answers others have provided, I'm now looking into Integer Programming using branch and bound method. Could you please give an example how to translate the "if-then" I gave in my question? –  Milan Babuškov Mar 16 '10 at 19:06
    
IF X, Y, and Z depend on a,b,c,etc., then they are essentially other variables. It could be that your best bet is to look at "fixed parameter tractable" algorithms for Integer Linear Programming. For example, if there are only k total variables in your problem then the problem can be solved in k^{O(k)} poly(n) time, independently of the domains. See > R. Kannan. Minkowski's convex body theorem and integer programming. Math. Oper. Res., 12(3):415--440, 1987. In my answer above, I will give a simple heuristic example of how to translate an "if...then" into inequalities. –  Ryan Williams Mar 16 '10 at 21:03
add comment

The simplified example you give, assuming the $x$, $y$ and $z$ are meant to just be coefficients and not variables themselves, is of a linear program. A few different methods exist to solve linear programs: simplex algorithm, ellipsoid algorithm and different interior point methods. The interior point and ellipsoid methods are guaranteed to run in polynomial time. The simplex algorithm is not; however, it usually performs well in practice.

In what you call step 2, where you add conditions that change the coefficients (i.e., $x$, $y$ and $z$), you no longer have a linear program; however it seems that your objective function is piecewise linear, so you may be able to decompose it into a set of linear programs and solve each independently (then simply take the best solution over all subproblems).

share|improve this answer
    
Thanks. x, y and z are really coefficients. Now my only concern is the time requires because I may have 20-30 conditions where coefficients change, which can create a lot of possible combinations to solve. –  Milan Babuškov Mar 16 '10 at 14:57
add comment

For code, check out GLPK and lp_solve. Wikipedia lists several other tools.

share|improve this answer
    
Thanks. I'm trying out lp_solve now. –  Milan Babuškov Mar 16 '10 at 18:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.