Wednesday, April 3, 2013

Hamming distance and persistent solutions

When building scheduling models it is often important to make sure that a new schedule is not radically different from an old schedule unless there is a very good reason (e.g. we can make a lot of money by doing so). One way to handle this is to adds a cost-term to the objective that measures the difference between two schedules.

As we usually use binary variables to model a schedule, we basically need to find a way to write:


where we measure the difference between a new solution x and a previous solution x*. Here x is a decision variable and x* is a parameter.

Here are some (equivalent) ways to write this as a linear expression:



See also:

1 comment:

  1. I remember in Uni they were teaching us that for such systems, it's best to use local search -- by design it will find a solution that is close to the original solution. I guess the solving systems and computations power have evolved so much that it's better to just model the distance, too.