Which method to apply to this problem?

Question

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.

Answer 1

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!

Answer 2

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).

Answer 3

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