1

Can you please identify what class of problem this is so that I can research algorithms for solving it please?

Its a a set of linear equations and inequalities/constraints looking like this:

a = 3*g
b = 1*h + 2
c = 1
d = 2
e = if (a >= b) then 1 else 0
f = if (a < b) then 1 else 0
g = if (c >= d) then 1 else 0
h = if (c < d) then 1 else 0

The equations can be more complicated but follow the same form e.g.

a = 3*g + 2*h + 3*i + 2
g = if (c >= d and c >= e and c >= f ) then 1 else 0

I'm not sure what you call the inequalities/constraints with if/then/else type construct and I expect there is a more standard way to express them. I think they could be expressed with the signum function but that doesn't take me much further.

Representing IF ... THEN ... ELSE ... in math notation

Community
  • 1
daw
  • 111
  • Hey. How are your equations linear? They seem to involve quadratic terms like $aq$, $ct$ and so on. – Mankind Dec 13 '15 at 13:21
  • Looks like a linear program with additional set-up costs. – Gyro Gearloose Dec 13 '15 at 13:24
  • @HowDoIMath Sorry I'm a programmer not a mathematician. "aq" is just a multi-character name. Shall I rewrite the example with single-character variable names? – daw Dec 13 '15 at 13:25
  • @GyroGearloose interesting but I'm not sure what that means - can you suggest a reference to read? – daw Dec 13 '15 at 13:28
  • @daw Ah, ok. It's alright. In case you don't know, this site uses MathJax (or LateX), which you can read more about here: http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference – Mankind Dec 13 '15 at 13:29
  • @daw https://en.wikipedia.org/wiki/Linear_programming but this does not include your if-then-else yet, it gets much harder with that. – Gyro Gearloose Dec 13 '15 at 13:31
  • @GyroGearloose I don't see how to map if-then-else into the linear-programming form - I guess this is what you mean by "setup cost" but its the part I seek guidance on. – daw Dec 13 '15 at 13:34
  • @daw exactly. Think of it this way: a linear program alone solves some problem like "given some limited resources and some possible products, how much should I produce of each product to maximize profit", but in real life there are additional set-up costs for each product. This way the problem gets NP-hard. – Gyro Gearloose Dec 13 '15 at 13:38
  • @GyroGearloose it sounds like we agree its not a linear programming problem - I'm trying to identify what class of problem it actually is and appropriate algorithms for it – daw Dec 13 '15 at 14:15
  • @daw sounds like a Mixed Integer Problem (same wiki article). – Gyro Gearloose Dec 13 '15 at 14:19

0 Answers0