MILP Impose Equality Constraint on Columns

Dear Community,

I have to solve the following binary optimization problem.

min C'X
X = m x n
s.t.
C1: sum(x(i)) = 1 - the sum of X on rows in the optimal solution is to be 1
C2: The number of columns with non-zero elements in X to be equal to 3!

I have my equality constraints matrix for the first constraint defined as a block diagonal matrix with equal number of rows as X and columns equal to the number of elements in C.

How do I define my second constraint? Any ideas will be welcome.

Many thanks, Stefan

[Matt J]

It's not clear how C'X works out to be a scalar if X is m x n. Do you really mean

     min C.' * X(:)

where C is a column vector?

Answer 1

[Alan Weiss]

I am not sure that I understand your problem, but perhaps what you need is a set of indicator (binary) variables y(j) where y(j) = 1 if there is at least one nonzero x(i,j) in column j, and y(j) = 0 otherwise. Then you need to have a constraint sum_j y(j) = 3.

If that is correct, then tie your variables y(j) to the x(i,j) using the following inequalities:

 y(j) <= sum(x(i,j)) % so y(j) = 0 when all x(i,j) = 0
 sum(x(i,j)) <= m*y(j) % m is the number of rows of X

Include these new variables and new linear inequality constraints, and I believe that your problem will be solved.

Alan Weiss

MATLAB mathematical toolbox documentation