Friday, February 22, 2013

Meta-Heuristics or Math Programming

The problem of scheduling maintenance of generators is a well-studied problem. In particular a specific data sets has been used a lot:

 

all use the same problem. They all use some form of meta-heuristics. However this problem is also easily solved by mathematical programming. The following reformulations have helped:

  • Look at the data: the 12 month schedule can be split into two 6-month schedules. Solves 2 smaller problems is in general faster than solving one big one.
  • Use a linearization technique. Although the original problem can be formulated as a MIQP, it turns out that some MIP formulations are still faster and more reliable (e.g. Cplex has serious problems with the MIQP models). See: http://yetanothermathprogrammingconsultant.blogspot.com/2012/11/smoothing.html.

Some advantages of using math programming approaches are:

  • May be able to prove global optimality
  • May give bounds to assess quality of a solution when terminated before proving optimality
  • Modeling vs programming may (or may not) lead to more maintainable systems (easier to adapt to new circumstances, especially when using a modeling language).