Debian Codegraph @

SYMPHONY/src/CutGen/Decomp/decomp.c

raw
1 #include <memory.h>
2 #include <string.h>
3
4 #include "decomp.h"
5 #include "sym_timemeas.h"
6 #include "sym_messages.h"
7 #include "decomp_types.h"
8 #include "sym_proccomm.h"
9 #include "decomp_sym_lp.h"
10 #include "sym_constants.h"
11 #include "sym_macros.h"
12
13 #define FARKAS 3
14
15 int decomp(cg_prob *p)
16 {
17 LPdata *lp_data = p->dcmp_data.lp_data;
18 decomp_data *dcmp_data = &p->dcmp_data;
19 int new_cols = -1, i, j, termcode;
20 char set_rhs, has_all_cols = FALSE;
21 int cpx_status, violation;
22 cut_data *new_cut;
23 double *binvrow;
24
25 set_rhs = user_set_rhs(lp_data->m-1, lp_data->rhs, p->cur_sol.xlength,
26 p->cur_sol.xind, p->cur_sol.xval, p->user);
27
28 if (!set_rhs){
29 for (i = 0, j = 0; i < lp_data->m - 1; i++){
30 if (j < p->cur_sol.xlength && p->cur_sol.xind[j] == i)
31 lp_data->rhs[i] = p->cur_sol.xval[j++];
32 else
33 lp_data->rhs[i] = 0;
34 }
35 }
36 lp_data->rhs[lp_data->m-1] = 1;
37
38 dcmp_data->dunbr = 0;
39 dcmp_data->iter_num = 0;
40
41 if (!(new_cols = create_initial_lp(p))){
42 unload_decomp_lp(p->dcmp_data.lp_data);
43 user_free_decomp_data_structures(p, &p->user);
44 printf("Performed 0 iterations in decomp\n");
45 return(0);
46 }
47
48 while (TRUE){
49 dcmp_data->iter_num++;
50
51 /* solve the current lp*/
52 /*Again, this is some LP-solver dependent stuff*/
53 termcode = CPXdualopt(lp_data->cpxenv, lp_data->lp);
54
55 switch (CPXgetstat(lp_data->cpxenv,lp_data->lp)){
56 case CPX_OPTIMAL: termcode = OPTIMAL; break;
57 case CPX_INFEASIBLE: termcode = D_INFEASIBLE; break;
58 case CPX_UNBOUNDED: termcode = D_UNBOUNDED; break;
59 case CPX_OBJ_LIM: termcode = D_OBJLIM; break;
60 case CPX_IT_LIM_FEAS:
61 case CPX_IT_LIM_INFEAS: termcode = D_ITLIM; break;
62 default: termcode = ABANDONED; break;
63 }
64
65 if (termcode == OPTIMAL || p->par.decomp_complete_enum){
66 if (termcode == D_UNBOUNDED)
67 has_all_cols = TRUE;
68 /*if (termcode != OPTIMAL){
69 if (termcode != D_UNBOUNDED)
70 printf("######## CutGen: Unexpected exit status %i########\n\n",
71 termcode);
72 else if (new_cols < p->par.decomp_max_col_num_per_iter)
73 has_all_cols = TRUE;
74 }*/
75 break;
76 }
77
78 violation = get_proof_of_infeas(lp_data, &dcmp_data->dunbr);
79
80 get_cols_from_pool(p, p->sol_pool);
81
82 new_cols = generate_new_cols(p);
83
84 if (termcode != D_UNBOUNDED)
85 printf("######## CutGen: Unexpected exit status %i########\n\n",
86 termcode);
87
88 if (dcmp_data->iter_num%p->par.decomp_sol_pool_check_freq == 0 &&
89 p->sol_pool)
90 new_cols += receive_cols(p);
91
92 if (new_cols == 0){
93 /*This assumes an exact column generator*/
94 has_all_cols = TRUE;
95 break;
96 }
97 }
98
99 printf("There are %i columns in the decomp LP at termination\n",
100 lp_data->n);
101 if(termcode == OPTIMAL){
102 new_cols = generate_cuts(p);
103 unload_decomp_lp(p->dcmp_data.lp_data);
104 user_free_decomp_data_structures(p, &p->user);
105 printf("Decomp imposed %i new constraints\n", new_cols);
106 return(new_cols);
107 }
108 else{
109 if (has_all_cols){
110 binvrow = (double *) malloc(lp_data->m*DSIZE);
111 lp_data->slacks = (double *) malloc(lp_data->m*DSIZE);
112 cpx_status = CPXgetslack(lp_data->cpxenv, lp_data->lp,
113 lp_data->slacks, 0, lp_data->m-1);
114 CPX_check_error("get_slacks");
115 violation = get_proof_of_infeas(lp_data, &dcmp_data->dunbr);
116 new_cut = (cut_data *) calloc (1, sizeof(cut_data));
117 cpx_status = CPXgetpi(lp_data->cpxenv, lp_data->lp, binvrow,
118 0, lp_data->m-1);
119 CPX_check_error("get_dualsol");
120 get_binvrow(lp_data, dcmp_data->dunbr, binvrow);
121 new_cut->type = FARKAS;
122 new_cut->rhs = -binvrow[lp_data->m-1];
123 new_cut->size = (lp_data->m-1)*DSIZE;
124 new_cut->coef = (char *)malloc((lp_data->m-1)*DSIZE);
125 memcpy(new_cut->coef, binvrow, (lp_data->m-1)*DSIZE);
126 cg_send_cut(new_cut);
127 free ((char *)new_cut->coef);
128 FREE(new_cut);
129 printf("New Farkas cut added\n");
130 }
131 unload_decomp_lp(p->dcmp_data.lp_data);
132 user_free_decomp_data_structures(p, &p->user);
133 return(0);
134 }
135 }
136
137 /*****************************************************************************/
138 /*****************************************************************************/
139
140 int create_initial_lp(cg_prob *p)
141 {
142 dcmp_col_set *cols;
143 LPdata *lp_data = p->dcmp_data.lp_data;
144 col_data *packed_col = (col_data *) calloc (1, sizeof(col_data));
145 int i, j, k, col_count, nzcnt, info, s_bufid, col_nzcnt;
146 double etol = p->cur_sol.lpetol;
147 char add_col;
148
149 get_cols_from_pool(p, p->sol_pool);
150 cols = user_generate_new_cols(p);
151
152 /*This is to allow some elements to be added in twice (i.e. the depot edges
153 in the VRP*/
154 memset(lp_data->matval, 0, (cols->nzcnt+cols->num_cols)*sizeof(double));
155
156 for (i = 0, nzcnt = 0, col_count = 0; i < cols->num_cols; i++){
157 for (j = cols->matbeg[i], k = 0, col_nzcnt = 0, add_col = TRUE;
158 j<cols->matbeg[i+1] && k < lp_data->m-1; k++){
159 /*This check is currently screwing things up but it should be added
160 back in in some other form at some point since it does limit the
161 number of columns in the LP*/
162 /*if (lp_data->rhs[k] < etol){
163 if (cols->matind[j] == k)
164 break;
165 else
166 continue;
167 }
168 if (lp_data->rhs[k] > 1-etol && cols->matind[j] != k)
169 break;*/
170 if (cols->matind[j] == k){
171 if (lp_data->rhs[k] < etol){
172 nzcnt -= col_nzcnt;
173 add_col = FALSE;
174 break;
175 }
176 /*while (j<cols->matbeg[i+1]){
177 if (!(cols->matind[j] == k)) break;
178 lp_data->matval[nzcnt] += 1;
179 lp_data->matind[nzcnt++] = cols->matind[j++];
180 col_nzcnt++;
181 }*/
182 lp_data->matind[nzcnt] = k;
183 while (j<cols->matbeg[i+1]){
184 if (!(cols->matind[j] == k)) break;
185 lp_data->matval[nzcnt] += 1;
186 j++;
187 }
188 nzcnt++;
189 col_nzcnt++;
190 }
191 }
192 if (!add_col){
193 add_col = TRUE;
194 continue;
195 }
196
197 lp_data->matind[nzcnt] = lp_data->m-1;
198 lp_data->matval[nzcnt++] = 1;
199 lp_data->lb[col_count] = 0;
200 lp_data->ub[col_count++] = 1;
201 lp_data->matbeg[col_count] = nzcnt;
202
203 if (p->sol_pool){
204 user_pack_col(cols->matind+cols->matbeg[i],
205 cols->matbeg[i+1]-cols->matbeg[i], packed_col);
206
207 if ((s_bufid = pvm_initsend(PvmDataRaw)) < 0) PVM_ERROR(s_bufid);
208 if ((info = pvm_pkint(&packed_col->size, 1, 1)) < 0) PVM_ERROR(info);
209 if ((info = pvm_pkint(&p->cur_sol.xlevel, 1, 1)) < 0) PVM_ERROR(info);
210 if ((info = pvm_pkbyte(packed_col->coef, packed_col->size, 1)) < 0)
211 PVM_ERROR(info);
212 if ((info = pvm_send(p->sol_pool, PACKED_COL)) < 0) PVM_ERROR(info);
213 if ((info = pvm_freebuf(s_bufid)) < 0) PVM_ERROR(info);
214 }
215
216 FREE(packed_col->coef);
217
218 if (col_count > p->par.decomp_max_col_num_per_iter) break;
219 }
220
221 lp_data->n = col_count;
222 lp_data->nz = nzcnt;
223
224 if (p->sol_pool && col_count < p->par.decomp_max_col_num_per_iter)
225 receive_cols(p);
226
227 free_dcmp_col_set(cols);
228 FREE(cols);
229 FREE(packed_col);
230
231 if (!lp_data->n)
232 return(0);
233
234 load_decomp_lp(lp_data);
235
236 p->dcmp_data.iter_num = 0;
237
238 return(lp_data->n);
239 }
240
241 /*===========================================================================*
242 * This function receives the cols to be added to the problem and adds them.
243 * First it stores all the cols to be added in the "cols" structure as a col
244 * ordered sparse matrix. Then adds them all at once.
245 *===========================================================================*/
246
247 int receive_cols(cg_prob *p)
248 {
249 int num_cols = 0, r_bufid, bytes, msgtag, sender;
250 dcmp_col_set cols;
251 int varnum = p->dcmp_data.lp_data->m;
252 int sol_id[2];
253 char block = TRUE;
254 static struct timeval tout = {15, 0};
255
256 /*------------------------------------------------------------------------*
257 * set up the data structure to store the cols so that they can all be
258 * added at once instead of one at a time -- this more efficient
259 *------------------------------------------------------------------------*/
260 cols.lb = (double *) calloc (COL_BLOCK_SIZE, sizeof(double));
261 cols.ub = (double *) calloc (COL_BLOCK_SIZE, sizeof(double));
262 cols.matbeg = (int *) calloc (COL_BLOCK_SIZE+1, sizeof(int));
263 cols.matind = (int *) calloc (varnum*COL_BLOCK_SIZE, sizeof(int));
264 cols.matval = (double *) calloc (varnum*COL_BLOCK_SIZE, sizeof(double));
265 cols.obj = (double *) calloc (COL_BLOCK_SIZE, sizeof(double));
266 cols.num_cols = 0;
267 cols.max_cols = COL_BLOCK_SIZE;
268 cols.nzcnt = 0;
269 cols.max_nzcnt = varnum*COL_BLOCK_SIZE;
270
271 /*------------------------------------------------------------------------*
272 * if "wait_for_cols" is set, then the we wait for all the cols associated
273 * with the current LP solution to come back before we return. Normally,
274 * we simply receive all the cols currently in the buffer and then return.
275 *------------------------------------------------------------------------*/
276
277 if (p->par.decomp_wait_for_cols){
278 while(TRUE){
279 do{
280 PVM_FUNC(r_bufid, pvm_trecv(ANYONE, ANYTHING, &tout));
281 if (! r_bufid){
282 if (pvm_pstat(p->tree_manager) != PvmOk){
283 printf("TM has died -- decomp exiting\n\n");
284 exit(-501);
285 }
286 }
287 }while (! r_bufid);
288 pvm_bufinfo(r_bufid, &bytes, &msgtag, &sender);
289 num_cols += dcmp_process_message(p, sender, msgtag, &cols, sol_id);
290 pvm_freebuf(r_bufid);
291
292 if (p->par.decomp_max_col_num_per_iter &&
293 num_cols >= p->par.decomp_max_col_num_per_iter)
294 break;
295 if (msgtag == NO_MORE_COLS && sol_id[0] == p->cur_sol.xlevel &&
296 sol_id[1] == p->dcmp_data.iter_num)
297 break;
298 }
299
300 if (num_cols >0)
301 add_dcmp_cols(p->dcmp_data.lp_data, &cols,
302 p->par.decomp_col_block_size,
303 p->par.decomp_mat_block_size);
304
305 free_dcmp_col_set(&cols);
306
307 return(num_cols);
308 }
309
310 /*------------------------------------------------------------------------*
311 * If we reach this part of the code, then "wait_for_cols" is not set.
312 * However, if block == 1, then this indicates that we should wait for
313 * at least one col to come back before exiting. This way we wait after
314 * the initial LP solution is submitted before determining that no cols
315 * have been generated.
316 *------------------------------------------------------------------------*/
317
318 while (TRUE){
319 if (block){
320 do{
321 PVM_FUNC(r_bufid, pvm_trecv(ANYONE, ANYTHING, &tout));
322 if (! r_bufid){
323 if (pvm_pstat(p->tree_manager) != PvmOk){
324 printf("TM has died -- decomp exiting\n\n");
325 exit(-502);
326 }
327 }
328 }while (! r_bufid);
329 }else{
330 if ((r_bufid = pvm_nrecv(ANYONE, ANYTHING)) < 0) PVM_ERROR(r_bufid);
331 }
332 if (!r_bufid)
333 break;
334
335 pvm_bufinfo(r_bufid, &bytes, &msgtag, &sender);
336 num_cols += dcmp_process_message(p, sender, msgtag, &cols, sol_id);
337 pvm_freebuf(r_bufid);
338
339 if (msgtag == NO_MORE_COLS && sol_id[0] == p->cur_sol.xlevel &&
340 sol_id[1] == p->dcmp_data.iter_num)
341 break;
342
343 if (p->par.decomp_max_col_num_per_iter &&
344 num_cols >= p->par.decomp_max_col_num_per_iter)
345 break;
346
347 if (num_cols){
348 /* If we received any cols
349 then set block to be false, thus we exit as soon as we have
350 process the rest of the messages in the queue. */
351 block = FALSE;
352 }
353 }
354
355 if (num_cols >0)
356 add_dcmp_cols(p->dcmp_data.lp_data, &cols,
357 p->par.decomp_col_block_size,p->par.decomp_mat_block_size);
358
359 free_dcmp_col_set(&cols);
360
361 return(num_cols);
362 }
363
364 /*===========================================================================*
365 * This function processes one message that arrived during receive_cols.
366 *===========================================================================*/
367 int dcmp_process_message(cg_prob *p, int sender, int msgtag,
368 dcmp_col_set *cols, int *sol_id)
369 {
370 int num_cols = 0, sol_pool_cols;
371 double find_cols_time;
372 col_data *col;
373 LPdata *lp_data = p->dcmp_data.lp_data;
374 int info, varnum = lp_data->m;
375 int colnum = cols->num_cols, nzcnt, i, is_new_col = FALSE;
376 double pivot_el, *unbdd_row = p->dcmp_data.unbdd_row;
377
378 switch (msgtag){
379 case PACKED_COL:
380 /* receive a packed col and add it to the current LP */
381 /* check to be sure there is enough room in the col set data structure
382 for another col -- otherwise reallocate memory */
383 if (cols->num_cols == cols->max_cols){
384 cols->max_cols += COL_BLOCK_SIZE;
385 cols->lb = (double *) realloc ((char *)cols->lb,
386 (cols->max_cols)*sizeof(double));
387 cols->ub = (double *) realloc ((char *)cols->ub,
388 (cols->max_cols)*sizeof(double));
389 cols->matbeg = (int *) realloc ((char *)cols->matbeg,
390 (cols->max_cols+1)*sizeof(int));
391 cols->obj = (double *) realloc ((char *)cols->obj,
392 (cols->max_cols+1)*sizeof(double));
393 }
394 if (cols->nzcnt + varnum > cols->max_nzcnt){
395 cols->max_nzcnt += varnum*COL_BLOCK_SIZE;
396 cols->matind = (int *) realloc ((char *)cols->matind,
397 cols->max_nzcnt*sizeof(int));
398 cols->matval = (double *) realloc ((char *)cols->matval,
399 cols->max_nzcnt*sizeof(double));
400 }
401
402 col = (col_data *) calloc (1, sizeof(col_data));
403 if ((info = pvm_upkint(&col->size, 1, 1)) < 0) PVM_ERROR(info);
404 col->coef = (char *) calloc (col->size, sizeof(char));
405 if ((info = pvm_upkbyte((col->coef), col->size, 1)) < 0) PVM_ERROR(info);
406 user_unpack_col(p, col, &nzcnt, cols->matind+cols->matbeg[colnum]);
407
408 /* check to see if the col has a pivot element < 0 in the
409 * current solution -- otherwise don't add it --
410 * also check to see if its a duplicate */
411
412 if (p->dcmp_data.dunbr){
413 for (i = cols->matbeg[colnum], pivot_el = 0; i < nzcnt; i++)
414 pivot_el += unbdd_row[cols->matind[i]];
415 }else{
416 pivot_el = -1;
417 }
418
419 if (pivot_el < - lp_data->lpetol){
420 is_new_col = TRUE;
421 for (i = 0; i < cols->num_cols; i++){
422 /* compare the new col with each of the existing cols */
423 if (cols->matbeg[i+1]-cols->matbeg[i] == nzcnt){
424 if (memcmp((char *)(cols->matind + cols->matbeg[i]),
425 (char *)(cols->matind + cols->matbeg[colnum]),
426 nzcnt*sizeof(int)) == 0){
427 is_new_col = FALSE;
428 break;
429 }
430 }
431 }
432 }
433 if (is_new_col){
434 if (p->par.verbosity > 4) user_display_col(p, col);
435 /* if we truly have a new constraint here then add it to the col set*/
436 for (i = cols->nzcnt; i < cols->nzcnt+nzcnt; i++){
437 if (lp_data->rhs[cols->matind[i]] != 0){
438 cols->matval[i] = 1;
439 }else{
440 break;
441 }
442 }
443 if (i < cols->nzcnt+nzcnt)
444 break;
445 cols->matind[cols->matbeg[colnum]+nzcnt] = varnum;
446 cols->matval[cols->matbeg[colnum]+nzcnt] = 1;
447 nzcnt++;
448 cols->lb[colnum] = 0;
449 cols->ub[colnum] = 1;
450 cols->matbeg[++cols->num_cols] = cols->matbeg[colnum]+nzcnt;
451 cols->nzcnt += nzcnt;
452 }
453 FREE(col->coef);
454 FREE(col);
455 num_cols = 1;
456 break;
457
458 case NO_MORE_COLS:
459 /* this message type says that all cols generated by the current
460 LP solution have been received and hence calculation can
461 resume */
462 if ((info = pvm_upkint(&sol_pool_cols, 1, 1)) < 0) PVM_ERROR(info);
463 if ((info = pvm_upkdouble(&find_cols_time, 1, 1)) < 0) PVM_ERROR(info);
464 if ((info = pvm_upkint(sol_id, 2, 1)) < 0) PVM_ERROR(info);
465 if (p->par.verbosity > 3)
466 printf("%i cols added from the solution pool\n", sol_pool_cols);
467 break;
468
469 default:
470 printf("Unknown message type!!\n (%i)", msgtag);
471 break;
472 }
473
474 return(num_cols);
475 }
476
477 /*****************************************************************************/
478 /*****************************************************************************/
479
480 void open_decomp_lp(cg_prob *p, int varnum)
481 {
482 LPdata *lp_data;
483 int maxn, maxm, maxnz, i;
484
485 lp_data = p->dcmp_data.lp_data
486 = (LPdata *) calloc (1, sizeof(LPdata));
487
488 open_lp_solver(lp_data);
489
490 lp_data->m = varnum+1;
491 lp_data->n = 0;
492 maxm = lp_data->maxm = varnum+1;
493
494 /* Should look at whether these sizes should be set more intelligently*/
495 maxn = lp_data->maxn = p->par.decomp_max_col_num_per_iter;
496 maxnz = lp_data->maxnz = lp_data->maxn*lp_data->maxm;
497
498 lp_data->rhs = (double *) calloc(maxm, sizeof(double));
499 lp_data->sense = (char *) calloc(maxm, sizeof(char));
500 lp_data->lb = (double *) calloc(maxn+maxm, sizeof(double));
501 lp_data->ub = (double *) calloc(maxn+maxm, sizeof(double));
502 lp_data->obj = (double *) calloc(maxn+maxm, sizeof(double));
503 lp_data->x = (double *) calloc(maxn, sizeof(double));
504 lp_data->matbeg = (int *) calloc(maxn+maxm+1, sizeof(int));
505 lp_data->matval = (double *) calloc(maxnz+maxm, sizeof(double));
506 lp_data->matind = (int *) calloc(maxnz+maxm, sizeof(int));
507 lp_data->dj = (double *) calloc(maxn, sizeof(int));
508
509 p->dcmp_data.unbdd_row = (double *) calloc (maxm, sizeof(double));
510
511 for (i=0; i<maxm; i++)
512 lp_data->sense[i] = 'E';
513
514 lp_data->lp_is_modified = LP_HAS_NOT_BEEN_MODIFIED;
515
516 }
517
518 /*****************************************************************************/
519 /*****************************************************************************/
520
521 void close_decomp_lp(cg_prob *p)
522 {
523 LPdata *lp_data = p->dcmp_data.lp_data;
524
525 FREE(lp_data->x);
526 FREE(lp_data->dj);
527
528 free_lp_solver_data(lp_data, TRUE);
529
530 /*close_lp_solver(lp_data);*/
531
532 FREE(p->dcmp_data.lp_data);
533 FREE(p->dcmp_data.unbdd_row);
534 }
535
536 /*****************************************************************************/
537 /*****************************************************************************/
538
539 int generate_cuts(cg_prob *p)
540
541 {
542 LPdata *lp_data = p->dcmp_data.lp_data;
543 double *x = lp_data->x;
544 int i, num_cols = 0, pos_cols = 0;
545
546 get_x(lp_data);
547
548 for (i = 0; i < lp_data->n; i++){
549 if (x[i] > 0){
550 pos_cols++;
551 num_cols += user_check_col(p, lp_data->matind+lp_data->matbeg[i],
552 lp_data->matval+lp_data->matbeg[i],
553 lp_data->matbeg[i+1]-lp_data->matbeg[i]);
554 }
555 }
556 printf("There are %i columns at nonzero level\n", pos_cols);
557 return(num_cols);
558 }
559
560 /*****************************************************************************/
561 /*****************************************************************************/
562
563 int generate_new_cols(cg_prob *p)
564 {
565 dcmp_col_set *cols, cols_to_add;
566 col_data *packed_col = (col_data *) calloc (1, sizeof(col_data));
567 LPdata *lp_data = p->dcmp_data.lp_data;
568 int i, j, k, info, nzcnt, col_count, s_bufid;
569 double etol = lp_data->lpetol;
570
571 cols = user_generate_new_cols(p);
572
573 if (cols->num_cols <= 0){
574 free_dcmp_col_set(cols);
575 FREE(cols);
576 FREE(packed_col)
577 return(0);
578 }
579
580 cols_to_add.lb = (double *) calloc (cols->num_cols, sizeof(double));
581 cols_to_add.ub = (double *) calloc (cols->num_cols, sizeof(double));
582 cols_to_add.matbeg = (int *) calloc (cols->num_cols+1, sizeof(int));
583 cols_to_add.matind = (int *) calloc (cols->nzcnt, sizeof(int));
584 cols_to_add.matval = (double *) calloc (cols->nzcnt, sizeof(double));
585 cols_to_add.obj = (double *) calloc (cols->num_cols, sizeof(double));
586 cols_to_add.num_cols = 0;
587 cols_to_add.max_cols = cols->num_cols;
588 cols_to_add.nzcnt = 0;
589 cols_to_add.max_nzcnt = cols->nzcnt;
590 cols_to_add.bd_type = 4;
591
592 for (i = 0, nzcnt = 0, col_count = 0; i < cols->num_cols; i++){
593 for (j = cols->matbeg[i], k = 0; j<cols->matbeg[i+1] && k < lp_data->m;
594 k++){
595 if (lp_data->rhs[k] < etol){
596 if (cols->matind[j] == k)
597 break;
598 else
599 continue;
600 }
601 if (lp_data->rhs[k] > 1-etol && cols->matind[j] != k)
602 break;
603 if (cols->matind[j] == k){
604 cols_to_add.matval[nzcnt] = 1;
605 cols_to_add.matind[nzcnt++] = cols->matind[j++];
606 }
607 }
608 if (j < cols->matbeg[i+1])
609 continue;
610
611 cols_to_add.matind[nzcnt] = lp_data->m-1;
612 cols_to_add.matval[nzcnt++] = 1;
613 cols_to_add.lb[col_count] = 0;
614 cols_to_add.ub[col_count++] = 1;
615 cols_to_add.matbeg[col_count] = nzcnt;
616
617 if (p->sol_pool){
618 user_pack_col(cols->matind+cols->matbeg[i],
619 cols->matbeg[i+1]-cols->matbeg[i], packed_col);
620
621 if ((s_bufid = pvm_initsend(PvmDataRaw)) < 0) PVM_ERROR(s_bufid);
622 if ((info = pvm_pkint(&packed_col->size, 1, 1)) < 0) PVM_ERROR(info);
623 if ((info = pvm_pkint(&p->cur_sol.xlevel, 1, 1)) < 0) PVM_ERROR(info);
624 if ((info = pvm_pkbyte(packed_col->coef, packed_col->size, 1)) < 0)
625 PVM_ERROR(info);
626 if ((info = pvm_send(p->sol_pool, PACKED_COL)) < 0) PVM_ERROR(info);
627 if ((info = pvm_freebuf(s_bufid)) < 0) PVM_ERROR(info);
628 }
629
630 FREE(packed_col->coef);
631 }
632 cols_to_add.num_cols = col_count;
633 cols_to_add.nzcnt = nzcnt;
634
635 add_dcmp_cols(lp_data, &cols_to_add, p->par.decomp_col_block_size,
636 p->par.decomp_mat_block_size);
637
638 free_dcmp_col_set(&cols_to_add);
639 free_dcmp_col_set(cols);
640 FREE(cols);
641 FREE(packed_col);
642
643 return(col_count);
644 }
645
646 void get_cols_from_pool(cg_prob *p, int tid)
647 {
648 LPdata *lp_data = p->dcmp_data.lp_data;
649 double etol = lp_data->lpetol;
650 int varnum = lp_data->m-1;
651 int *ind = NULL, *rhs_ind;
652 double *val = NULL, *unbdd_row = p->dcmp_data.unbdd_row, *rhs_val;
653 int nzcnt = 0, rhs_nzcnt, i, s_bufid, info;
654 double *rhs = lp_data->rhs;
655 int dunbr = p->dcmp_data.dunbr;
656
657 if (dunbr){
658 memset((char *)unbdd_row, 0, (varnum+1)*sizeof(double));
659 unbdd_row[dunbr-1] = -1;
660 btran(lp_data, unbdd_row);
661 }
662
663 if (!(p->dcmp_data.iter_num%p->par.decomp_sol_pool_check_freq == 0)
664 || tid == 0)
665 return;
666
667 if (dunbr){
668 ind = (int *) calloc (varnum, sizeof(int));
669 val = (double *) calloc (varnum, sizeof(double));
670 }
671
672 rhs_ind = (int *) calloc (varnum, sizeof(int));
673 rhs_val = (double *) calloc (varnum, sizeof(double));
674
675 /* xind is a list of the indices correspondoing to the nonzeros variables
676 in the current lp solution. xval contains the actual values of these
677 variables */
678 if (dunbr){
679 for (nzcnt = i = 0; i < varnum; i++){
680 if (unbdd_row[i] > etol || unbdd_row[i] < -etol){
681 ind[nzcnt] = i;
682 val[nzcnt++] = unbdd_row[i];
683 }
684 }
685 }
686 for (rhs_nzcnt = i = 0; i < varnum; i++){
687 if (rhs[i] > etol){
688 rhs_ind[rhs_nzcnt] = i;
689 rhs_val[rhs_nzcnt++] = rhs[i];
690 }
691 }
692 if (dunbr && (ind[nzcnt-1] != lp_data->m-1)){
693 ind[nzcnt] = lp_data->m-1;
694 val[nzcnt++] = 0;
695 }
696
697 /* send the data */
698 if ((s_bufid = pvm_initsend(PvmDataRaw)) < 0) PVM_ERROR(s_bufid);
699 if ((info = pvm_pkint(&nzcnt, 1, 1)) < 0) PVM_ERROR(info);
700 if (nzcnt){
701 if ((info = pvm_pkint(ind, nzcnt, 1)) < 0) PVM_ERROR(info);
702 if ((info = pvm_pkdouble(val, nzcnt, 1)) < 0) PVM_ERROR(info);
703 }
704 if ((info = pvm_pkint(&rhs_nzcnt, 1, 1)) < 0) PVM_ERROR(info);
705 if ((info = pvm_pkint(rhs_ind, rhs_nzcnt, 1)) < 0) PVM_ERROR(info);
706 if ((info = pvm_pkdouble(rhs_val, rhs_nzcnt, 1)) < 0) PVM_ERROR(info);
707 if ((pvm_pkint(&p->cur_sol.xlevel, 1, 1)) < 0) PVM_ERROR(info);
708 if ((info = pvm_pkint(&p->dcmp_data.iter_num, 1, 1)) < 0) PVM_ERROR(info);
709 if ((info = pvm_send(tid, CG_LP_SOLUTION)) < 0) PVM_ERROR(info);
710
711 FREE(ind);
712 FREE(val);
713 FREE(rhs_ind);
714 FREE(rhs_val);
715 }
716
717 void add_dcmp_cols(LPdata *lp_data, dcmp_col_set *cols, int col_block_size,
718 int mat_block_size)
719 {
720 char *where_to_move = (char *) calloc(cols->num_cols, sizeof(char));
721
722 if (lp_data->n + cols->num_cols > lp_data->maxn ||
723 lp_data->nz + cols->nzcnt > lp_data->maxnz){
724 /*Currently, this should never happen since we allocate enough space up
725 front. However, should think about changing this */
726 printf("Error: Resizing LP in decomp. Aborting...\n\n");
727 exit(1);
728 #if 0
729 resize_lp(lp_data, 0, col_block_size, mat_block_size, 0, cols->num_cols,
730 cols->nzcnt, &maxm, &maxn, &maxnz);
731 if (maxn > lp_data->maxn){
732 lp_data->maxn = maxn;
733 lp_data->x = (double *) realloc(lp_data->x, maxn * DSIZE);
734 lp_data->dj = (double *) realloc(lp_data->dj, maxn * DSIZE);
735 }
736 #endif
737 }
738
739 add_cols(lp_data, cols->num_cols, cols->nzcnt, cols->obj, cols->matbeg,
740 cols->matind, cols->matval, cols->lb, cols->ub, where_to_move);
741 }
742
743 void free_dcmp_col_set(dcmp_col_set *cols)
744 {
745 FREE(cols->obj);
746 FREE(cols->lb);
747 FREE(cols->ub);
748 FREE(cols->matbeg);
749 FREE(cols->matind);
750 FREE(cols->matval);
751 }