Modeling XNOR in Pyomo

Question

I am writing a nurse patient matching algorithm, and I want to incorporate something into the objective function that measures how well the new patient-nurse assignments match the patient-nurse assignments from the previous day. I've introduced a new binary variable model.MATCHES_PREVIOUS which should be equal to the XNOR operation of model.Prev_Assignments and model.Assignments (if both are 0 or both are 1, then model.MATCHES_PREVIOUS is 1, otherwise it is 0).

#Sets

model.PatientIDs  = {0, 1, 2}
model.NurseIDs = {a, b}

Indexed parameter (indexed by (patient, nurse))

model.Prev_Assignments = {(0, a): 1, (0, b): 0, (1, a) : 0, (1, b) : 1, (2, a) : 1, (2, b) : 0}

Indexed variable (indexed by (patient, nurse))

model.Assignments = {(0, a): 1, (0, b): 0, (1, a) : 0, (1, b) : 1, (2, a) : 0, (2, b) : 1}

model.Matches_Previous = {(0, a): 1, (0, b): 1, (1, a) : 1, (1, b) : 1, (2, a) : 0, (2, b) : 0}

Currently, I'm trying to implement this with the below constraint, which I thought was the proper way to translate XNOR into a linear expression:

def matches_previous(self, patient, nurse):
  return model.Matches_Previous[patient, nurse] == (model.Assignments[patient, nurse] * model.Prev_Assignments[patient, nurse]) + (1 - model.Assignments[patient, nurse])  * (1 - model.Prev_Assignments[patient, nurse])

In the objective function, I include (-model.Matches_Previous) along with the other components (since I am minimizing the objective, this would maximize model.Matches_Previous).

However, this isn't giving the behavior I want. Note that there are other aspects of the model which would motivate it to produce assignments that are different from the previous assignments (e.g. changing patient workloads), but I want it to match the previous assignments as best as possible.

Any idea how to implement this better? I looked into Pyomo.GDP and LogicalConstriants, but I haven't been able to get this to work and the documentation is lacking for these modeling extensions.

Answer 1

So here is a strategy you might try. Note your attempt above makes the problem non-linear by multiplying variables, which is probably NOT desired.

You can code the XNOR variable in linear fashion, assuming there is some "pressure" on it... Let me explain.

In pseudocode:

Let X = binary variable
Let X_prev = other binary variable

Let P = binary variable {1: if X, X_prev are not equal, else 0}

So, we intend to make P a penalty that can be indexed (optionally) and summed up, then introduce 2 constraints

P >= X - X_prev
P >= X_prev - X

And in your objective function, use P to induce a penalty not a reward and it should work... something like:

Obj = <some other components> + p_weight * sum(P)   ; minimized