Tuesday, March 12, 2013

Meta-Heuristics or Math Programming (2): Comparing solutions

A well-known example data set for Generator Maintenance Scheduling (GMS) is the basis for quite a few computational studies using meta-heuristics. The data sets has 21 units, has time-periods of a week and asks for a yearly schedule. This note is actually a follow up to http://yetanothermathprogrammingconsultant.blogspot.com/2013/02/meta-heuristics-or-math-programming.html. To my knowledge the data sets used in the references were not solved to optimality before. So it is time to see if we can do something about that. There are a few good linear approximations that can be used to create good schedules, but here we will use the identical quadratic objective used in the other studies. This means we are dealing with an MIQP (Mixed Integer Quadratic Programming) model. Solvers like Cplex and Gurobi offer MIQP capabilities, although in general MIQPs are more difficult to solve than comparable MIP problems.

From the thesis “Decision Support for Generator Maintenance Scheduling in the Energy Sector”, Evert Barend Schl├╝nz, Stellenbosch University, Dec 2011:

  image_thumb1

Actually, using a careful implementation of the MIQP formulation I was able to prove global optimality, with an objective of:

---- 220 PARAMETER TotalSumSquares = 1.361890E+7

This was with Gurobi on a laptop using 4 threads in 47 minutes (most of the time was spent in proving optimality – in practice we could have stopped much earlier).

Indeed the meta-heuristics are a little bit off:

image_thumb5

Some heuristics claim better results than I have been able to verify:

image_thumb7

But that turns out to be an infeasible solution:

image_thumb11

Others are not as good:

image_thumb9

My solution is shown below:

gms_res1gms_res2