Wednesday, October 23, 2019

Rolling horizon approach for scheduling model

I need to run a (large) scheduling model with a planning horizon of several months: october 2019 through march 2020. This leads to a very large MIP model. One way to split this up into smaller problems is to solve it one month at the time.

Simple approach


This is easier said than done. We don't have a nice break in the schedule at the end of the month. Assignments are bleeding into the next month:

Schedule (partial view)


One way to deal with this problem is to shift the window a bit more complicated way:

Tailored rolling horizon algorithm

We basically solve the problem as a MIP two months at the time, but shift it by only one month. The binary variables more in the future are relaxed to continuous variables. That part becomes like an LP. I.e. the green parts are easy. Past binary variables are fixed. Of course, the MIP presolver will remove all fixed variables from the model, so the orange parts are also easy.

This approach only really works if we don't have global constraints over all months. The danger is that we push the bad stuff into the future. That can even lead to infeasible sub-problems at the end.  Luckily this model has no constraints that span all six months.

If we want we can solve the big model at the end using the solution we built up in parts as a starting point (using the mipstart option). If the algorithm is working as expected, this last big MIP model should not find solutions that are much better. This is indeed the case for my model. (Note that not all sub-problems are solved to optimality -- sometimes a small gap remains).


3 comments:

  1. Hi, thanks for a good blog!
    I wonder which solvers have the 'mipstart' option? Do you know how CPLEX exposes it, for instance?

    ReplyDelete
    Replies
    1. I don't have a list available but many MIP solvers have a mipstart facility. The Cplex documentation has a chapter called Using MIP Starts that lists all related API calls.

      Delete
  2. About the relaxed MIP in the future periods : What about the objective function? The objective function , when , is a sum over all the months taken together, it will be problem right? And I guess, the objective is also a sum over all months in your case too.

    ReplyDelete