|
Re: Binary constraint 1 Year, 6 Months ago
|
Karma: 0
|
well I run this code
| Code: |
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];
%a = rand(2,n)
%[C, fopt,N, TT,indx,MM]=testM(a,2,1);
%C
%fopt
%M=cell2mat(N);
w = ones(n,1);
z = sdpvar(n,1);
y = binvar(n,m);
objective = z'*w;
K=[];
for i=1:n
K=[K,sum(y(i,:))==1];
end
%K = [K, y.*(y-1)==0];
K = [z>=0];
for i = 1:n
for j = 1:m
K = [K, z(i)^2-y(i,j)^2*((X(1,j)-a(1,i))^2+(X(2,j)-a(2,i))^2)>=0];
end
K = [K, M(i)-z(i)^2-X(1,1)^2-X(2,1)^2-X(1,2)^2-X(2,2)^2 >=0 ];
end
solvesdp(K,objective,sdpsettings('solver','bnb'))
double(objective)
double(X)
double(z)
double(y)
|
and I get
| Code: |
* Starting YALMIP integer branch & bound.
* Lower solver : fmincon-standard
* Upper solver : rounder
* Max iterations : 300
Node Upper Gap(%) Lower Open
1 : 0.000E+000 0.00 0.000E+000 0
+ 1 Finishing. Cost: 0
ans =
yalmiptime: 0.155999999999999
solvertime: 0.265999999999998
info: 'No problems detected (BNB)'
problem: 0
dimacs: [NaN NaN 0 0 NaN NaN]
ans =
0
ans =
0.520527824616399 0.430515908185903
0.430515908185903 0.200231871156247
ans =
0
0
0
0
ans =
0 0
0 0
0 0
0 0
|
as you see all y_ij are zero then the constraint sum(y(i,  )==1 is not satisfied. |
|
|
|
|
|
|
Re: Binary constraint 1 Year, 6 Months ago
|
Karma: 32
|
|
should be
K = [K, z>=0];
|
|
lofberg
Platinum Boarder
Posts: 2280
|
|
|
|
|
Re: Binary constraint 1 Year, 6 Months ago
|
Karma: 0
|
|
sorry I didn't pay attention
|
|
|
|
|
|
|
Re: Binary constraint 1 Year, 6 Months ago
|
Karma: 32
|
and as you have posed it now, it will yield a problem with nasty nonconvex binary relaxations since you multiply y and squared terms. Hence bnb complains and warns you that it will probably not be solved to global optimality. You should use the big-M form I gave on the first page, since the binary relaxations then will be SOCPs, hence you get a MISOCP, which can be solved to optimality using either bnb+sedumi, or cplex.
If you want to understand what big-M is, here is a start
users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Big-M |
|
lofberg
Platinum Boarder
Posts: 2280
|
|
|
|
|
Re: Binary constraint 1 Year, 6 Months ago
|
Karma: 0
|
Maybe I am telling you something stupid gain, but I try the bigM formulation and I I still getting some anomaly:
yalmiptime: 0.1710
solvertime: 3.0160
info: 'No problems detected (BNB)'
problem: 0
dimacs: [NaN NaN 0 0.0329 NaN NaN]
but the constraints "M(i)-z(i)^2-X(1,1)^2-X(2,1)^2-X(1,2)^2-X(2,2)^2>=0"are not respected
| Code: |
function tstylmp()
format short;
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];
xopt =[0.4428 0.5187;0.8368 0.0222];
fopt = 0.2899;
M = [1.2658;1.2658;1.2741;1.3054]
%a = rand(2,n)
%[C, fopt,N]=testM(a,2,1)
%M=cell2mat(N);
w = ones(n,1);
z = sdpvar(n,1);
v = sdpvar(n,1);
y = binvar(n,m);
objective = z'*w+10*sum(v);
K=[];
for i=1:n
K=[K,sum(y(i,:))==1];
end
%K = [K, y.*(y-1)==0];
K = [K,z>=0];
K = [K,v>=0];
for i = 1:n
%for j = 1:m
K = [K, z(i)^2-y(i,1)*((X(1,1)-a(1,i))^2+(X(2,1)-a(2,i))^2)-y(i,2)*((X(1,2)-a(1,i))^2+(X(2,2)-a(2,i))^2)-v(i)>=0];
%end
K = [K, M(i)-z(i)^2-X(1,1)^2-X(2,1)^2-X(1,2)^2-X(2,2)^2>=0 ];
K = [K, 1-v(i)>=0 ];
end
%K
solvesdp(K,objective,sdpsettings('solver','bnb'))
checkset(K)
fopt
double(objective)
double(X)
double(z)
double(y)
double(v)
end
|
??
Thank you |
|
|
|
|
|
|
Re: Binary constraint 1 Year, 6 Months ago
|
Karma: 32
|
Which solvers are invoked by bnb (displayed when it starts). What does the complete display look like.
On my machine, fmincon is used, and fails completely thus leading bnb to conclude that the problem is infeasible (once again, a consequence of the fact that this is a bad formulation, since it yields nonconvex relaxations)
| Code: |
* Starting YALMIP integer branch & bound.
* Lower solver : fmincon-standard
* Upper solver : rounder
* Max iterations : 300
Warning : The continuous relaxation may be nonconvex. This means
that the branching process is not guaranteed to find a
globally optimal solution, since the lower bound can be
invalid. Hence, do not trust the bound or the gap...
Node Upper Gap(%) Lower Open
1 : Inf Inf 8.772E+006 2 No problems detected
2 : Inf Inf 8.772E+006 1 Infeasible problem
3 : Inf Inf 8.772E+006 0 Infeasible problem
+ 3 Finishing. Cost: Inf
|
|
|
lofberg
Platinum Boarder
Posts: 2280
|
|
|
|
|
