|
Binary constraint 1 Year, 7 Months ago
|
Karma: 0
|
Hi,
well I try to solve this problem
| Code: |
min sum()w_i z_i
s.t z_i^2>=y_ij^2norm(X_j-a_i,2)^2
sum(y_ij)^2=1
y_ij(y_ij-1)=0
norm(z_i,2)2+norm(X_j,2)^2<=Mi
z_i>=0
|
where ai and Mi are the known, but I get always infeasibility while the problem is feasible and when I change the constraint z_i>0 by z_i>Ni with Ni the exact value of z_i, I get feasibility but the binary variable y_ij are wrong some of theme are near from 1 or 0 but the other are not, I don't know where is the error.
I use SeDuMi to solve it but using a reformulation with generalized problem of moments so the inequality are defined as localizing matrices and the equality are the equality multiply the basis to order 2, am I making me clear? I don't know where is the problem |
|
|
|
|
|
|
Re: Binary constraint 1 Year, 7 Months ago
|
Karma: 32
|
|
I think your notation has been messed up. Hard to understand some parts. Is w_i known?
Are you using YALMIPs built-in support for method of moments?
I think the problem is much more efficiently solving using mixed-conic programming instead of a semidefinite relaxation (which doesn't guarantee that you get a feasible solution, it only gives you a lower bound on achievable objective)
In short, impossible to say anything without your code.
|
|
lofberg
Platinum Boarder
Posts: 2280
|
|
|
|
|
Re: Binary constraint 1 Year, 7 Months ago
|
Karma: 0
|
|
w_i are known, well the code is much more complicated (a lot of functions are defined) when I try with simple example which I know the solution I get infeasibility, well I think that I have no error in my code, any suggestion??
Thank you
|
|
|
|
|
|
|
Re: Binary constraint 1 Year, 7 Months ago
|
Karma: 32
|
This would be the YALMIP implementation of the moment relaxation solution. Indeed, the lowest possble relaxation order yields infeasible binary
| Code: |
n = 2;
m = 2;
X = sdpvar(m,1);
a = randn(n,1);
M = rand(m,1);
w = randn(n,1);
z = sdpvar(n,1);
y = sdpvar(n,m,'full');
objective = z'*w
constraints = [z>=0];
constraints = [constraints, sum(sum(y))==1];
constraints = [constraints, y.*(y-1)==0];
for i = 1:m
for j = 1:n
constraints = [constraints, z(i)^2>=y(i,j)^2*(X(j)-a(i))^2];
constraints = [constraints, z(i)^2+X(j)^2 <= M(i)];
end
end
solvesdp(constraints,objective,sdpsettings('solver','moment'))
|
It will become very slow very quickly. Installing sparsepop and using that (by changeing the flag in sdpsettings) instead of moment might be better, but I don't think a semidefinite relaxation is the best way to go here.
Here is a mixed-integer version (big-M approach, so you should derive the largenumber carefully as always), solved using YALMIPs internal b&b framework. If you have cplex 12 installed, you can use that too
| Code: |
y = binvar(n,m,'full');
objective = z'*w
constraints = [z>=0];
constraints = [constraints, sum(sum(y))==1];
largenumber=50;
for i = 1:m
for j = 1:n
constraints = [constraints,norm(X(j)-a(i))<z(i)+largenumber*(1-y(i,j))];
constraints = [constraints, z(i)^2+X(j)^2 <= M(i)];
end
end
solvesdp(constraints,objective,sdpsettings('solver','bnb'))
|
And finally, if the problem really is feasible, and your relaxation says its not, well then your implementation is simply wrong. |
|
lofberg
Platinum Boarder
Posts: 2280
|
|
Last Edit: 2011/10/24 11:57 By lofberg.
|
|
|
Re: Binary constraint 1 Year, 7 Months ago
|
Karma: 0
|
well I rewrite your code in yalmip to the appropriate form and this is an example
| Code: |
function tstylmp()
n = 4;
m = 2;
X = sdpvar(2,m);
a =[0.4428 0.5187 0.3759 0.4290
0.8368 0.0222 0.8986 0.1996];
fopt =0.2898;
M =[0.8964;0.8964;0.9047;0.9359];
w = ones(n,1);
z = sdpvar(n,1);
y = sdpvar(n,m,'full');
objective = z'*w
constraints = [z>=0];
constraints = [constraints, sum(sum(y.^2))==1];
constraints = [constraints, y.*(y-1)==0];
for i = 1:n
for j = 1:m
constraints = [constraints, z(i)^2>=y(i,j)^2*((X(1,j)-a(1,i))^2+(X(2,j)-a(2,i))^2)];
end
constraints = [constraints, z(i)^2+X(1,1)^2+X(2,1)^2+X(1,2)^2+X(2,2)^2 <= M(i)];
end
solvesdp(constraints,objective,sdpsettings('solver','moment'))
constraints
objective
sdisplay(X)
end
|
I get this
| Code: |
SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, theta = 0.250, beta = 0.500
Put 1224 free variables in a quadratic cone
eqs m = 3875, order n = 275, dim = 21778, blocks = 11
nnz(A) = 16022 + 0, nnz(ADA) = 15015625, nnz(L) = 7509750
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 1.32E+000 0.000
1 : -2.62E-001 8.47E-001 0.000 0.6422 0.9000 0.9000 3.66 1 1 6.9E+000
2 : 2.25E-002 3.65E-001 0.000 0.4311 0.9000 0.9000 3.98 1 1 1.3E+000
3 : -1.01E-002 1.32E-001 0.000 0.3624 0.9000 0.9000 2.16 1 1 3.8E-001
4 : -6.74E-003 3.77E-002 0.000 0.2846 0.9000 0.9000 1.46 1 1 1.8E-001
SeDuMi had unexplained problems, maybe due to linear dependence?
YALMIP tweaks the problem (adds 1e6 magnitude bounds on all variables) and restarts...
SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, theta = 0.250, beta = 0.500
Put 1224 free variables in a quadratic cone
eqs m = 3875, order n = 8025, dim = 29528, blocks = 11
nnz(A) = 23772 + 0, nnz(ADA) = 15015625, nnz(L) = 7509750
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 1.50E+010 0.000
1 : -5.38E+005 8.86E+009 0.000 0.5918 0.9000 0.9000 1.00 1 1 1.6E+001
2 : -2.43E+005 3.66E+009 0.000 0.4127 0.9000 0.9000 1.00 1 1 7.1E+000
3 : -1.23E+005 1.06E+009 0.000 0.2910 0.9000 0.9000 1.00 1 1 2.8E+000
4 : -1.57E+003 4.16E+007 0.000 0.0391 0.9900 0.9900 1.00 1 1 1.1E+000
Nope, unexplained crash in SeDuMi! (could be memory issues or wrong binary)
Make sure you have a recent and compiled version
For better diagnostics, use sdpsettings('debug',1)
??? Error using ==> svd
Input to SVD must not contain NaN or Inf.
Error in ==> extractsolution>numranks at 108
[U{i},S{i},V{i}] = svd(moment{i});
Error in ==> extractsolution at 23
[U,S,V,ranks] = numranks(moment);
Error in ==> solvemoment at 289
x_extract = extractsolution(momentsstructure,options);
Error in ==> solvesdp at 205
[diagnostic,x,momentdata] = solvemoment(F,h,options,options.moment.order);
Error in ==> tstylmp at 23
solvesdp(constraints,objective,sdpsettings('solver','moment'))
|
|
|
|
|
|
|
|
Re: Binary constraint 1 Year, 7 Months ago
|
Karma: 32
|
You probably run out of memory as it says. Try using the debug flag as YALMIP tells you. When I run the code, it takes forever to finish. Still haven't crashed, but it's been running for 50 minutes!
Which makes no sense, considering that you can solve the MISOCP problem in 30 seconds (and using cplex it shouldn't take many seconds)
| Code: |
z = sdpvar(n,1);
y = binvar(n,m,'full');
objective = z'*w
constraints = [z>=0,sum(sum(y))==1];
for i = 1:n
for j = 1:m
constraints = [constraints, z(i)+1000*(1-y(i,j))>=norm(X(:,j)-a(:,i))];
end
constraints = [constraints, z(i)^2+X(1,1)^2+X(2,1)^2+X(1,2)^2+X(2,2)^2 <= M(i)];
end
solvesdp(constraints,objective,sdpsettings('solver','bnb'))
constraints
|
|
|
lofberg
Platinum Boarder
Posts: 2280
|
|
|
|
|
