On the 0-1 combinatorial optimization issue

21

I don’t understand exactly what you are saying. But I will answer what I am guessing you mean.

If you require the same power plant to customer assignment in each of the K hours, then define Q as an M by N binary variable. And then your cost needs to be summed over all K hours, and your supply constraint needs to match whatever the actual supply constraint is (I don’t know whether supply per hour for each power plant is the same for all K periods). P and D can vary or not across the K periods, and you’ll have to decide what’s appropriate for your problem…

As for “Q is always inclined to all one in certain line in Q after optimization”, I don’t understand what you mean, but if you mean that there is one row in Q which is all ones, and all other rows of Q are zeros, then that could (would) be the legitimate solution if that power plant has the lowest power price and has sufficient supply for all customers, or that if not the lowest price power plant, none of the lower price plants have enough supply for any customer. My constraint sum(Q.*D,2) <= S ensures that no power plant provides more power than its supply, so of course it’s a very important constraint - if you forget this constraint, the lowest price power plant will supply power to all customers.

I think at this point, all your CVX difficulties should have been resolved, so it’s up to you to build a model suitable for your problem.

22

Mark,

This question remains! I posted the sources codes in here. please assist to find question. Thank!

%% parameter initialization
M=2; % power suppliers #
N=10; % power customers #
K=24; % 24hrs time intervals per day
m_ik=0.5+1.*rand(N,K); % customer mini power usage
M_ik=3+5.rand(N,K); % customer max power usage
t=0; % iteration #
w=randi([1 4],N,K); % customer willing to buy power
L=randi([5 50],M,K); % power capability upper-bound per time interval
alpha=0.01;
th=2.8;
%% customer power usage update and optimization
r_ij=randi([1 M],N,1); % random power supplier selection N by 1
r_ij_ex=zeros(M,N);
for i=1:N
r_ij_ex(r_ij(i),i)=1;
end
R=r_ij_ex;
lambda_jk=0.2+0.6rand(M,K); % initial electricity price
c=ones(N,K);
flag=1; % while loop flag

while(flag)
t=t+1;
for k=1:K
W(:,:,k)=repmat(w(:,k)’,M,1); % M by N by K
Q(:,:,k)=repmat(lambda_jk(:,k),1,N); % electricity price
end
r=reshape(repmat(R,1,K),M,N,K); % power supplier selection
% for k=1:K
% for i=1:N
cvx_begin
variable x(N,K);
% variable x(i,k);
maximize(sum(sum(4.(log(x+c)-x.(R’*lambda_jk))),2));
% maximize(w(i,k).*log(x(i,k)+c(i,k))-x(i,k)sum(r(:,i,k). …
% (Q(:,i,k))));
subject to
m_ik<=x<=M_ik;
cvx_end
% X(i,k)=x(i,k);
% end
% end
for k=1:K
XX(:,:,k)=repmat(x(:,k),1,M)’;
end
%% power suppliers selection (combinatorial optimization)
% for i=1:N
cvx_begin
variable R(M,N) binary;
minimize(sum(sum(R.*sum(XX.*Q,3))));
% maximize(sum(sum(w.*log(x+c)))-sum(sum(R.*sum(XX.Q,3))));
subject to
sum(R,1)==1;
% Rx<=L;
cvx_end
% end
tmp=lambda_jk;

%% Lagrangian multiplier update 
delta_lambda_jk=zeros(M,K);
for k=1:K
    for j=1:M
        delta_lambda_jk(j,k)=L(j,k)-sum(R(j,:).*XX(j,:,k),2);
        if delta_lambda_jk(j,k)<0
            delta_lambda_jk(j,k)=0;
        end
        lambda_jk(j,k)=lambda_jk(j,k)-alpha.*delta_lambda_jk(j,k);
        if lambda_jk(j,k)<0
            lambda_jk(j,k)=0;
        end
    end
end
if sum(sum(abs(tmp-lambda_jk)))<=th
    flag=0;
    x_opt=x;
    lambda_opt=lambda_jk;
    r_ij_opt=zeros(1,N);
    for i=1:N
        [Y,I]=max(R(:,i));
        r_ij_opt(i)=I;
    end
end

end

Thanks again!

23

You posted code. I don’t know what it does. I do not have integer capability in my installation, but I was able to run it by removing the binary variable declaration on R and imposing the constraint 0 <= R <= 1, which of course is not binary. Doing so, it ran (therefore is valid CVX code) and provided an answer. The values of R came out to all zeros and ones (maybe due to being close enough to an assignment problem?), and ones are sometimes split across the power suppliers (and sometimes not). With the binary specification instead of 0 <= R <= 1, it should also be valid CVX code. I have no idea whether your code corresponds to the problem you actually want to solve. But at this point, it is a general mathematical optimization modeling matter, and not a CVX-specifc matter, so you will need to seek any further assistance on this problem elsewhere, unless you encounter another CVX-specifc matter to be addressed.

24

Yes, though the operations provide an answer, however, it is not the results I want, those questions take me quite a while, and not yet resolved, These questions frustrated me as well, maybe this optimal model has some questions in somewhere I had not found, anyway, I will have to seek other helps on this problem I have been addressing. Unfortunately, I emailed some optimal experts around the world, they do not reply to me on this problem, for now I am getting trapped in this problem.