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:

image

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:

image

 

See also: