4 ms·

In my experience, each sufficiently complicated model becomes non-linear in some respect. For example, you might want to work with margins for time-slots that a

In my experience, each sufficiently complicated model becomes non-linear in some respect. For example, you might want to work with margins for time-slots that are non-linear but smooth. So, even though I've worked with constrained linear programming in the past, I tend to prefer algorithms with meta-heuristics, such as simulated annealing or Tabu search. Although this might not provide the 'best' solution, it provides a wider range of modelling tools. To elaborate a bit on a use-case. Lets say we want to plan a high-school roster. Teachers might have a maximum of 8 hours per day of work, but if we make a hard cut-off at that time, we might miss an interesting 8:15 schedule that gives a teacher more time to have proper lunch. If, furthermore, we do not break the 40 hr./week rule, it might be a workable schedule. Also, it provides the search algorithm a usable gradient, so the search space becomes smooth and easier to navigate. Finally, if we provide several top solutions, we give a human planner information on how the problem is (over-)constrained.

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.
LolWolf 7y ago
There are also ways around this by suitable generalizations of MILPs, namely mixed integer comic programs (MICPs), which are about as fast to solve in practice. This generalization allows you to use nonlinear (convex) functions in the objective and in constraints. Coupled with the integrality constraints, almost all nonlinear problems I’ve encountered can be written as MICPs.
- agravier 7y ago
  mixed integer convex programming, not comic (unfortunately; although I hope someone takes this as a challenge). Or maybe you meant conic programming? As in MISOCP
  - LolWolf 7y ago
    I did mean to write mixed integer convex optimization; on the other hand, conic programming includes convex programming as a special case (and vice versa in the case where cones are convex). Most convex problems we solve (e.g. When written in a high level DSL like CVXPY) are reduced to conic forms (such as SOCPs, but also SDPs, etc) before they are solved.
  - LolWolf 7y ago
    Oh, oops, I just realized I actually wrote "comic," oops! (My phone really does not like the word conic for whatever reason...) Would be a fun (and uhh, interesting?) challenge indeed, whatever that would entail :)
    - kragen 7y ago
      It fits in well with your username! There have been a number of (computer) programming environments that used a comic-strip-like format to depict a sequence of events; I think some are profiled in Watch What I Do and/or Your Wish Is My Command, which I don't have with me at the moment.

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.

LolWolf 7y ago

There are also ways around this by suitable generalizations of MILPs, namely mixed integer comic programs (MICPs), which are about as fast to solve in practice. This generalization allows you to use nonlinear (convex) functions in the objective and in constraints. Coupled with the integrality constraints, almost all nonlinear problems I’ve encountered can be written as MICPs.

agravier 7y ago
mixed integer convex programming, not comic (unfortunately; although I hope someone takes this as a challenge). Or maybe you meant conic programming? As in MISOCP
- LolWolf 7y ago
  I did mean to write mixed integer convex optimization; on the other hand, conic programming includes convex programming as a special case (and vice versa in the case where cones are convex). Most convex problems we solve (e.g. When written in a high level DSL like CVXPY) are reduced to conic forms (such as SOCPs, but also SDPs, etc) before they are solved.
- LolWolf 7y ago
  Oh, oops, I just realized I actually wrote "comic," oops! (My phone really does not like the word conic for whatever reason...) Would be a fun (and uhh, interesting?) challenge indeed, whatever that would entail :)
  - kragen 7y ago
    It fits in well with your username! There have been a number of (computer) programming environments that used a comic-strip-like format to depict a sequence of events; I think some are profiled in Watch What I Do and/or Your Wish Is My Command, which I don't have with me at the moment.