Skip to main content
added 410 characters in body
Source Link
Ryan Williams
  • 4.7k
  • 27
  • 38

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!

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

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!

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!

Source Link
Ryan Williams
  • 4.7k
  • 27
  • 38

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

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!