Any body can give some suggestions about whether or not the cvx can solve the discrete combinatorial optimization, like 0-1 problem.
Thanks so much!
There is support for mixed integer DCP’s in CVX, presuming you have a solver which supports that. You can declare variables to be binary or integer. Read the CVX Users’ Guide http://web.cvxr.com/cvx/doc/ .
Thanks so much!
Let me try!
the supported solvers installed in my machine support only SDPT3 and SeDuMi solver, UNFORTUNATELY, they both DO NOT support mixed integer DCP’s in CVX, but Gurobi, MOSEK require CVX professional license I do not have for now in spite of they both support mixed integer. Basically, the 0-1 discrete optimization is the combinatorial optimization with an exhaustive search space such as a branch-and-bound algorithm, which is typically NP-hard question. So any other idea to handle this difficulty.
Thanks so much!
Riheng
You can may be able to use GLPK, but I will defer to @mcg on that . See section 8.1 http://web.cvxr.com/cvx/doc/solver.html of the CVX Users’ Guide.
Note, per that secton 8.1 :Support for GLPK should be considered experimental, and has been provided primarly to support upcoming Octave capability (that is not ready yet.)
I downloaded the MOSEK solver and install it in my machine,
however, when I run the programs again, it gives the following errors:
"Error using subsindex
Function ‘subsindex’ is not defined for values of class ‘cvx’ ", and I attached the codes as follows
cvx_begin
variable R(10) integer
minimize(sum(vec(lambda_jk(R,:)).*x(:)))
subject to
R(N)＜=ones(N,1)
r(n)＞=2.*ones(N,1)
cvx_end
Thanks!
You haven’t provided reproducible code. For instance, I don’t even know what lambda_jk is. Nevertheless, you can not use a CVX variable, such as R, to index into an array. I believe that is the cause of that error message.
Also, I am not sure what you intend your constraints to be, but those don’t look correct. You haven’t even declared r as a CVX variable, what is N vs. n, and if it is meant to be R and N = n, then the constraints are inconsistent. And you want the right hand side to be of the same dimension as the left hand side, unless it is something like c*ones(N,1), in which case you can just use c as the right hand side.
I think you need to read through the CVX Users’ Guide to learn the basics of using CVX.
I think you are right for the first guess, I believe so as well! the lambda_jk is a matrix indexed by R that is used to match the corresponding vector in x, however, I have no idea on how to express my intent via CVX if such express wouldn’t be employed.
R is the integer vector variables to be optimized, sorry, N=10, the constraint conditions denote that R(N) is either 1 or 2 in an element-wise fashion, forth hence, this is essentially a combinatorial optimization problem, I am sorry, the second constraint condition is my fault, it is supposed to be R(N) ＞=2.*ones(N,1), but this error remains!
I wish to constrain R on an elementwise basis, so I express them R(N) ＞=1.*ones(N,1), R(N) <=2.*ones(N,1) , and according to what you said, Do I need to describe them as R(N) ＞=1. and R(N) <=2?
Thanks so much!
You wrote the R(N) ＞=2.*ones(N,1) in the opposite direction of what you intended. Also R(N) is constraining just the N’rh component of R, which is not what you want, and has mismatched dimension to ones(N,1). Your R(N)＜=ones(N,1) has analogous errors.
1 <= R <= 2
will do what you want.
1*ones(N,1) <= R <= 2*ones(N,1)
would also work. Those errors are easy to fix, as I just showed.
I don’t know what your objective function is supposed to be. If you clearly specify mathematically the problem you are trying to solve, perhaps we can determine whether there is a way of expressing it which CVX will accept.
sorry for the error!
the original codes as follows
cvx_begin
variable R(N) integer
minimize(sum(vec(lambda_jk(R,:)).*x(:)))
subject to
R(N)>=ones(N,1)
R(N)<=2.*ones(N,1)
cvx_end
The combinatorial optimal problem I describe is that N is the number of users, they attempt to select M factories buy power, M<N, is the power suppliers, and x, N by 1, denotes power consumption, lambda_jk represents the power price sent by power suppliers, the problem is on how to find the power supplier for each user to minimize the power cost.
So the problem is how I can index the discrete integer R used in the lambda_jk, I cannot figure out the right way to show my intent.
Thank you so much!
Forget about CVX for the moment. Can you write your optimization problem mathematically, very clearly stating what the input data is and what the optimization (i.e., decision) variables are, and the dimensions of all data and variables? How does R being restricted to 1 or 2 come into play?
the input is lambda_jk, x and R is the optimization variable, in my example, assuming R is integer vector, each element stands for the user selection from one of power supplier, lambda_jk is power price and x is the user power consumption, the value of lambda_jk vary with R, but x is fixed, so the object function is to minimize the product, i.e., sum(vec(lambda_jk(R,:)).*x(:)) here, in my instance, N=10, and M=2, provided that N user select the M power suppliers, and what kind of combination is the best one in the view of object function.
Thanks so lot!
Where are your constraints? Otherwise, why don’t all users just use the lowest price supplier?
You still need to formulate a clearly specified mathematical optimization problem.
Like you said, the constraint condition is 1<=R<=2, because we have only M=2 power suppliers that have to be selected by N=10 users, each power supplier has individual power upper bound, therefore, it is impossible for all users to select the same power supplier simultaneously, the optimization problem goal is to keep balance between power price transmitted by power suppliers and the grid stability, basically, this optimization problem is a sub-problem of big problem, so some other users have to select the other power supplier with respect to the minimization of object function.
In this optimization problem, the N by 1 variable R is like integer selector, lambda_jk is just like M by 1 vector, but the index of lambda_jk is determined by R, i.e., N=10, M=2, the value of R is restricted either 1 or 2, so the question is how to find a mapping method to map R to the index of lambda_jk, maybe this needs some tricks.
The new code snippet is attached, but the error message is the same
cvx_begin
variable R(N) integer
for i=1:N
tmp_lambda_j(i,:)=lambda_jk(R(i),:);
end
minimize(sum(vec(tmp_lambda_j(:)).*x(:)))
subject to
1<=R<=2;
cvx_end
This is getting to be out of scope in this forum, but I’ll sketch how I think you can handle this problem.
First of all, I am assuming that for a given customer, all the power to be supplied must be from a single plant. If that is not true, then I don’t think binary (or integer) variables are required at all, and it would just be a standard Transportation problem (transport supply at power plants to demand at customers).
The following are inputs:
Let M = number of power plants.
Let N = number of customers.
Let d = 1 by N vector of power demand (number of KW-hours) per customer
Then D = repmat(d,M,1) is M by N matrix with each row being d
Let S = M by 1 vector of supply (KW-hours) per plant
Let p = M by 1 vector of prices (per KW-hour)
Then P = repmat(p,1,N) is M by N matrix with each column being p
Declare Q as an M by N binary CVX variable.
Interpretation is that Q(i,j) = 1 if customer j is supplied by plant i, and 0 otherwise.
Cost = sum(sum(Q.*(D.*P))) which you minimize (extraneous parentheses included for readability)
Constraints are
sum(Q,1) == 1 which forces exactly one plant be used per customer to meet demand
sum(Q.*D,2) <= S which ensures that available supply is not exceeded for any plant
So, presuming M,N,d,S,p are already available and of correct dimensions:
D = repmat(d,M,1);
P = repmat(p,1,N);
cvx_begin
variable Q(M,N) binary
minimize(sum(sum(Q.*(D.*P))))
sum(Q,1) == 1
sum(Q.*D,2) <= S
cvx_end
I haven’t checked or tried this out, so I am not providing a guarantee.
Thanks for your hard work, your assumption is correct.
Basically, the optimization problem is more complex than we image, the customers are using electricity hour by hour, and the price of electricity varies with hour in 24 hours, in this example, we divide the entire hours into 24 time interval (i.e., K=24), and one price per hour, so the dimensions are three, one has to pick up the optimal Q throughout the entire K. I don’t insure how to write the for loop in the CVX.
For loops can be used in CVX. See the CVX User’s Guide. However, if you want fast running code, it is better to avoid them where possible, for example by using sum instead of a for loop.
I don’t see why formulating the problem with 24 hour long periods should cause any difficulty, other than if it is a large problem, it may require a lot of run time and/or memory.
I am trying to solve the other problem I mentioned in the post, I defined the Q with the size of M by N by K binary CVX variable, K is the time interval, say 24. This 3D matrix is constrained with the condition that all M by N matrix is the same, i.e, K M by N matrix has the same structure, how to do that in the subject to command line?
By the way, the test code indicated that the Q is always inclined to all one in certain line in Q after optimization, I suspect something is wrong or lacking of more constraint condition, is the guess correct?
Thanks!