4 ms·

A single decision could still be easily modeled by a 0/1 variable (as an input) and a real variable (as an output, like revenue for example). That 0/1 input va

A single decision could still be easily modeled by a 0/1 variable (as an input) and a real variable (as an output, like revenue for example). That 0/1 input variable could also have arbitrary interactions with other variables, which would also amount to “step function “ input effects. See for example the autism/age setup down thread.

eru 2y ago
Discrete linear optimisation is infinitely more complicated than continuous linear optimisation. The former is NP complete, the latter is in P.
- naasking 2y ago
  Which seems almost ironic, because continuous linear optimization almost certainly doesn't exist really because real numbers can only be approximated, and so we're always doing discrete linear optimization at some level.
  - eru 2y ago
    Who cares about real numbers in this context? If all the numbers that appear in your constraints are rational (p/q with finite p and q), then any solution is also a rational number (with finite nominator and finite denominator). (Well, any finite solution. Your solution could also be unbounded, then you might have infinities in there.) A computer can represent finite rational numbers just fine. See eg https://docs.python.org/3/library/fractions.html https://docs.python.org/3/library/fractions.html or https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-Ratio.html https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-... for some libraries. Though in most cases, people just use floating point numbers in practice, but that's of no philosophical concern.
- mturmon 2y ago
  No argument with that fact. But the parent comment is not talking about constrained optimization, just gradient following. In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” The question is not, “if I can only set M of these N variables to 1, which should I choose?” That’s a good question, and it leads to problems in NP, but that’s not what the comment was referring to.
  - eru 2y ago
    > In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” Yes, you are right in that abstract setting. If you always have the full hypercube of available, the problem is as easy as you describe. But if there are constraints between the variables, it gets hairier.

eru 2y ago

Discrete linear optimisation is infinitely more complicated than continuous linear optimisation. The former is NP complete, the latter is in P.

naasking 2y ago
Which seems almost ironic, because continuous linear optimization almost certainly doesn't exist really because real numbers can only be approximated, and so we're always doing discrete linear optimization at some level.
- eru 2y ago
  Who cares about real numbers in this context? If all the numbers that appear in your constraints are rational (p/q with finite p and q), then any solution is also a rational number (with finite nominator and finite denominator). (Well, any finite solution. Your solution could also be unbounded, then you might have infinities in there.) A computer can represent finite rational numbers just fine. See eg https://docs.python.org/3/library/fractions.html https://docs.python.org/3/library/fractions.html or https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-Ratio.html https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-... for some libraries. Though in most cases, people just use floating point numbers in practice, but that's of no philosophical concern.
mturmon 2y ago
No argument with that fact. But the parent comment is not talking about constrained optimization, just gradient following. In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” The question is not, “if I can only set M of these N variables to 1, which should I choose?” That’s a good question, and it leads to problems in NP, but that’s not what the comment was referring to.
- eru 2y ago
  > In the context of this post, that’s just “which of these N discrete variables, if moved from 0 to 1, will increase the quantity of interest according to the linear model?” “Which will decrease it?” Yes, you are right in that abstract setting. If you always have the full hypercube of available, the problem is as easy as you describe. But if there are constraints between the variables, it gets hairier.