4 ms·

Could you handle your example in MIP through the objective function, making time outside normal hours expensive, but balancing that with a positive value for lu

by zelos 7y ago

Could you handle your example in MIP through the objective function, making time outside normal hours expensive, but balancing that with a positive value for lunchtime? Possibly with an integer value limiting the number of days where normal hours can be violated?

roenxi 7y ago
It is sort of trivially true that any nonlinear model in practice can be approximated by a sufficiently complicated linear model. So yes, probably. However that is not without cost. It reduces the amount of computer time required and increases the amount of human interpretation and attention required (+ increased time to linearise the original model). On the face of it that is a questionable trade. My anecdotes are somewhere close to the grandparent's where I'd prefer to see the heuristic method tried first before a linear model is attempted. If nothing else implementing a GA or simulated annealing algorithm is generally very cheap and debuggable in a way that moderately complicated linear models aren't. I'd guestimate that there are 5-10x more programmers who can implement a genetic algorithm than could tackle mixed integer optimisation. Debugging AMPL code is not a straightforward or satisfying experience.
- kragen 7y ago
  > I'd guestimate that there are 5-10x more programmers who can implement a genetic algorithm than could tackle mixed integer optimisation. You don't need 5–10× more wizards, though; you only need one wizard. If her ILP optimal solution is 0.1% better than the GA heuristic solution — which it might not be! — that might mean 3% higher profits for your company for the year. We are not talking about riveting sheet metal here, where productivity is roughly proportional to the number of workers.
  - roenxi 7y ago
    :o That is cheating! You can't assume that one solution is better than another then use that assumption to support the conclusion that it is better. There is no particular reason to believe the ideal solution to the linear approximation is better than the approximate solution of a non-linear model. And shrugging off the people who understand the model as 'wizards' shows the pretty neat cultural problem - people start to believe they can't and won't understand why they are getting solutions that they get. Any fool can understand GAs and get a feel for the risks involved.
    - kragen 7y ago
      The meaning I intended was not the meaning you read.
edejong 7y ago
In addition to this remarks of the sibling comment, we don't always have a well-understood objective function. For example, how much is lunchtime worth compared with time outside normal hours? What we can say is that there is a certain 'badness' to it, which should increase exponentially or polynomially as we thread further outside of our preferred domain. These are known as soft constraints. A fundamental problem with soft constraints in MIP is that we cannot create cuts in the conflict graph. Technically, everything conflicts with everything else, but at very high badness. So, we then have to decompose the problem in a preconceived way, such as on geographical boundaries, time boundaries or using heuristics. This engineering can be challenging, especially given that MIP is often hard to debug. So, like the sibling comment: I prefer meta-heuristics over constraint logic programming in many cases, but I do not deny that CLP/MIP can be very useful as well.
- 7thaccount 7y ago
  Aren't CLP/MIP very different mathematically/programatically? I know they are more similar to each other than meta-heuristics, but I'm not sure shy. Assuming your linearization is good, at least you'll get a global optimum and the MIP gap. With meta-heuristics you have no clue where you could end up right?
kragen 7y ago
Yes, as I explained in https://news.ycombinator.com/item?id=22157419 https://news.ycombinator.com/item?id=22157419 you can model literally anything in MIP if it's in NP, but the structure of the problem may or may not peek through enough for your solver to run efficiently. Some MIP solvers are effectively alien technology from the future, so this can be worthwhile, but it isn't always.

by zelos 7y ago

roenxi 7y ago

It is sort of trivially true that any nonlinear model in practice can be approximated by a sufficiently complicated linear model. So yes, probably. However that is not without cost. It reduces the amount of computer time required and increases the amount of human interpretation and attention required (+ increased time to linearise the original model). On the face of it that is a questionable trade. My anecdotes are somewhere close to the grandparent's where I'd prefer to see the heuristic method tried first before a linear model is attempted. If nothing else implementing a GA or simulated annealing algorithm is generally very cheap and debuggable in a way that moderately complicated linear models aren't. I'd guestimate that there are 5-10x more programmers who can implement a genetic algorithm than could tackle mixed integer optimisation. Debugging AMPL code is not a straightforward or satisfying experience.

kragen 7y ago
> I'd guestimate that there are 5-10x more programmers who can implement a genetic algorithm than could tackle mixed integer optimisation. You don't need 5–10× more wizards, though; you only need one wizard. If her ILP optimal solution is 0.1% better than the GA heuristic solution — which it might not be! — that might mean 3% higher profits for your company for the year. We are not talking about riveting sheet metal here, where productivity is roughly proportional to the number of workers.
- roenxi 7y ago
  :o That is cheating! You can't assume that one solution is better than another then use that assumption to support the conclusion that it is better. There is no particular reason to believe the ideal solution to the linear approximation is better than the approximate solution of a non-linear model. And shrugging off the people who understand the model as 'wizards' shows the pretty neat cultural problem - people start to believe they can't and won't understand why they are getting solutions that they get. Any fool can understand GAs and get a feel for the risks involved.
  - kragen 7y ago
    The meaning I intended was not the meaning you read.

edejong 7y ago

In addition to this remarks of the sibling comment, we don't always have a well-understood objective function. For example, how much is lunchtime worth compared with time outside normal hours? What we can say is that there is a certain 'badness' to it, which should increase exponentially or polynomially as we thread further outside of our preferred domain. These are known as soft constraints. A fundamental problem with soft constraints in MIP is that we cannot create cuts in the conflict graph. Technically, everything conflicts with everything else, but at very high badness. So, we then have to decompose the problem in a preconceived way, such as on geographical boundaries, time boundaries or using heuristics. This engineering can be challenging, especially given that MIP is often hard to debug. So, like the sibling comment: I prefer meta-heuristics over constraint logic programming in many cases, but I do not deny that CLP/MIP can be very useful as well.

7thaccount 7y ago
Aren't CLP/MIP very different mathematically/programatically? I know they are more similar to each other than meta-heuristics, but I'm not sure shy. Assuming your linearization is good, at least you'll get a global optimum and the MIP gap. With meta-heuristics you have no clue where you could end up right?

kragen 7y ago

Yes, as I explained in https://news.ycombinator.com/item?id=22157419 https://news.ycombinator.com/item?id=22157419 you can model literally anything in MIP if it's in NP, but the structure of the problem may or may not peek through enough for your solver to run efficiently. Some MIP solvers are effectively alien technology from the future, so this can be worthwhile, but it isn't always.