How to add integer cut to MILP constraints to find alternative optimal solutions?

Jorge B. Source

I am solving an MILP optimization with binary variables in MATLAB in which I want to find more than one optimal solution by excluding previous solutions. Therefore, I know I must include the following integer cut as a constraint in my model:

sum {y_j : y'_j = 1} + sum {(1-y_j) : y'_j = 0} <= M - 1

Where, y_j is my vector of binary variables. M is the total number of binary variables (j loops from 1 to M) and y'_j is the value of my binary variable in a previous solution.

In an MILP framework, constraints are included through a matrix A in the form: A* x <= b, where x is the vector of binary variables and b the RHS of known coefficients.

Then, my problem is I am unable to "translate" a constraint like the one above into this MILP format.

Thank you very much for your help,

Jorge

matlabmathematical-optimizationalgebramixed-integer-programming

Answers

answered 4 months ago Erwin Kalvelagen #1

  1. Create a row with all zeros
  2. If y*[j]=1 (the optimal value of y[j]) then put a 1.0 in the column corresponding to y[j]
  3. if y*[j]=0, put a -1.0 in the corresponding column
  4. Set the rhs to the number of y*[j]=1 minus one.

comments powered by Disqus