Can't find the optimal solution for multi-resources bin packing problem
回答済みthe element xij the matrix x represents if the item i is put in the bin j or not
xij=1 if the item i is put in the bin j ,otherwise zero.
yj in the vector y represents the bin.
yj = 1 if the bin j is used, otherwise zero.
the matrix H represents the attributes for the item
H(i,:) means the weight(s) vector of item i
H(i,j) is the corresponding weight j of the item i
we have limit 1 for every capacity of every weight.
the goal is to find the minimum number of used bin(s)
this to check the items can be put in the bin j together.
this means no item can be put in if the bin j is not used.
this means each item can only be packed into one bin.
code in Matlab:
n=2; %bus number
x = binvar(n,n);
y = binvar(n,1);
H=0.1*rand(n,n);
obj =y(1,1)+y(2,1);
con = [];
con = con + [H(1,1)*x(1,1)+H(1,2)*x(2,1) <= y(1,1)];
con = con + [H(2,1)*x(1,1)+H(2,2)*x(2,1) <= y(1,1)];
con = con + [H(1,1)*x(1,2)+H(1,2)*x(2,2) <= y(2,1)];
con = con + [H(2,1)*x(1,2)+H(2,2)*x(2,2) <= y(2,1)];
con= con + [x(1,1)<=y(1,1)];
con= con + [x(2,1)<=y(1,1)];
con= con + [x(1,2)<=y(2,1)];
con= con + [x(2,2)<=y(2,1)];
con = con +[y(2,1)<=y(1,1)];
con = con + [x(1,1)+x(1,2) == 1];
con = con + [x(2,1)+x(2,2) ==1];
% con = con + [x(1,1)>=x(1,2)]; ##
% con = con + [x(2,1)>=x(2,2)]; ##
opts = sdpsettings('solver','bnb','bnb.maxtime',120,'bnb.maxiter',300 );
optimize(con,obj,opts);
this solution is feasible but also a trivial one. It means that each item is put in each bin.
the matrix H obviously shows that two items should be put in only one bin.
For instance, the optimal solution should be x=[1 0; 1 0] or x=[0 1; 0 1] ,and the value of obj should be 1 , not 2.
two constraints with tag(##) are used to make system return the only one solution x=[1 0; 1 0] with obj =1, but the result will be:
It will give me the worst answer. I gave my best to fix this program, but still unable to make it.
I've debugged this code for lots of time, but still can't make the program right.
Can someone help me? Thanks!
-
正式なコメント
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
This constraints
con = con +[y(2,1)<=y(1,1)];
looks like it is too much. Could you try removing it?
To debug such issues, it is best to write the model file after optimization has finished.
gurobi_write(model, 'myModel.lp')
and then inspect it. The generated file allows you to analyze whether the model is formulated correctly.
Best regards,
Jaromił0 -
-
Thanks for Jaromił's reply!
I removed the additional constraint .
con = con +[y(2,1)<=y(1,1)];
I did what you said and compared the model written by gurobi with the one by yalmip.
They are the same. So I think the model by yalmip is formulated correctly.
But why I still unable to get the optimal solution?
Is it possible that x=[1 0; 1 0] or x=[0 1; 0 1] is eliminated during the process?
My idea on how gurobi solve this small sample problem is that,
we will have 16 possible matrix x, and the computer will check if the constraints are violated or not.
and record the object value for the no-violating matrix. And we will get the optimal solution with the smallest obj by comparing one by one.
Am I wrong on how gurobi works on this small sample?
I appreciate someone who reply me.
Thank you!
0 -
-
-
Could you please post the LP file you generated?
My idea on how gurobi solve this small sample problem is that,
we will have 16 possible matrix x, and the computer will check if the constraints are violated or not.
and record the object value for the no-violating matrix. And we will get the optimal solution with the smallest obj by comparing one by one.
Am I wrong on how gurobi works on this small sample?
Gurobi does not brute force all possible solutions. A nice introduction on how Gurobi works on a high level can be found here. Additionally, we list multiple resources to get a better grasp of how mathematical programming works under the hood.
0 -
-
Thank you for your reply!
I found out that I only make 6 constraint because I forgot to recover the following constraints.
I was trying to see if the constraints will affect the result. It shows that without the missed ones ,the result is still the same obj=2 and x=[1 0; 0 1] by yalmip constrution.
When I ran the following code:
con= con + [x(1,1)<=y(1,1)];
con= con + [x(2,1)<=y(1,1)];
con= con + [x(1,2)<=y(2,1)];
con= con + [x(2,2)<=y(2,1)];
con = con +[y(2,1)<=y(1,1)];After I added the missed ones,
model.A = sparse([ 0.0208 0 0.0134 0 -1 0; 0.0318 0 0.0671 0 -1 0; 0 0.0208 0 0.0134 0 -1; 0 0.0318 0 0.0671 0 -1; 1 1 0 0 0 0; 0 0 1 1 0 0; 1 0 0 0 -1 0; 0 0 1 0 -1 0; 0 1 0 0 0 -1; 0 0 0 1 0 -1 ]);
model.obj = [ 0 0 0 0 1 1 ];
model.modelsense = 'min';
model.rhs = [ 0; 0; 0; 0; 1; 1; 0; 0; 0; 0 ];
model.lb = [ 0; 0; 0; 0; 0; 0 ];
model.ub = [ 1; 1; 1; 1; 1; 1 ];
model.vtype = 'binary';
model.varnames ={'x11';'x12';'x21';'x22';'y1';'y2' };
model.constrnames = {'c1';'c2';'c3';'c4';'c5';'c6';'c7';'c8';'c9';'c10'};
model.sense = '<<<<==<<<<';
gurobi_write(model, 'mymodel.mps');
gurobi_write(model, 'mymodel.lp');
gurobi_write(model, 'mymodel.mps.bz2');an error message jumped out, and I can't fix it.
Do you have any idea what's wrong?
Thank you!
0 -
-
-
It looks like YALMIP does not directly support the native Gurobi write function. I am not a YALMIP user, thus my help here is only limited. Maybe the Knowledge Base article How do I write an MPS model file from a third-party API? will help.
0 -
-
Thanks for your help!
Best regards.
0 -
投稿コメントは受け付けていません。
コメント
7件のコメント