MILP Impose Equality Constraint on Columns
2 views (last 30 days)
Show older comments
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
1 Comment
Matt J
on 28 Oct 2014
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?
Answers (1)
Alan Weiss
on 28 Oct 2014
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
0 Comments
See Also
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!