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,
Jorge
I'd do the following:
Let $y^*$ be your previous solution. You now want the next solution to be different from $y^*$. Let $J = \{1, \dots, M\}$ be your index set. Then you want it to hold that $\sum_{j \in J} abs(y^*_j -y_j)\geq 1$ where $y_j^*$ is the value of the $j$-th variable $y_j$ in the previous solution. That means that the two solutions differ in at least one variable. Let $J'=\{j\in J | y_j =1 \}$. Then:
$\sum_{j \in J} abs(y^*_j -y_j)=\sum_{j \in J'} (1 - y_j) + \sum_{j \in J\setminus J'} y_j \geq 1 $
$\Leftrightarrow \sum_{j \in J'} - y_j + \sum_{j \in J\setminus J'} y_j \geq - |J'|+1$
where $|J'|$ is the cardinality of J'. That means you can add a new row to your matrix with value -1 for each variable in $J'$, 1 for each variable not in J' and a row to the right hand side with value $- |J'|+1$, or if your writing your inequality as $Ax \leq b$, just flip the signs.