MATLAB: How to add integer cut to MILP constraints to find alternative optimal solutions

Question

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. Thus, if yj in the next optimization round takes values equal to those in a previous solution (y'_j), that solution is ruled out.

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. I suppose that the M-1 part goes in vector b, but I am unable to find some constants in matrix A such that A* x gives the expression on the LHS of my constraint.

Thank you very much for your help,

Answer 1

Let f represent the indices of your y'_j = 1 entries, and g represent the indices of your y'_j = 0 entries. Let gs be the number of terms in g, meaning

gs = length(g);

Then take a new row in your A matrix, say A(j,:), to have entries 1 in the f spots and -1 in the g spots:

A(j,f) = 1;
A(j,g) = -1;

Then the inequality for this row is

A*x <= M - 1 - gs;

This is because there are gs entries of 1 in your sum (1-y_j) for j a member of g. OK?

Alan Weiss

MATLAB mathematical toolbox documentation