Skip to first unread message
李汇熙
Feb 20, 2015, 11:46:25 PM2/20/15
to yal...@googlegroups.com
Hi Johan
I use the code below to solve a very simple 01 binpacking problem.
global g_VM;
%m
global g_PM;
%n
g_VM = 20;
g_PM = 50;
vc = round(5*rand(1,g_VM))
pc = round(10*rand(1,g_PM));
for i = 1:g_PM
%if pc(i) < 5
pc(i) = pc(i)*10;
%end
end
vm = round(5*rand(1,g_VM))
pm = round(10*rand(1,g_PM));
for i = 1:g_PM
%if pm(i) < 5
pm(i) = pm(i)*10;
% end
end
pc
pm
X = binvar(g_VM, g_PM);
obj = length(find(sum(X),1)~=0));
constraints = [vc*X<=pc, vm*X<=pm, sum(X,2)==1];
optimize(constraints, obj);
value(obj)
value(X)
toc;
%m
global g_PM;
%n
g_VM = 20;
g_PM = 50;
vc = round(5*rand(1,g_VM))
pc = round(10*rand(1,g_PM));
for i = 1:g_PM
%if pc(i) < 5
pc(i) = pc(i)*10;
%end
end
vm = round(5*rand(1,g_VM))
pm = round(10*rand(1,g_PM));
for i = 1:g_PM
%if pm(i) < 5
pm(i) = pm(i)*10;
% end
end
pc
pm
X = binvar(g_VM, g_PM);
obj = length(find(sum(X),1)~=0));
constraints = [vc*X<=pc, vm*X<=pm, sum(X,2)==1];
optimize(constraints, obj);
value(obj)
value(X)
toc;
No matter how I set the value of g_PM and g_VM and ran the code, the display of value(obj) is 1, but if I modify "obj = length(find(sum(X),1)~=0));" to "obj = length(find(sum(value(X),1)~=0));", it showed the correct answer, which is strange. I don't know whether the use of value() could influence the process of solving the model.
And there are lots of 0.5000 apprear in the outcome sometimes if I set the values of g_PM and g_VM a little bit larger(yalmip wiki says that binvar is used to define decision variables constrained to be binary (0 or 1).). Plz help me to aviod this.
And there are lots of 0.5000 apprear in the outcome sometimes if I set the values of g_PM and g_VM a little bit larger(yalmip wiki says that binvar is used to define decision variables constrained to be binary (0 or 1).). Plz help me to aviod this.
Thx!
李汇熙
Feb 20, 2015, 11:58:09 PM2/20/15
to yal...@googlegroups.com
For example ,it showed:
* Starting YALMIP integer branch & bound.
* Lower solver : LINPROG
* Upper solver : rounder
* Max iterations : 300
Node Upper Gap(%) Lower Open
1 : Inf Inf 0.000E+00 2 Successfully solved
2 : Inf Inf 0.000E+00 3 Successfully solved
3 : Inf Inf 0.000E+00 4 Successfully solved
4 : Inf Inf 0.000E+00 5 Successfully solved
5 : Inf Inf 0.000E+00 6 Successfully solved
6 : Inf Inf 0.000E+00 7 Successfully solved
7 : Inf Inf 0.000E+00 8 Successfully solved
8 : Inf Inf 0.000E+00 9 Successfully solved
9 : Inf Inf 0.000E+00 10 Successfully solved
10 : Inf Inf 0.000E+00 11 Successfully solved
11 : Inf Inf 0.000E+00 12 Successfully solved
12 : Inf Inf 0.000E+00 13 Successfully solved
13 : Inf Inf 0.000E+00 14 Successfully solved
14 : Inf Inf 0.000E+00 15 Successfully solved
15 : Inf Inf 0.000E+00 16 Successfully solved
16 : Inf Inf 0.000E+00 17 Successfully solved
17 : Inf Inf 0.000E+00 18 Successfully solved
18 : Inf Inf 0.000E+00 19 Successfully solved
19 : Inf Inf 0.000E+00 20 Successfully solved
20 : Inf Inf 0.000E+00 21 Successfully solved
21 : Inf Inf 0.000E+00 22 Successfully solved
22 : Inf Inf 0.000E+00 23 Successfully solved
23 : Inf Inf 0.000E+00 24 Successfully solved
24 : Inf Inf 0.000E+00 25 Successfully solved
25 : Inf Inf 0.000E+00 26 Successfully solved
26 : Inf Inf 0.000E+00 27 Successfully solved
27 : Inf Inf 0.000E+00 28 Successfully solved
28 : Inf Inf 0.000E+00 29 Successfully solved
29 : Inf Inf 0.000E+00 30 Successfully solved
30 : Inf Inf 0.000E+00 31 Successfully solved
31 : Inf Inf 0.000E+00 32 Successfully solved
32 : Inf Inf 0.000E+00 33 Successfully solved
33 : Inf Inf 0.000E+00 34 Successfully solved
34 : Inf Inf 0.000E+00 35 Successfully solved
35 : Inf Inf 0.000E+00 36 Successfully solved
36 : Inf Inf 0.000E+00 37 Successfully solved
37 : Inf Inf 0.000E+00 38 Successfully solved
38 : Inf Inf 0.000E+00 39 Successfully solved
39 : Inf Inf 0.000E+00 40 Successfully solved
40 : Inf Inf 0.000E+00 41 Successfully solved
41 : Inf Inf 0.000E+00 42 Successfully solved
42 : Inf Inf 0.000E+00 43 Successfully solved
43 : Inf Inf 0.000E+00 44 Successfully solved
44 : Inf Inf 0.000E+00 45 Successfully solved
45 : Inf Inf 0.000E+00 46 Successfully solved
46 : Inf Inf 0.000E+00 47 Successfully solved
47 : Inf Inf 0.000E+00 48 Successfully solved
48 : Inf Inf 0.000E+00 49 Successfully solved
49 : Inf Inf 0.000E+00 50 Successfully solved
50 : Inf Inf 0.000E+00 51 Successfully solved
51 : Inf Inf 0.000E+00 52 Successfully solved
52 : Inf Inf 0.000E+00 53 Successfully solved
53 : Inf Inf 0.000E+00 54 Successfully solved
54 : Inf Inf 0.000E+00 55 Successfully solved
55 : Inf Inf 0.000E+00 56 Successfully solved
56 : Inf Inf 0.000E+00 57 Successfully solved
57 : Inf Inf 0.000E+00 58 Successfully solved
58 : Inf Inf 0.000E+00 59 Successfully solved
59 : Inf Inf 0.000E+00 60 Successfully solved
60 : Inf Inf 0.000E+00 61 Successfully solved
61 : Inf Inf 0.000E+00 62 Successfully solved
62 : Inf Inf 0.000E+00 63 Successfully solved
63 : Inf Inf 0.000E+00 64 Successfully solved
64 : Inf Inf 0.000E+00 65 Successfully solved
65 : Inf Inf 0.000E+00 66 Successfully solved
66 : Inf Inf 0.000E+00 67 Successfully solved
67 : Inf Inf 0.000E+00 68 Successfully solved
68 : Inf Inf 0.000E+00 69 Successfully solved
69 : Inf Inf 0.000E+00 70 Successfully solved
70 : Inf Inf 0.000E+00 71 Successfully solved
71 : Inf Inf 0.000E+00 72 Successfully solved
72 : Inf Inf 0.000E+00 73 Successfully solved
73 : Inf Inf 0.000E+00 74 Successfully solved
74 : Inf Inf 0.000E+00 75 Successfully solved
75 : Inf Inf 0.000E+00 76 Successfully solved
76 : Inf Inf 0.000E+00 77 Successfully solved
77 : Inf Inf 0.000E+00 78 Successfully solved
78 : Inf Inf 0.000E+00 79 Successfully solved
79 : Inf Inf 0.000E+00 80 Successfully solved
80 : Inf Inf 0.000E+00 81 Successfully solved
81 : Inf Inf 0.000E+00 82 Successfully solved
82 : Inf Inf 0.000E+00 83 Successfully solved
83 : Inf Inf 0.000E+00 84 Successfully solved
84 : Inf Inf 0.000E+00 85 Successfully solved
85 : Inf Inf 0.000E+00 86 Successfully solved
86 : Inf Inf 0.000E+00 87 Successfully solved
87 : Inf Inf 0.000E+00 88 Successfully solved
88 : Inf Inf 0.000E+00 89 Successfully solved
89 : Inf Inf 0.000E+00 90 Successfully solved
90 : Inf Inf 0.000E+00 91 Successfully solved
91 : Inf Inf 0.000E+00 92 Successfully solved
92 : Inf Inf 0.000E+00 93 Successfully solved
93 : Inf Inf 0.000E+00 94 Successfully solved
94 : Inf Inf 0.000E+00 95 Successfully solved
95 : Inf Inf 0.000E+00 96 Successfully solved
96 : Inf Inf 0.000E+00 97 Successfully solved
97 : Inf Inf 0.000E+00 98 Successfully solved
98 : Inf Inf 0.000E+00 99 Successfully solved
99 : Inf Inf 0.000E+00 100 Successfully solved
100 : Inf Inf 0.000E+00 101 Successfully solved
101 : Inf Inf 0.000E+00 102 Successfully solved
102 : Inf Inf 0.000E+00 103 Successfully solved
103 : Inf Inf 0.000E+00 104 Successfully solved
104 : Inf Inf 0.000E+00 105 Successfully solved
105 : Inf Inf 0.000E+00 106 Successfully solved
106 : Inf Inf 0.000E+00 107 Successfully solved
107 : Inf Inf 0.000E+00 108 Successfully solved
108 : Inf Inf 0.000E+00 109 Successfully solved
109 : Inf Inf 0.000E+00 110 Successfully solved
110 : Inf Inf 0.000E+00 111 Successfully solved
111 : Inf Inf 0.000E+00 112 Successfully solved
112 : Inf Inf 0.000E+00 113 Successfully solved
113 : Inf Inf 0.000E+00 114 Successfully solved
114 : Inf Inf 0.000E+00 115 Successfully solved
115 : Inf Inf 0.000E+00 116 Successfully solved
116 : Inf Inf 0.000E+00 117 Successfully solved
117 : Inf Inf 0.000E+00 118 Successfully solved
118 : Inf Inf 0.000E+00 119 Successfully solved
119 : Inf Inf 0.000E+00 120 Successfully solved
120 : Inf Inf 0.000E+00 121 Successfully solved
121 : Inf Inf 0.000E+00 122 Successfully solved
122 : Inf Inf 0.000E+00 123 Successfully solved
123 : Inf Inf 0.000E+00 124 Successfully solved
124 : Inf Inf 0.000E+00 125 Successfully solved
125 : Inf Inf 0.000E+00 126 Successfully solved
126 : Inf Inf 0.000E+00 127 Successfully solved
127 : Inf Inf 0.000E+00 128 Successfully solved
128 : Inf Inf 0.000E+00 129 Successfully solved
129 : Inf Inf 0.000E+00 130 Successfully solved
130 : Inf Inf 0.000E+00 131 Successfully solved
131 : Inf Inf 0.000E+00 132 Successfully solved
132 : Inf Inf 0.000E+00 133 Successfully solved
133 : Inf Inf 0.000E+00 134 Successfully solved
134 : Inf Inf 0.000E+00 135 Successfully solved
135 : Inf Inf 0.000E+00 136 Successfully solved
136 : Inf Inf 0.000E+00 137 Successfully solved
137 : Inf Inf 0.000E+00 138 Successfully solved
138 : Inf Inf 0.000E+00 139 Successfully solved
139 : Inf Inf 0.000E+00 140 Successfully solved
140 : Inf Inf 0.000E+00 141 Successfully solved
141 : Inf Inf 0.000E+00 142 Successfully solved
142 : Inf Inf 0.000E+00 143 Successfully solved
143 : Inf Inf 0.000E+00 144 Successfully solved
144 : Inf Inf 0.000E+00 145 Successfully solved
145 : Inf Inf 0.000E+00 146 Successfully solved
146 : Inf Inf 0.000E+00 147 Successfully solved
147 : Inf Inf 0.000E+00 148 Successfully solved
148 : Inf Inf 0.000E+00 149 Successfully solved
149 : Inf Inf 0.000E+00 150 Successfully solved
150 : Inf Inf 0.000E+00 151 Successfully solved
151 : Inf Inf 0.000E+00 152 Successfully solved
152 : Inf Inf 0.000E+00 153 Successfully solved
153 : Inf Inf 0.000E+00 154 Successfully solved
154 : Inf Inf 0.000E+00 155 Successfully solved
155 : Inf Inf 0.000E+00 156 Successfully solved
156 : Inf Inf 0.000E+00 157 Successfully solved
157 : Inf Inf 0.000E+00 158 Successfully solved
158 : Inf Inf 0.000E+00 159 Successfully solved
159 : Inf Inf 0.000E+00 160 Successfully solved
160 : Inf Inf 0.000E+00 161 Successfully solved
161 : Inf Inf 0.000E+00 162 Successfully solved
162 : Inf Inf 0.000E+00 163 Successfully solved
163 : Inf Inf 0.000E+00 164 Successfully solved
164 : Inf Inf 0.000E+00 165 Successfully solved
165 : Inf Inf 0.000E+00 166 Successfully solved
166 : Inf Inf 0.000E+00 167 Successfully solved
167 : Inf Inf 0.000E+00 168 Successfully solved
168 : Inf Inf 0.000E+00 169 Successfully solved
169 : Inf Inf 0.000E+00 170 Successfully solved
170 : Inf Inf 0.000E+00 171 Successfully solved
171 : Inf Inf 0.000E+00 172 Successfully solved
172 : Inf Inf 0.000E+00 173 Successfully solved
173 : Inf Inf 0.000E+00 174 Successfully solved
174 : Inf Inf 0.000E+00 175 Successfully solved
175 : Inf Inf 0.000E+00 176 Successfully solved
176 : Inf Inf 0.000E+00 177 Successfully solved
177 : Inf Inf 0.000E+00 178 Successfully solved
178 : Inf Inf 0.000E+00 179 Successfully solved
179 : Inf Inf 0.000E+00 180 Successfully solved
180 : Inf Inf 0.000E+00 181 Successfully solved
181 : Inf Inf 0.000E+00 182 Successfully solved
182 : Inf Inf 0.000E+00 183 Successfully solved
183 : Inf Inf 0.000E+00 184 Successfully solved
184 : Inf Inf 0.000E+00 185 Successfully solved
185 : Inf Inf 0.000E+00 186 Successfully solved
186 : Inf Inf 0.000E+00 187 Successfully solved
187 : Inf Inf 0.000E+00 188 Successfully solved
188 : Inf Inf 0.000E+00 189 Successfully solved
189 : Inf Inf 0.000E+00 190 Successfully solved
190 : Inf Inf 0.000E+00 191 Successfully solved
191 : Inf Inf 0.000E+00 192 Successfully solved
192 : Inf Inf 0.000E+00 193 Successfully solved
193 : Inf Inf 0.000E+00 194 Successfully solved
194 : Inf Inf 0.000E+00 195 Successfully solved
195 : Inf Inf 0.000E+00 196 Successfully solved
196 : Inf Inf 0.000E+00 197 Successfully solved
197 : Inf Inf 0.000E+00 198 Successfully solved
198 : Inf Inf 0.000E+00 199 Successfully solved
199 : Inf Inf 0.000E+00 200 Successfully solved
200 : Inf Inf 0.000E+00 201 Successfully solved
201 : Inf Inf 0.000E+00 202 Successfully solved
202 : Inf Inf 0.000E+00 203 Successfully solved
203 : Inf Inf 0.000E+00 204 Successfully solved
204 : Inf Inf 0.000E+00 205 Successfully solved
205 : Inf Inf 0.000E+00 206 Successfully solved
206 : Inf Inf 0.000E+00 207 Successfully solved
207 : Inf Inf 0.000E+00 208 Successfully solved
208 : Inf Inf 0.000E+00 209 Successfully solved
209 : Inf Inf 0.000E+00 210 Successfully solved
210 : Inf Inf 0.000E+00 211 Successfully solved
211 : Inf Inf 0.000E+00 212 Successfully solved
212 : Inf Inf 0.000E+00 213 Successfully solved
213 : Inf Inf 0.000E+00 214 Successfully solved
214 : Inf Inf 0.000E+00 215 Successfully solved
215 : Inf Inf 0.000E+00 216 Successfully solved
216 : Inf Inf 0.000E+00 217 Successfully solved
217 : Inf Inf 0.000E+00 218 Successfully solved
218 : Inf Inf 0.000E+00 219 Successfully solved
219 : Inf Inf 0.000E+00 220 Successfully solved
220 : Inf Inf 0.000E+00 221 Successfully solved
221 : Inf Inf 0.000E+00 222 Successfully solved
222 : Inf Inf 0.000E+00 223 Successfully solved
223 : Inf Inf 0.000E+00 224 Successfully solved
224 : Inf Inf 0.000E+00 225 Successfully solved
225 : Inf Inf 0.000E+00 226 Successfully solved
226 : Inf Inf 0.000E+00 227 Successfully solved
227 : Inf Inf 0.000E+00 228 Successfully solved
228 : Inf Inf 0.000E+00 229 Successfully solved
229 : Inf Inf 0.000E+00 230 Successfully solved
230 : Inf Inf 0.000E+00 231 Successfully solved
231 : Inf Inf 0.000E+00 232 Successfully solved
232 : Inf Inf 0.000E+00 233 Successfully solved
233 : Inf Inf 0.000E+00 234 Successfully solved
234 : Inf Inf 0.000E+00 235 Successfully solved
235 : Inf Inf 0.000E+00 236 Successfully solved
236 : Inf Inf 0.000E+00 237 Successfully solved
237 : Inf Inf 0.000E+00 238 Successfully solved
238 : Inf Inf 0.000E+00 239 Successfully solved
239 : Inf Inf 0.000E+00 240 Successfully solved
240 : Inf Inf 0.000E+00 241 Successfully solved
241 : Inf Inf 0.000E+00 242 Successfully solved
242 : Inf Inf 0.000E+00 243 Successfully solved
243 : Inf Inf 0.000E+00 244 Successfully solved
244 : Inf Inf 0.000E+00 245 Successfully solved
245 : Inf Inf 0.000E+00 246 Successfully solved
246 : Inf Inf 0.000E+00 247 Successfully solved
247 : Inf Inf 0.000E+00 248 Successfully solved
248 : Inf Inf 0.000E+00 249 Successfully solved
249 : Inf Inf 0.000E+00 250 Successfully solved
250 : Inf Inf 0.000E+00 251 Successfully solved
251 : Inf Inf 0.000E+00 252 Successfully solved
252 : Inf Inf 0.000E+00 253 Successfully solved
253 : Inf Inf 0.000E+00 254 Successfully solved
254 : Inf Inf 0.000E+00 255 Successfully solved
255 : Inf Inf 0.000E+00 256 Successfully solved
256 : Inf Inf 0.000E+00 257 Successfully solved
257 : Inf Inf 0.000E+00 258 Successfully solved
258 : Inf Inf 0.000E+00 259 Successfully solved
259 : Inf Inf 0.000E+00 260 Successfully solved
260 : Inf Inf 0.000E+00 261 Successfully solved
261 : Inf Inf 0.000E+00 262 Successfully solved
262 : Inf Inf 0.000E+00 263 Successfully solved
263 : Inf Inf 0.000E+00 264 Successfully solved
264 : Inf Inf 0.000E+00 265 Successfully solved
265 : Inf Inf 0.000E+00 266 Successfully solved
266 : Inf Inf 0.000E+00 267 Successfully solved
267 : Inf Inf 0.000E+00 268 Successfully solved
268 : Inf Inf 0.000E+00 269 Successfully solved
269 : Inf Inf 0.000E+00 270 Successfully solved
270 : Inf Inf 0.000E+00 271 Successfully solved
271 : Inf Inf 0.000E+00 272 Successfully solved
272 : Inf Inf 0.000E+00 273 Successfully solved
273 : Inf Inf 0.000E+00 274 Successfully solved
274 : Inf Inf 0.000E+00 275 Successfully solved
275 : Inf Inf 0.000E+00 276 Successfully solved
276 : Inf Inf 0.000E+00 277 Successfully solved
277 : Inf Inf 0.000E+00 278 Successfully solved
278 : Inf Inf 0.000E+00 279 Successfully solved
279 : Inf Inf 0.000E+00 280 Successfully solved
280 : Inf Inf 0.000E+00 281 Successfully solved
281 : Inf Inf 0.000E+00 282 Successfully solved
282 : Inf Inf 0.000E+00 283 Successfully solved
283 : Inf Inf 0.000E+00 284 Successfully solved
284 : Inf Inf 0.000E+00 285 Successfully solved
285 : Inf Inf 0.000E+00 286 Successfully solved
286 : Inf Inf 0.000E+00 287 Successfully solved
287 : Inf Inf 0.000E+00 288 Successfully solved
288 : Inf Inf 0.000E+00 289 Successfully solved
289 : Inf Inf 0.000E+00 290 Successfully solved
290 : Inf Inf 0.000E+00 291 Successfully solved
291 : Inf Inf 0.000E+00 292 Successfully solved
292 : Inf Inf 0.000E+00 293 Successfully solved
293 : Inf Inf 0.000E+00 294 Successfully solved
294 : Inf Inf 0.000E+00 295 Successfully solved
295 : Inf Inf 0.000E+00 296 Successfully solved
296 : Inf Inf 0.000E+00 297 Successfully solved
297 : Inf Inf 0.000E+00 298 Successfully solved
298 : Inf Inf 0.000E+00 299 Successfully solved
299 : Inf Inf 0.000E+00 300 Successfully solved
300 : Inf Inf 0.000E+00 301 Successfully solved
+ 300 Finishing. Cost: Inf
ans =
1
ans =
Columns 1 through 10
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
Columns 11 through 20
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
Columns 21 through 30
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
0 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000 0.5000
Elapsed time is 0.018847 seconds.
Johan Löfberg
Feb 21, 2015, 3:16:20 AM2/21/15
to
You have to install a MILP solver (mosek, gurobi, ...)
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.Solvers
As you don't have any MILP solver installed, YALMIP uses its internal bnb framework. To make matters worse, you don't have any good LP solver either, so the bnb solver gets crap from the LP relaxations and doesn't even manage to find a feasible solution before it terminates (look at the error code, maximum iterations met, and the display says cost is infinite, i.e., no feasible solution found yet)
A real MILP solver solves the problem in the root node in 0 seconds.
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Solvers.Solvers
As you don't have any MILP solver installed, YALMIP uses its internal bnb framework. To make matters worse, you don't have any good LP solver either, so the bnb solver gets crap from the LP relaxations and doesn't even manage to find a feasible solution before it terminates (look at the error code, maximum iterations met, and the display says cost is infinite, i.e., no feasible solution found yet)
A real MILP solver solves the problem in the root node in 0 seconds.
Mark L. Stone
Feb 21, 2015, 7:51:22 AM2/21/15
to yal...@googlegroups.com
Hmm, the Mathworks sells an extra cost Optimization Toolbox whose LP solver, LINPROG, is a piece of junk. The reason why is apparently one of those unsolved mysteries of the universe.
李汇熙
Feb 21, 2015, 8:43:06 PM2/21/15
to yal...@googlegroups.com
so is the solver also the major reason of the difference of X and value(X)?
Johan Löfberg
Feb 22, 2015, 3:18:27 AM2/22/15
to yal...@googlegroups.com
That question makes no sense. X is a symbolic decision variable, value(X) is a numerical value.
李汇熙
Feb 27, 2015, 4:37:03 AM2/27/15
to yal...@googlegroups.com
Hi Johan
I'm using Gurobi now and all 0.5 are gone.
But I still have problems with describing the objective and constraints of 01 bin-packing model in Yalmip.
The figure below is a standard bin-packing model( from wikipedia)
I use two binvars X and Y to define the decision variables respectively.
objective = sum(Y).
How can I write the constraints, especially the 1st line of S.T.?
I've tried some ways, but the answer of Y is full of zeros and there is 1 in every column of X, which is unreasonable.
It would be very thankful if you give me an example of this.
Johan Löfberg
Feb 27, 2015, 5:14:18 AM2/27/15
to yal...@googlegroups.com
Just standard matlab. You can trivially vectorize it
assuming a and y are column vectors
X*a <= V*y
assuming a and y are column vectors
Johan Löfberg
Feb 27, 2015, 5:29:53 AM2/27/15
to yal...@googlegroups.com
Note that a square matrix is symmetric by default. Most likely you do not want that.
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics
http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Basics
李汇熙
Feb 27, 2015, 6:33:39 AM2/27/15
to yal...@googlegroups.com
Hi
it still dose not work well. I've tried many methods and source data.
In terms of the dataset I give in the attachment, value(X) is a zero matrix. And sometimes it is a diagonal matrix for other dataset, which means all bins are occupied.
Plz help me to fix it. It has been confusing me for a while.
Johan Löfberg
Feb 27, 2015, 6:41:04 AM2/27/15
to yal...@googlegroups.com
The problem trivially infeasible. Have you not looked at the display and diagnostics? In several elements of pc you have a zero, hence it is obviously impossible as vc is positive and every row of X has non-zero elements
Optimize a model with 200 rows, 5050 columns and 20000 nonzeros
Coefficient statistics:
Matrix range [1e+00, 3e+01]
Objective range [0e+00, 0e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+02]
Presolve removed 0 rows and 3655 columns
Presolve time: 0.00s
ans =
yalmiptime: 0.1364
solvertime: 0.0366
info: 'Infeasible problem (GUROBI-GUROBI)'
Explored 0 nodes (0 simplex iterations) in 0.03 seconds
Thread count was 1 (of 4 available processors)
Model is infeasible
Best objective -, best bound -, gap -
Optimize a model with 200 rows, 5050 columns and 20000 nonzeros
Coefficient statistics:
Matrix range [1e+00, 3e+01]
Objective range [0e+00, 0e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+02]
Presolve removed 0 rows and 3655 columns
Presolve time: 0.00s
ans =
yalmiptime: 0.1364
solvertime: 0.0366
info: 'Infeasible problem (GUROBI-GUROBI)'
Explored 0 nodes (0 simplex iterations) in 0.03 seconds
Thread count was 1 (of 4 available processors)
Model is infeasible
Best objective -, best bound -, gap -
Johan Löfberg
Feb 27, 2015, 6:42:58 AM2/27/15
to yal...@googlegroups.com
and as I said, you are forcing X to be symmetric as it is square
Johan Löfberg
Feb 27, 2015, 6:46:04 AM2/27/15
to
sorry, now I saw you summed with vc over columns, so then you can have zero columns (as the at-least-one condition is in the rows)
your problem the fact that you have enforced X to be symmetric, which will force each column to sum to 1 too, which then trivially is infeasible according to previous discussion
your problem the fact that you have enforced X to be symmetric, which will force each column to sum to 1 too, which then trivially is infeasible according to previous discussion
Johan Löfberg
Feb 27, 2015, 7:24:23 AM2/27/15
to yal...@googlegroups.com
Make things comparable by creating a matrix in greedy_pack which can be directly compared with the optimal solution X computed using MILP. As you do it now with completely different structures, it is impossible for anyone but you to understand what the different things are
You should still update your code to ensure X isn't structurally symmetric (in this dataset you are saved as the matrix is not square, but why not write robust code...)
You should still update your code to ensure X isn't structurally symmetric (in this dataset you are saved as the matrix is not square, but why not write robust code...)
Johan Löfberg
Feb 27, 2015, 7:30:01 AM2/27/15
to yal...@googlegroups.com
and note that you cannot use find(/X) as a symbolic expression. find(X) on a decision variable X gives nonzero elements in the basis of X, something you most likely is completely uninteerested in (i.e, it is a fixed number, equal to
X = binvar(g_vm*4, g_pm);
length(find(sum(X))~=0)
ans =
110Johan Löfberg
Feb 27, 2015, 7:36:16 AM2/27/15
to
appears your objective is the number of non-zero columns
constraints = [vc*X<=pc, vm*X<=pm, sum(X,2)==1,];
Z = binvar(1,g_pm);
optimize([constraints,sum(X,1) <= g_pm*Z],sum(Z));
Reply all
Reply to author
Forward
0 new messages