Search code examples
optimizationmathematical-optimizationcplexnonlinear-optimizationconstraint-programming

IBM CPLEX use XOR in objective function

I want to model the Max-Cut problem for graphs.

As you need to select a subset of the vertices, my approach is to encode each vertex with a boolean decision variable.

My problem is the objective function: And edge {a,b} is in the cut exactly if one of its vertices is in the subset while the other is not, which is the logical XOR.

I don't see a way how to include "1 if XOR(a,b) else 0" in the objective function. Should the approach be entirely different?

Solution

  • z = x xor y can be written as a system of linear inequalities:

      z ≤ x+y
  z ≥ x-y
  z ≥ y-x
  z ≤ 2-x-y