Hi everyone, I need your help with my strange solution obtained by cvx.
Assume that, C is a constant, m and p are same-size matrices containing zero and positive real values. The following is my simple convex opt problem:
cvx_begin variable x(e,e); maximize (sum(sum(m(1:e,1:e).*(1-x(1:e,1:e))+(p(1:e,1:e).*x(1:e,1:e))))) subject to for i=1:e x(i,i)==1; %constraint #1 sum(x(i,:))<=C; %constraint #2 for j=1:e 0<=x(i,j)<=1; %constraint #3 if j~=i for k=i+1:e if k~=j x(i,j)+x(j,k)-x(i,k)<=1; % %constraint #4 (presumably causes issue) end end end end end cvx_end
The solution to this problem contains some flaws (despite getting no error). The values of x are partially negative which shows that cvx disregards the 3rd constraint, however, excluding the 4th constraint, the solution is mostly conceivable. My cvx is the latest version on which Gurobi and Mosek are enabled as well.
What’s wrong with the 4th constraint? (x_i,j + x_j,k - x_i,k ≤ 1, ∀i,j,k∈E:k>i,j≠i,k)
Two thoughts. First of all, you haven’t specified the absolute levels of constraint violation here. Small violations due to roundoff error are expected and must be handled by the modeler. There might also be scaling issues depending upon the absolute values of C, m, and p.
@mcg Thanks for your response Michael. In this problem C is supposed to be smaller than e. (for instance e=20, C=5). The elements of m and p are real positive values within the range [0,inf), however, in my experiment they scarcely exceed 10 or 20. I should also add this that in the above LP-relaxation problem x, m and p are symmetric matrices.
If the matter was only small violation of x elements (which exists now), we could handle it manually as you mentioned. But the latest constraint which is known as “triangular condition” is not guaranteed after the problem is solved. It should satisfy the fact that if x(i,j)=1 and x(j,k)=1, then it is implied that x(i,k)=1, Even if I handle the trivial violation, I am still having trouble with the absence of “triangular condition” in the solution.