1 /*===========================================================================*/
2 /* */
3 /* This file is part of the SYMPHONY MILP Solver Framework. */
4 /* */
5 /* SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and */
6 /* Laci Ladanyi (ladanyi@us.ibm.com). */
7 /* */
8 /* (c) Copyright 2000-2019 Ted Ralphs. All Rights Reserved. */
9 /* */
10 /* The OSI interface in this file was written by Menal Guzelsoy. */
11 /* The OSL interface was written by Ondrej Medek. */
12 /* */
13 /* This software is licensed under the Eclipse Public License. Please see */
14 /* accompanying file for terms. */
15 /* */
16 /*===========================================================================*/
17
18 #include <stdlib.h>
19 #include <memory.h>
20 #include <math.h>
21
22 #ifdef _OPENMP
23 #include "omp.h"
24 #endif
25
26 #include "sym_lp.h"
27 #include "sym_master.h"
28 #include "sym_proccomm.h"
29 #include "sym_messages.h"
30 #include "sym_constants.h"
31 #include "sym_macros.h"
32 #include "sym_types.h"
33 #include "sym_lp_solver.h"
34 #include "sym_primal_heuristics.h"
35 #include "sym_qsort.h"
36 #ifdef USE_CGL_CUTS
37 #include "sym_cg.h"
38 #endif
39 #if defined (COMPILE_IN_LP) && defined (COMPILE_IN_TM)
40 #include "sym_master_u.h"
41 #endif
42 #ifdef COMPILE_IN_CP
43 #include "sym_cp.h"
44 #endif
45
46 /*===========================================================================*/
47
48 /*===========================================================================*\
49 * This file contains LP wrapper functions that interface with the user.
50 \*===========================================================================*/
51
52 /*===========================================================================*\
53 * This function invokes the user written function user_receive_lp_data that
54 * receives the initial data from the Master process. Returns TRUE if
55 * succeeded, FALSE otherwise.
56 \*===========================================================================*/
57
receive_lp_data_u(lp_prob * p)58 int receive_lp_data_u(lp_prob *p)
59 {
60 int r_bufid;
61 char has_desc;
62 char has_colnames;
63 int i;
64
65 r_bufid = receive_msg(p->master, LP_DATA);
66 receive_char_array((char *)(&p->par), sizeof(lp_params));
67 receive_int_array(&p->has_ub, 1);
68 if (p->has_ub){
69 receive_dbl_array(&p->ub, 1);
70 }else{
71 p->ub = - (MAXDOUBLE / 2);
72 }
73 if(p->par.multi_criteria){
74 receive_int_array(&p->has_mc_ub, 1);
75 if (p->has_mc_ub){
76 receive_dbl_array(&p->mc_ub, 1);
77 receive_dbl_array(p->obj, 2);
78 }else{
79 p->mc_ub = - (MAXDOUBLE / 2);
80 }
81 receive_dbl_array(p->utopia, 2);
82 }
83 receive_int_array(&p->draw_graph, 1);
84 receive_int_array(&p->base.varnum, 1);
85 if (p->base.varnum > 0){
86 p->base.userind = (int *) malloc(p->base.varnum * ISIZE);
87 receive_int_array(p->base.userind, p->base.varnum);
88 }
89 receive_int_array(&p->base.cutnum, 1);
90 MIPdesc *mip = p->mip = (MIPdesc *) calloc(1, sizeof(MIPdesc));
91 receive_int_array(&(mip->m), 1);
92 receive_int_array(&(mip->n), 1);
93 receive_int_array(&(mip->nz), 1);
94 receive_char_array(&(mip->obj_sense), 1);
95 receive_dbl_array(&(mip->obj_offset), 1);
96 receive_char_array(&has_desc, 1);
97
98 if (has_desc){
99 /* Allocate memory */
100 mip->matbeg = (int *) malloc(ISIZE * (mip->n + 1));
101 mip->matind = (int *) malloc(ISIZE * mip->nz);
102 mip->matval = (double *) malloc(DSIZE * mip->nz);
103 mip->obj = (double *) malloc(DSIZE * mip->n);
104 if (p->par.multi_criteria){
105 mip->obj1 = (double *) malloc(DSIZE * mip->n);
106 mip->obj2 = (double *) malloc(DSIZE * mip->n);
107 }
108 mip->rhs = (double *) malloc(DSIZE * mip->m);
109 mip->sense = (char *) malloc(CSIZE * mip->m);
110 mip->rngval = (double *) malloc(DSIZE * mip->m);
111 mip->ub = (double *) malloc(DSIZE * mip->n);
112 mip->lb = (double *) malloc(DSIZE * mip->n);
113 mip->is_int = (char *) calloc(CSIZE, mip->n);
114
115 /* Receive the problem description */
116 receive_int_array(mip->matbeg, mip->n+1);
117 receive_int_array(mip->matind, mip->nz);
118 receive_dbl_array(mip->matval, mip->nz);
119 receive_dbl_array(mip->obj, mip->n);
120 if (p->par.multi_criteria){
121 receive_dbl_array(mip->obj1, mip->n);
122 receive_dbl_array(mip->obj2, mip->n);
123 }
124 receive_dbl_array(mip->rhs, mip->m);
125 receive_char_array(mip->sense, mip->m);
126 receive_dbl_array(mip->rngval, mip->m);
127 receive_dbl_array(mip->ub, mip->n);
128 receive_dbl_array(mip->lb, mip->n);
129 receive_char_array(mip->is_int, mip->n);
130 receive_char_array(&has_colnames, 1);
131 if (has_colnames){
132 mip->colname = (char **) malloc(sizeof(char *) * mip->n);
133 for (i = 0; i < mip->n; i++){
134 mip->colname[i] = (char *) malloc(CSIZE * MAX_NAME_SIZE);
135 receive_char_array(mip->colname[i], MAX_NAME_SIZE);
136 mip->colname[i][MAX_NAME_SIZE-1] = 0;
137 }
138 }
139 }
140
141 #ifdef USE_SYM_APPLICATION
142 switch( user_receive_lp_data(&p->user)){
143 case USER_ERROR:
144 freebuf(r_bufid);
145 return(ERROR__USER);
146 case USER_SUCCESS:
147 case USER_AND_PP:
148 case USER_NO_PP:
149 /* User function terminated without problems. No post-processing. */
150 break;
151 default:
152 freebuf(r_bufid);
153 /* Unexpected return value. Do something!! */
154 return(ERROR__USER);
155 }
156 #endif
157
158 return(FUNCTION_TERMINATED_NORMALLY);
159 }
160
161 /*===========================================================================*/
162
comp_cut_name(const void * c0,const void * c1)163 int comp_cut_name(const void *c0, const void *c1)
164 {
165 return((*((cut_data **)c0))->name - (*((cut_data **)c1))->name);
166 }
167
168 /*===========================================================================*/
169
170 /*===========================================================================*\
171 * This function invokes the user written function user_create_subproblem that
172 * creates the problem matrix.
173 \*===========================================================================*/
174
create_subproblem_u(lp_prob * p)175 int create_subproblem_u(lp_prob *p)
176 {
177 node_desc *desc = p->desc;
178
179 LPdata *lp_data = p->lp_data;
180 int i, j, k, maxm, maxn, maxnz;
181 row_data *row, *rows;
182
183 int bvarnum = p->base.varnum;
184 int bcutnum = p->base.cutnum;
185 var_desc **vars;
186
187 int *d_uind = NULL, *d_cind = NULL; /* just to keep gcc quiet */
188
189 double *rhs, *rngval, *darray;
190 char *sense;
191 char *status;
192 cut_data *cut;
193 branch_desc *bobj;
194
195 int new_row_num;
196 waiting_row **new_rows;
197
198 int user_res;
199 int *userind;
200
201 double *lb, *ub;
202 char *is_int;
203 MIPdesc *lp_data_mip, *p_mip, *tmp_mip;
204 char *lp_data_mip_is_int, *p_mip_is_int;
205 double *lp_data_mip_ub, *p_mip_ub;
206 double *lp_data_mip_lb, *p_mip_lb;
207 double *lp_data_mip_obj, *p_mip_obj;
208 int *lp_data_mip_matbeg, *p_mip_matbeg;
209 int *lp_data_mip_matind, *p_mip_matind;
210 double *lp_data_mip_matval, *p_mip_matval;
211 char *lp_data_mip_sense, *p_mip_sense;
212 double *lp_data_mip_rhs, *p_mip_rhs;
213 double *lp_data_mip_rngval, *p_mip_rngval;
214
215 p->par.lp_data_mip_is_copied = TRUE;
216 p_mip = p->mip;
217 tmp_mip = lp_data->mip;
218
219 lp_data->n = bvarnum + desc->uind.size;
220 lp_data->m = bcutnum + desc->cutind.size;
221
222 maxm = lp_data->maxm;
223 maxn = lp_data->maxn;
224 maxnz = lp_data->maxnz;
225 lp_data->nf_status = desc->nf_status;
226 if (desc->nf_status == NF_CHECK_AFTER_LAST ||
227 desc->nf_status == NF_CHECK_UNTIL_LAST){
228 lp_data->not_fixed_num = desc->not_fixed.size;
229 memcpy(lp_data->not_fixed, desc->not_fixed.list,
230 lp_data->not_fixed_num * ISIZE);
231 }
232
233 if (desc->uind.size > 0){ /* fill up the rest of lp_data->vars */
234 if (MAX(maxn, bvarnum) < lp_data->n){
235 vars = lp_data->vars = (var_desc **)
236 realloc(lp_data->vars, lp_data->n * sizeof(var_desc *));
237 for (i = lp_data->n - 1; i >= MAX(maxn, bvarnum); i--){
238 vars[i] = (var_desc *) malloc(sizeof(var_desc) );
239 }
240 }
241 vars = lp_data->vars;
242 d_uind = desc->uind.list;
243 for (i = desc->uind.size - 1; i >= 0; i--){
244 vars[i + bvarnum]->userind = d_uind[i];
245 vars[i + bvarnum]->colind = bvarnum + i;
246 }
247
248 if (p->par.multi_criteria && !p->par.mc_find_supported_solutions){
249 vars[lp_data->n - 1]->userind = p_mip->n;
250 vars[lp_data->n - 1]->colind = lp_data->n - 1;
251 }
252 }
253 lp_data->ordering = COLIND_AND_USERIND_ORDERED;
254
255 lp_data_mip = lp_data->mip;
256 lp_data_mip->n = lp_data->n;
257 lp_data_mip->m = lp_data->m;
258
259 /* Create the list of indices to pass to the user */
260 userind = (int *) malloc(lp_data->n * ISIZE);
261 vars = lp_data->vars;
262 p->par.is_userind_in_order = TRUE;
263 for (i = lp_data->n - 1; i >= 0; --i){
264 userind[i] = vars[i]->userind;
265 if (userind[i]!=i) {
266 p->par.is_userind_in_order = FALSE;
267 }
268 }
269 /*This is always violated for multi_crtieria due to the addition of the
270 artificial variable. It's probably not needed...*/
271 if (lp_data->n != p_mip->n) {
272 p->par.is_userind_in_order = FALSE;
273 }
274
275 #ifdef USE_SYM_APPLICATION
276 user_res = user_create_subproblem(p->user,
277 /* list of base and extra variables */
278 userind,
279 /* description of the LP relaxation to be filled out by the user */
280 lp_data_mip,
281 /* max sizes (estimated by the user) */
282 &maxn, &maxm, &maxnz);
283 #else
284 user_res = USER_DEFAULT;
285 #endif
286 switch (user_res){
287
288 case USER_DEFAULT:
289
290 if (!p_mip->matbeg){
291 printf("Illegal return code.\n");
292 printf("Trying to use default user_create_subproblem without");
293 printf("reading an MPS or AMPL file. Exiting...\n\n");
294 return(ERROR__ILLEGAL_RETURN_CODE);
295 }
296
297 lp_data_mip->nz = p_mip->nz;
298 if (p->par.multi_criteria && !p->par.mc_find_supported_solutions){
299 lp_data_mip->nz += 2 * lp_data->n;
300 }
301
302 if (p->par.is_userind_in_order == FALSE || p->bc_index == 0) {
303 /* Allocate the arrays.*/
304 lp_data_mip->matbeg = (int *) malloc((lp_data_mip->n + 1) * ISIZE);
305 lp_data_mip->matind = (int *) malloc((lp_data_mip->nz) * ISIZE);
306 lp_data_mip->matval = (double *) malloc((lp_data_mip->nz) * DSIZE);
307 lp_data_mip->obj = (double *) malloc(lp_data_mip->n * DSIZE);
308 lp_data_mip->ub = (double *) malloc(lp_data_mip->n * DSIZE);
309 lp_data_mip->lb = (double *) calloc(lp_data_mip->n, DSIZE);
310 lp_data_mip->rhs = (double *) malloc(lp_data_mip->m * DSIZE);
311 lp_data_mip->sense = (char *) malloc(lp_data_mip->m * CSIZE);
312 lp_data_mip->rngval = (double *) calloc(lp_data_mip->m, DSIZE);
313 lp_data_mip->is_int = (char *) calloc(lp_data_mip->n, CSIZE);
314
315 lp_data_mip_is_int = lp_data_mip->is_int;
316 lp_data_mip_ub = lp_data_mip->ub;
317 lp_data_mip_lb = lp_data_mip->lb;
318 lp_data_mip_obj = lp_data_mip->obj;
319 lp_data_mip_matbeg = lp_data_mip->matbeg;
320 lp_data_mip_matind = lp_data_mip->matind;
321 lp_data_mip_matval = lp_data_mip->matval;
322 lp_data_mip_sense = lp_data_mip->sense;
323 lp_data_mip_rhs = lp_data_mip->rhs;
324 lp_data_mip_rngval = lp_data_mip->rngval;
325
326 p_mip_is_int = p_mip->is_int;
327 p_mip_ub = p_mip->ub;
328 p_mip_lb = p_mip->lb;
329 p_mip_obj = p_mip->obj;
330 p_mip_matbeg = p_mip->matbeg;
331 p_mip_matind = p_mip->matind;
332 p_mip_matval = p_mip->matval;
333 p_mip_sense = p_mip->sense;
334 p_mip_rhs = p_mip->rhs;
335 p_mip_rngval = p_mip->rngval;
336 /* Fill out the appropriate data structures*/
337 lp_data_mip_matbeg[0] = 0;
338 for (j = 0, i = 0; i < lp_data_mip->n; i++){
339 if (userind[i] == p_mip->n){
340 /* We should only be here with multi-criteria problems. */
341 /* This is the artifical variable added for finding nondominated */
342 /* solutions. */
343 lp_data_mip_is_int[i] = FALSE;
344 lp_data_mip_ub[i] = MAXINT;
345 lp_data_mip_lb[i] = -MAXINT;
346 lp_data_mip_obj[i] = 1.0;
347 lp_data_mip_matval[j] = -1.0;
348 lp_data_mip_matind[j++] = bcutnum - 2;
349 lp_data_mip_matval[j] = -1.0;
350 lp_data_mip_matind[j++] = bcutnum - 1;
351 lp_data_mip_matbeg[i+1] = j;
352 continue;
353 }
354 lp_data_mip_ub[i] = p_mip_ub[userind[i]];
355 lp_data_mip_lb[i] = p_mip_lb[userind[i]];
356 lp_data_mip_is_int[i] = p_mip_is_int[userind[i]];
357 for (k = p_mip_matbeg[userind[i]]; k < p_mip_matbeg[userind[i]+1];
358 k++){
359 lp_data_mip_matind[j] = p_mip_matind[k];
360 lp_data_mip_matval[j++] = p_mip_matval[k];
361 }
362 if (p->par.multi_criteria && !p->par.mc_find_supported_solutions){
363 lp_data_mip_obj[i] = p->par.mc_rho*(p_mip->obj1[userind[i]] +
364 p_mip->obj2[userind[i]]);
365 lp_data_mip_matval[j] = p->par.mc_gamma*p_mip->obj1[userind[i]];
366 lp_data_mip_matind[j++] = bcutnum - 2;
367 lp_data_mip_matval[j] = p->par.mc_tau*p_mip->obj2[userind[i]];
368 lp_data_mip_matind[j++] = bcutnum - 1;
369 }else{
370 lp_data_mip_obj[i] = p_mip_obj[userind[i]];
371 }
372 lp_data_mip_matbeg[i+1] = j;
373 }
374 lp_data_mip->nz = j;
375 for (i = 0; i < p_mip->m; i++){
376 lp_data_mip_rhs[i] = p_mip_rhs[i];
377 lp_data_mip_sense[i] = p_mip_sense[i];
378 lp_data_mip_rngval[i] = p_mip_rngval[i];
379 }
380 if (p->par.multi_criteria && !p->par.mc_find_supported_solutions){
381 lp_data_mip_rhs[bcutnum - 2] = p->par.mc_gamma * p->utopia[0];
382 lp_data_mip_sense[bcutnum - 2] = 'L';
383 lp_data_mip_rhs[bcutnum - 1] = p->par.mc_tau * p->utopia[1];
384 lp_data_mip_sense[bcutnum - 1] = 'L';
385 }
386 } else {
387 p->par.lp_data_mip_is_copied = FALSE;
388 lp_data->mip = p->mip;
389 lp_data_mip = p->mip;
390 }
391 maxm = lp_data->m;
392 maxn = lp_data->n;
393 maxnz = lp_data->nz;
394 lp_data->m = bcutnum;
395 lp_data->nz = lp_data_mip->nz;
396 break;
397 case USER_SUCCESS:
398 /* Fall through to next case */
399 case USER_AND_PP:
400 case USER_NO_PP:
401
402 /* User function terminated without problems. In the post-processing
403 * the extra cuts are added. HOWEVER, this might not be done until the
404 * problem is loaded into the lp solver (for cplex it is not possible).
405 * So for now just reset lp_data->m, do everything to load in the
406 * stuff into the lp solver then come back to adding the cuts. */
407
408 /* change obj coeff only if the obj funct. was created through
409 user_create_subproblem() */
410
411 if (p_mip->obj_sense == SYM_MAXIMIZE){
412 lp_data_mip_obj = lp_data_mip->obj;
413 for (i = 0; i < lp_data_mip->n; i++){
414 lp_data_mip_obj[i] *= -1.0;
415 }
416 }
417
418 lp_data->m = bcutnum;
419 lp_data->nz = lp_data_mip->nz;
420 break;
421
422 case USER_ERROR:
423
424 /* Error. The search tree node will not be processed. */
425 FREE(userind);
426 return(ERROR__USER);
427
428 default:
429
430 /* Unexpected return value. Do something!! */
431 FREE(userind);
432 return(ERROR__USER);
433 }
434
435 FREE(userind); /* No longer needed */
436
437 /*------------------------------------------------------------------------*\
438 * Let's see about reallocing...
439 \*----------------------------------------------------------------------- */
440
441 if (maxm < lp_data->m) maxm = lp_data->m;
442 if (maxn < lp_data->n) maxn = lp_data->n;
443 if (maxnz < lp_data->nz) maxnz = lp_data->nz;
444
445 size_lp_arrays(lp_data, FALSE, TRUE, maxm, maxn, maxnz);
446
447 /* generate the random hash. useful for checking duplicacy of cuts and
448 * solutions from feasibility pump
449 */
450
451 if (p->par.is_userind_in_order == FALSE || p->bc_index == 0) {
452 darray = lp_data->random_hash;
453 for (i=0; i<lp_data->n; i++) {
454 darray[i] = CoinDrand48();
455 }
456 }
457
458 if (lp_data->maxn > lp_data->n){
459 vars = lp_data->vars = (var_desc **)
460 realloc(lp_data->vars, lp_data->maxn * sizeof(var_desc *));
461 for (i = lp_data->n; i < lp_data->maxn; i++){
462 vars[i] = (var_desc *) malloc( sizeof(var_desc) );
463 }
464 }
465
466 // TODO: fix char vs int
467 /* Default status of every variable is NOT_FIXED */
468 status = lp_data->status;
469 if (bvarnum > 0) {
470 //memset(lp_data->status, NOT_FIXED | BASE_VARIABLE, bvarnum);
471 for (i=0; i<bvarnum; i++) {
472 status[i] = NOT_FIXED | BASE_VARIABLE;
473 }
474 }
475 if (bvarnum < lp_data->n) {
476 //memset(lp_data->status + bvarnum, NOT_FIXED, lp_data->n - bvarnum);
477 for (i=bvarnum; i<lp_data->n; i++) {
478 status[i] = NOT_FIXED;
479 }
480 }
481
482 /*------------------------------------------------------------------------*\
483 * Set the necessary fields in rows
484 \*----------------------------------------------------------------------- */
485
486 rows = lp_data->rows;
487 rhs = lp_data_mip->rhs;
488 rngval = lp_data_mip->rngval;
489 sense = lp_data_mip->sense;
490 if (p->par.multi_criteria){
491 assert(bcutnum == p->mip->m+2);
492 }else{
493 assert(bcutnum == p->mip->m);
494 }
495 for (i = bcutnum - 1; i >= 0; i--){
496 row = rows + i;
497 cut = row->cut;
498 cut->rhs = rhs[i];
499 cut->range = rngval[i];
500 cut->branch = (((cut->sense = sense[i]) != 'E') ?
501 ALLOWED_TO_BRANCH_ON : DO_NOT_BRANCH_ON_THIS_ROW);
502 cut->size = 0;
503 row->eff_cnt = 1;
504 row->free = FALSE;
505 cut->name = BASE_CONSTRAINT;
506 cut->type = ORIGINAL_CONSTRAINT;
507 }
508
509 /*------------------------------------------------------------------------*\
510 * Set the upper and lower bounds and integer status
511 \*----------------------------------------------------------------------- */
512
513 lb = lp_data_mip->lb;
514 ub = lp_data_mip->ub;
515 is_int = lp_data_mip->is_int;
516
517 vars = lp_data->vars;
518 for (i = lp_data->n - 1; i >= 0; i--){
519 vars[i]->lb = vars[i]->new_lb = lb[i];
520 vars[i]->ub = vars[i]->new_ub = ub[i];
521 vars[i]->is_int = is_int[i];
522 }
523
524 /*------------------------------------------------------------------------*\
525 * Load the lp problem (load_lp is an lp solver dependent routine).
526 \*----------------------------------------------------------------------- */
527 if (p->bc_index == 0 || p->par.should_reuse_lp == FALSE) {
528 load_lp_prob(lp_data, p->par.scaling, p->par.fastmip); //load new
529 } else {
530 reset_lp_prob(lp_data, p->par.scaling, p->par.fastmip); //use old
531 }
532
533 /* Free the user's description */
534 if (p->par.lp_data_mip_is_copied == TRUE) {
535 free_mip_desc(lp_data_mip);
536 }
537 lp_data->mip = tmp_mip;
538
539 if (desc->cutind.size > 0){
540 unpack_cuts_u(p, CUT_FROM_TM, UNPACK_CUTS_SINGLE,
541 desc->cutind.size, desc->cuts, &new_row_num, &new_rows);
542 add_row_set(p, new_rows, new_row_num);
543 FREE(new_rows);
544 }
545 /* We don't need the cuts anymore. Free them. */
546 if (desc->cutind.size > 0){
547 #ifndef COMPILE_IN_LP /*If we are using shared memory, we don't need to free*/
548 free_cuts(desc->cuts, desc->cutind.size);
549 #endif
550 FREE(desc->cuts);
551 }else{
552 desc->cuts = NULL;
553 }
554 lp_data->cgl = p->par.cgl;
555 #ifdef COMPILE_IN_LP
556 /* reliability branching */
557 /* pseudo costs and reliability measures */
558 if (p->tm->pcost_down==NULL) {
559 p->pcost_down = (double *)calloc(p->mip->n, DSIZE);
560 p->pcost_up = (double *)calloc(p->mip->n, DSIZE);
561 p->br_rel_down = (int *)calloc(p->mip->n, ISIZE);
562 p->br_rel_up = (int *)calloc(p->mip->n, ISIZE);
563 p->br_rel_cand_list = (int *)calloc(p->mip->n, ISIZE);
564 p->br_rel_down_min_level = (int *)malloc(p->mip->n* ISIZE);
565 p->br_rel_up_min_level = (int *)malloc(p->mip->n* ISIZE);
566 p->br_inf_down = (int *)calloc(p->mip->n, ISIZE);
567 p->br_inf_up = (int *)calloc(p->mip->n, ISIZE);
568 for(i = 0; i <p->mip->n; i++){
569 p->br_rel_down_min_level[i] =
570 p->br_rel_up_min_level[i] = (int)1e7;
571 }
572 p->tm->pcost_down = p->pcost_down;
573 p->tm->pcost_up = p->pcost_up;
574 p->tm->br_rel_down = p->br_rel_down;
575 p->tm->br_rel_up = p->br_rel_up;
576 p->tm->br_rel_cand_list = p->br_rel_cand_list;
577 p->tm->br_rel_down_min_level = p->br_rel_down_min_level;
578 p->tm->br_rel_up_min_level = p->br_rel_up_min_level;
579 p->tm->br_inf_down = p->br_inf_down;
580 p->tm->br_inf_up = p->br_inf_up;
581 } else {
582 p->pcost_down = p->tm->pcost_down;
583 p->pcost_up = p->tm->pcost_up;
584 p->br_rel_down = p->tm->br_rel_down;
585 p->br_rel_up = p->tm->br_rel_up;
586 p->br_rel_down_min_level = p->tm->br_rel_down_min_level;
587 p->br_rel_up_min_level = p->tm->br_rel_up_min_level;
588 p->br_inf_down = p->tm->br_inf_down;
589 p->br_inf_up = p->tm->br_inf_up;
590 p->br_rel_cand_list = p->tm->br_rel_cand_list;
591 }
592
593 if(p->tm->var_rank == NULL){
594 p->var_rank = (double *)calloc(p->mip->n, DSIZE);
595 //p->var_rank_num = (int *)calloc(p->mip->n, ISIZE);
596 p->tm->var_rank = p->var_rank;
597 //p->tm->var_rank_num = p->var_rank_num;
598 }else{
599 p->var_rank = p->tm->var_rank;
600 //p->var_rank_num = p->tm->var_rank_num;
601 }
602
603 //if(p->frac_var_cnt == NULL)
604 // p->frac_var_cnt = (int *)calloc(lp_data->n,ISIZE);
605 //lp_data->frac_var_cnt = p->frac_var_cnt;
606
607 if(p->tm->root_lp == NULL){
608 p->root_lp = (double *)calloc(p->mip->n+1, DSIZE);
609 p->tm->root_lp = p->root_lp;
610 }else{
611 p->root_lp = p->tm->root_lp;
612 }
613 #endif
614
615 p->str_br_check = TRUE;
616 /*------------------------------------------------------------------------*\
617 * Now go through the branching stuff
618 \*----------------------------------------------------------------------- */
619 if (p->par.lp_data_mip_is_copied == FALSE) {
620 /* first reset all bounds */
621 for (j=0; j<lp_data->n; j++) {
622 change_ub(lp_data, j, p->mip->ub[j]);
623 change_lb(lp_data, j, p->mip->lb[j]);
624 }
625 }
626 d_cind = desc->cutind.list;
627 vars = lp_data->vars;
628 rows = lp_data->rows;
629 if (p->bc_level){
630 bobj = p->bdesc + p->bc_level - 1;
631 p->branch_var = -1;
632 p->branch_dir = bobj->sense;
633 status = lp_data->status;
634 for (i = 0; i < p->bc_level; i++){
635 bobj = p->bdesc + i;
636 //bd_change = p->bnd_change + i;
637 if (bobj->type == BRANCHING_VARIABLE){
638 j = bobj->name < 0 ? /* base variable : extra variable */
639 -bobj->name-1 :
640 bfind(bobj->name, d_uind, desc->uind.size) + bvarnum;
641 p->branch_var = j;
642 switch (bobj->sense){
643 case 'E':
644 change_lbub(lp_data, j, bobj->rhs, bobj->rhs);
645 vars[j]->lb = vars[j]->ub = bobj->rhs;
646 vars[j]->new_lb = vars[j]->new_ub = bobj->rhs;
647 break;
648 case 'L':
649 change_ub(lp_data, j, bobj->rhs);
650 vars[j]->ub = bobj->rhs;
651 vars[j]->new_ub = bobj->rhs;
652 break;
653 case 'G':
654 change_lb(lp_data, j, bobj->rhs);
655 vars[j]->lb = bobj->rhs;
656 vars[j]->new_lb = bobj->rhs;
657 break;
658 case 'R':
659 change_lbub(lp_data, j, bobj->rhs, bobj->rhs + bobj->range);
660 vars[j]->lb = bobj->rhs;
661 vars[j]->new_lb = bobj->rhs;
662 vars[j]->ub = bobj->rhs + bobj->range;
663 vars[j]->new_ub = bobj->rhs + bobj->range;
664 break;
665 }
666 status[j] |= VARIABLE_BRANCHED_ON;
667 }else if(bobj->type == SOS1_IMPLICIT){
668 for(j = 0; j < bobj->sos_cnt; j++){
669 change_ub(lp_data, bobj->sos_ind[j], 0.0);
670 vars[bobj->sos_ind[j]]->ub = 0.0;
671 vars[bobj->sos_ind[j]]->new_ub = 0.0;
672 }
673 }else{ /* BRANCHING_CUT */
674 j = bobj->name < 0 ? /* base constraint : extra constraint */
675 -bobj->name-1 :
676 bfind(bobj->name, d_cind, desc->cutind.size) + bcutnum;
677 change_row(lp_data, j, bobj->sense, bobj->rhs, bobj->range);
678 #ifdef COMPILE_IN_LP
679 /* Because these cuts are shared with the treemanager, we have to
680 make a copy before changing them if the LP is compiled in */
681 cut = (cut_data *) malloc(sizeof(cut_data));
682 memcpy((char *)cut, (char *)rows[j].cut, sizeof(cut_data));
683 if (cut->size){
684 cut->coef = (char *) malloc(cut->size);
685 memcpy((char *)cut->coef, (char *)rows[j].cut->coef,
686 cut->size);
687 }
688 rows[j].cut = cut;
689 #else
690 cut = rows[j].cut;
691 #endif
692 cut->rhs = bobj->rhs;
693 cut->range = bobj->range;
694 cut->sense = bobj->sense;
695 cut->branch |= CUT_BRANCHED_ON;
696 }
697 }
698 }
699
700 /*------------------------------------------------------------------------*\
701 * Change bounds of variables that got changed in previous nodes
702 \*----------------------------------------------------------------------- */
703 /*
704 for (i=0; i<lp_data->n; i++) {
705 if (vars[i]->lb != vars[i]->new_lb) {
706 printf("new lb of %d = %f, old = %f\n", i, vars[i]->new_lb,
707 vars[i]->lb);
708 }
709 if (vars[i]->ub != vars[i]->new_ub) {
710 printf("new ub of %d = %f, old = %f\n", i, vars[i]->new_ub,
711 vars[i]->ub);
712 }
713 }
714 */
715 #ifdef COMPILE_IN_LP
716 if (p->desc->bnd_change) {
717 bounds_change_desc *bnd_change = p->desc->bnd_change;
718 int *index = bnd_change->index;
719 char *lbub = bnd_change->lbub;
720 double *value = bnd_change->value;
721 int tmp_index = -1;
722 for (i=0; i<bnd_change->num_changes; i++) {
723 tmp_index = -1;
724 if (vars[index[i]]->userind == index[i]) {
725 tmp_index = index[i];
726 } else {
727 for (j=0; j<lp_data->n; j++) {
728 if (vars[j]->userind==index[i]) {
729 tmp_index = j;
730 }
731 }
732 }
733 if (tmp_index<0) {
734 /*
735 * the variable with userind index[i] does not exist in this
736 * formulation
737 */
738 continue;
739 }
740 if (lbub[i] == 'L') {
741 if (vars[tmp_index]->lb<value[i]) {
742 vars[tmp_index]->lb = value[i];
743 vars[tmp_index]->new_lb = value[i];
744 change_lb(lp_data, tmp_index, value[i]);
745 }
746 }
747 if (lbub[i] == 'U') {
748 if (vars[tmp_index]->ub>value[i]) {
749 vars[tmp_index]->ub = value[i];
750 vars[tmp_index]->new_ub = value[i];
751 change_ub(lp_data, tmp_index, value[i]);
752 }
753 }
754 }
755 /* p->desc->bnd_change_desc no longer needed. free it */
756 FREE(bnd_change->index);
757 FREE(bnd_change->lbub);
758 FREE(bnd_change->value);
759 FREE(p->desc->bnd_change);
760 }
761 #else
762 p->desc->bnd_change = NULL;
763 #endif
764
765 /*------------------------------------------------------------------------*\
766 * The final step: load in the basis.
767 * This is cplex style. sorry about it... Still, it
768 * might be ok if {VAR,SLACK}_{B,LB,UB} are properly defined
769 \*----------------------------------------------------------------------- */
770
771 if (p->par.should_warmstart_chain == TRUE &&
772 desc->basis.basis_exists == TRUE){
773 int *rstat, *cstat;
774 if (desc->basis.extravars.size == 0){
775 cstat = desc->basis.basevars.stat;
776 }else if (desc->basis.basevars.size == 0){
777 cstat = desc->basis.extravars.stat;
778 }else{ /* neither is zero */
779 cstat = lp_data->tmp.i1; /* n */
780 memcpy(cstat,
781 desc->basis.basevars.stat, desc->basis.basevars.size *ISIZE);
782 memcpy(cstat + desc->basis.basevars.size,
783 desc->basis.extravars.stat, desc->basis.extravars.size *ISIZE);
784 }
785 if (desc->basis.extrarows.size == 0){
786 rstat = desc->basis.baserows.stat;
787 }else if (desc->basis.baserows.size == 0){
788 rstat = desc->basis.extrarows.stat;
789 }else{ /* neither is zero */
790 rstat = lp_data->tmp.i2; /* m */
791 memcpy(rstat,
792 desc->basis.baserows.stat, desc->basis.baserows.size *ISIZE);
793 memcpy(rstat + desc->basis.baserows.size,
794 desc->basis.extrarows.stat, desc->basis.extrarows.size *ISIZE);
795 }
796 load_basis(lp_data, cstat, rstat);
797 }
798 return(FUNCTION_TERMINATED_NORMALLY);
799 }
800
801 /*===========================================================================*/
802 /* is_last_iter == TRUE ==> it is the last iteration before branching. However
803 * if a solutiion is found by the following heuristics, then this may no
804 * longer be a last call. */
is_feasible_u(lp_prob * p,char branching,char is_last_iter)805 int is_feasible_u(lp_prob *p, char branching, char is_last_iter)
806 {
807 #ifndef COMPILE_IN_LP
808 int s_bufid;
809 #endif
810 int user_res;
811 int feasible = IP_INFEASIBLE;
812 double true_objval = p->lp_data->objval;
813 LPdata *lp_data = p->lp_data;
814 double lpetol = lp_data->lpetol;
815 //double lpetol100 = lpetol*100, lpetol1 = 1 - lpetol100;
816 double lpetol100 = lpetol, lpetol1 = 1 - lpetol100;
817 int *indices;
818 double *values, valuesi, *heur_solution = NULL, *col_sol = NULL,
819 new_obj_val;
820 int cnt, i, termcode;
821 var_desc **vars = lp_data->vars;
822 char found_better_solution;
823 char force_heur_sol = FALSE;
824 int should_call_fp = FALSE;
825 double *x;
826 int n = lp_data->n;
827 double gran_round;
828 int do_primal_heuristic = FALSE, check_ls = TRUE;
829 double t_lb = p->lp_data->objval;
830
831 //get_x(lp_data); /* maybe just fractional -- parameter ??? */
832
833 indices = lp_data->tmp.i1; /* n */
834 values = lp_data->tmp.d; /* n */
835
836 double dual_gap = 100;
837
838 heur_solution = p->lp_data->heur_solution;
839 col_sol = p->lp_data->col_solution;
840
841 #ifdef USE_SYM_APPLICATION
842 cnt = collect_nonzeros(p, lp_data->x, indices, values);
843 user_res = user_is_feasible(p->user, lpetol, cnt, indices, values,
844 &feasible, &true_objval, branching,
845 heur_solution);
846 #else
847 user_res = USER_DEFAULT;
848 #endif
849
850 switch (user_res){
851 case USER_ERROR: /* Error. Consider as feasibility not recognized. */
852 return(FALSE);
853 case USER_SUCCESS:
854 case USER_AND_PP:
855 case USER_NO_PP:
856 if (feasible == IP_HEUR_FEASIBLE){
857 memcpy(col_sol, heur_solution, DSIZE*lp_data->n);
858 if(true_objval > t_lb + lpetol100){
859 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
860 p->mip->obj_sense);
861 }else{
862 dual_gap = 1e-4;
863 }
864 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
865 check_ls = FALSE;
866 }
867 break;
868 case USER_DEFAULT: /* set the default */
869 user_res = TEST_INTEGRALITY;
870 if (feasible != IP_INFEASIBLE){
871 printf("Warning: User set feasibility status of solution, but\n");
872 printf("SYMPHONY to check feasibility. Ignoring request.");
873 user_res = USER_SUCCESS;
874 }
875 break;
876 default:
877 break;
878 }
879
880 switch (user_res){
881 case TEST_ZERO_ONE: /* User wants us to test 0/1 -ness. */
882 cnt = collect_nonzeros(p, lp_data->x, indices, values);
883 for (i=cnt-1; i>=0; i--){
884 if (!vars[indices[i]]->is_int)
885 continue; /* Not an integer variable */
886 if (values[i] < lpetol1) break;
887 }
888 feasible = i < 0 ? IP_FEASIBLE : IP_INFEASIBLE;
889 break;
890 case TEST_INTEGRALITY:
891 x = lp_data->x;
892 for (i = n - 1; i >= 0; i--){
893 if (!vars[i]->is_int)
894 continue; /* Not an integer variable */
895 valuesi = x[i];
896 if (valuesi-floor(valuesi) > lpetol100 &&
897 ceil(valuesi)-valuesi > lpetol100 &&
898 valuesi>vars[i]->lb-lpetol && valuesi<vars[i]->ub+lpetol){
899 break;
900 }
901 }
902 feasible = i < 0 ? IP_FEASIBLE : IP_INFEASIBLE;
903 break;
904 default:
905 break;
906 }
907
908 #ifdef COMPILE_IN_LP
909
910 if(p->bc_index < 1 && p->lp_stat.lp_calls < 2){
911 memcpy(p->root_lp, lp_data->x, DSIZE*n);
912 }
913
914 if(p->tm->stat.analyzed > 1){
915 //find_tree_lb(p->tm);
916 t_lb = MIN(t_lb, p->tm->lb);
917 }
918
919 if (user_res == TEST_INTEGRALITY && feasible != IP_FEASIBLE && feasible != IP_HEUR_FEASIBLE &&
920 p->par.do_primal_heuristic && !p->par.multi_criteria){
921
922 if (feasible == IP_INFEASIBLE){
923 true_objval = SYM_INFINITY;
924 }
925
926 p->var_rank_cnt++;
927 for(i = 0; i < n; i++){
928
929 p->var_rank[i] += (fabs(x[i] - floor(x[i] + lpetol100)) > lpetol100 ? 1.0 : 0.0);
930
931 }
932
933 if(p->has_ub){
934 if(p->ub > t_lb + lpetol100){
935 dual_gap = d_gap(p->ub, t_lb,
936 p->mip->obj_offset, p->mip->obj_sense);
937 }else dual_gap = 1e-4;
938 true_objval = p->ub;
939 }
940
941 do_primal_heuristic = TRUE;
942 }
943
944 if(do_primal_heuristic){
945 /* try rounding first */
946
947 if (p->has_ub){
948 memset(col_sol, 0, DSIZE*lp_data->n);
949 for(i = 0; i< p->best_sol.xlength; i++) {
950 col_sol[p->best_sol.xind[i]] = p->best_sol.xval[i];
951 }
952 }
953
954 if(p->par.rounding_enabled && dual_gap > p->par.rounding_min_gap){
955
956 if (round_solution(p, p->lp_data, &true_objval, heur_solution, t_lb)){
957 feasible = IP_HEUR_FEASIBLE;
958 memcpy(col_sol, heur_solution, DSIZE*lp_data->n);
959 if(true_objval > t_lb + lpetol100){
960 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
961 p->mip->obj_sense);
962 }else{
963 dual_gap = 1e-4;
964 }
965 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
966 check_ls = FALSE;
967 }
968 }
969
970 if(feasible != IP_HEUR_FEASIBLE && p->par.shifting_enabled && dual_gap > p->par.shifting_min_gap &&
971 p->bc_level % 5 == 0){
972 if (shift_solution(p, p->lp_data, &true_objval, heur_solution, t_lb)){
973 feasible = IP_HEUR_FEASIBLE;
974 memcpy(col_sol, heur_solution, DSIZE*lp_data->n);
975 if(true_objval > t_lb + lpetol100){
976 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
977 p->mip->obj_sense);
978 }else{
979 dual_gap = 1e-4;
980 }
981 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
982 check_ls = FALSE;
983 }
984 }
985
986 if((!p->par.disable_obj || (p->par.disable_obj && p->bc_level < 10)) &&
987 p->par.ds_enabled && dual_gap > p->par.ds_min_gap && !branching &&
988 (p->bc_level % p->par.ds_frequency == 0) && is_last_iter ){// && p->bc_level < 1){ //}
989 if (diving_search(p, &true_objval, col_sol, heur_solution, is_last_iter, t_lb)){
990 feasible = IP_HEUR_FEASIBLE;
991 memcpy(col_sol, heur_solution, DSIZE*lp_data->n);
992 if(true_objval > t_lb + lpetol100){
993 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
994 p->mip->obj_sense);
995 }else{
996 dual_gap = 1e-4;
997 }
998 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
999 check_ls = FALSE;
1000 }
1001 }
1002
1003 if (user_res == TEST_INTEGRALITY && feasible != IP_FEASIBLE && feasible != IP_HEUR_FEASIBLE) {
1004 fp_should_call_fp(p,branching,&should_call_fp,is_last_iter, t_lb);
1005 if (should_call_fp==TRUE && (!p->par.disable_obj || (p->par.disable_obj && p->bc_level < 10)) &&
1006 ((p->bc_level >= 1 && p->lp_stat.fp_last_call_ind != p->bc_index) ||
1007 (p->bc_level < 1 && p->lp_stat.fp_calls < 1))){
1008 new_obj_val = true_objval;
1009 termcode = feasibility_pump (p, &found_better_solution,
1010 new_obj_val, col_sol, heur_solution);
1011
1012 if (termcode!=FUNCTION_TERMINATED_NORMALLY) {
1013 PRINT(p->par.verbosity,0,("warning: feasibility pump faced some "
1014 "difficulties.\n"));
1015 } else if (found_better_solution) {
1016 feasible = IP_HEUR_FEASIBLE;
1017 true_objval = new_obj_val;
1018 memcpy(col_sol, heur_solution, DSIZE*lp_data->n);
1019 if(true_objval > t_lb + lpetol100){
1020 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
1021 p->mip->obj_sense);
1022 }else{
1023 dual_gap = 1e-4;
1024 }
1025 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
1026 check_ls = FALSE;
1027 }
1028 }
1029 }
1030
1031 int reg_factor = (int)(p->tm->stat.analyzed/100.0);
1032 int reg_base = p->tm->stat.analyzed;
1033 if(reg_factor <= 5){
1034 reg_factor += p->par.fr_frequency;
1035 reg_base = p->bc_level;
1036 }else if(reg_factor <= 10){
1037 reg_factor = MAX(20, 4*p->par.fr_frequency);
1038 }else{
1039 reg_factor = MAX(100, 20*p->par.fr_frequency);
1040 }
1041
1042 double rs_min_gap = 0.5;
1043 if(p->bc_index >= 0) rs_min_gap = p->par.rs_min_gap;
1044
1045 if((!p->par.disable_obj || (p->par.disable_obj && p->bc_level < 10)) &&
1046 p->par.rs_enabled && dual_gap > rs_min_gap && !branching && p->par.rs_dive_level > 0 &&
1047 is_last_iter &&
1048 (p->lp_stat.rs_calls - p->lp_stat.rs_last_sol_call <= 20) &&
1049 (p->tm->stat.analyzed < 10000 ||
1050 (p->tm->stat.analyzed < 100000 && !p->has_ub)) &&
1051 (p->bc_level < 1 || reg_factor % reg_base == 0)){
1052 if(restricted_search (p, &true_objval, col_sol, heur_solution, RINS_SEARCH, t_lb)){
1053 feasible = IP_HEUR_FEASIBLE;
1054 memcpy(col_sol, heur_solution, DSIZE*lp_data->n);
1055 if(true_objval > t_lb + lpetol100){
1056 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
1057 p->mip->obj_sense);
1058 }else{
1059 dual_gap = 1e-4;
1060 }
1061 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
1062 check_ls = FALSE;
1063 }
1064 }
1065
1066 double fr_min_gap = 0.5;
1067 if(p->bc_index >= 0) fr_min_gap = p->par.fr_min_gap;
1068
1069 if((!p->par.disable_obj || (p->par.disable_obj && p->bc_level < 10)) &&
1070 p->par.fr_enabled && dual_gap > fr_min_gap && !branching && p->par.fr_dive_level > 0 &&
1071 is_last_iter && //p->bc_level < 1 &&
1072 (p->lp_stat.fr_calls - p->lp_stat.fr_last_sol_call <= 20) &&
1073 (p->bc_level < 1 || (reg_factor % reg_base == 0)) &&
1074 (p->tm->stat.analyzed < 10000 ||
1075 (p->tm->stat.analyzed < 100000 && !p->has_ub))){
1076
1077 if(restricted_search (p, &true_objval, col_sol, heur_solution, FR_SEARCH, t_lb)){
1078 feasible = IP_HEUR_FEASIBLE;
1079 memcpy(col_sol, heur_solution, DSIZE*lp_data->n); //no need --
1080 if(true_objval > t_lb + lpetol100){
1081 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
1082 p->mip->obj_sense);
1083 }else{
1084 dual_gap = 1e-4;
1085 }
1086 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
1087 check_ls = FALSE;
1088 }
1089 }
1090 }
1091
1092 if(user_res == TEST_INTEGRALITY &&
1093 p->par.do_primal_heuristic && (feasible == IP_FEASIBLE || feasible == IP_HEUR_FEASIBLE) &&
1094 (p->par.ls_enabled || p->par.lb_enabled) && !p->par.multi_criteria){
1095
1096 if(feasible == IP_FEASIBLE){
1097 memcpy(col_sol, p->lp_data->x, DSIZE*lp_data->n);
1098 if(true_objval > t_lb + lpetol100){
1099 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
1100 p->mip->obj_sense);
1101 }else{
1102 dual_gap = 1e-4;
1103 }
1104 }
1105
1106 if(check_ls){
1107 if(apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb)){
1108 if(feasible == IP_FEASIBLE) force_heur_sol = TRUE;
1109 }
1110 }
1111
1112 double lb_min_gap = p->par.lb_min_gap;
1113
1114 if(p->par.lb_enabled && dual_gap > lb_min_gap && p->par.lb_dive_level > 0){
1115 if(lbranching_search (p, &true_objval, col_sol, heur_solution, t_lb)){
1116 if(feasible == IP_FEASIBLE) force_heur_sol = TRUE;
1117 memcpy(col_sol, heur_solution, DSIZE*lp_data->n);
1118 if(true_objval > t_lb + lpetol100){
1119 dual_gap = d_gap(true_objval, t_lb, p->mip->obj_offset,
1120 p->mip->obj_sense);
1121 }else{
1122 dual_gap = 1e-4;
1123 }
1124 /* do local search inside lbranching */
1125 apply_local_search(p, &true_objval, col_sol, heur_solution, &dual_gap, t_lb);
1126 }
1127 }
1128 }
1129
1130 #endif
1131
1132 if ((feasible == IP_FEASIBLE || feasible == IP_HEUR_FEASIBLE)
1133 && p->par.multi_criteria){
1134 if (feasible == IP_HEUR_FEASIBLE || force_heur_sol) {
1135 cnt = collect_nonzeros(p, heur_solution, indices, values);
1136 } else {
1137 cnt = collect_nonzeros(p, lp_data->x, indices, values);
1138 }
1139 if (analyze_multicriteria_solution(p, indices, values, cnt,
1140 &true_objval, lpetol, branching,
1141 feasible) > 0){
1142 if(feasible == IP_FEASIBLE &&
1143 (p->par.mc_add_optimality_cuts || branching)){
1144 feasible = IP_FEASIBLE_BUT_CONTINUE;
1145 }
1146 }
1147 }
1148
1149 if (feasible == IP_FEASIBLE || feasible == IP_FEASIBLE_BUT_CONTINUE ||
1150 feasible == IP_HEUR_FEASIBLE){
1151 if (feasible == IP_HEUR_FEASIBLE || force_heur_sol) {
1152 cnt = collect_nonzeros(p, heur_solution, indices, values);
1153 } else {
1154 cnt = collect_nonzeros(p, lp_data->x, indices, values);
1155 }
1156 gran_round = p->par.granularity;
1157 gran_round = floor(gran_round + 0.5);
1158 if (p->par.granularity > lpetol100 &&
1159 fabs(gran_round-p->par.granularity) < lpetol100) {
1160 /* we have granularity. symphony now uses granularity to set ub on
1161 * lp-solver using granularity. so we round the solution to the
1162 * nearest integer so that this tighter ub does not cut off other
1163 * good solutions.
1164 */
1165 true_objval = floor(true_objval+0.5);
1166 }
1167
1168 /* Send the solution value to the treemanager */
1169 if (p->has_ub && true_objval >= p->ub - p->par.granularity){
1170 if (!p->par.multi_criteria){
1171 PRINT(p->par.verbosity, 0,
1172 ("\n* Found Another Feasible Solution.\n"));
1173 if (p->mip->obj_sense == SYM_MAXIMIZE){
1174 PRINT(p->par.verbosity, 0, ("* Cost: %f\n\n", -true_objval
1175 + p->mip->obj_offset));
1176 }else{
1177 PRINT(p->par.verbosity, 0, ("****** Cost: %f\n\n", true_objval
1178 + p->mip->obj_offset));
1179 }
1180 }
1181 return(feasible);
1182 }
1183 p->has_ub = TRUE;
1184 p->ub = true_objval;
1185 #ifdef COMPILE_IN_LP
1186 p->tm->lp_stat.ip_sols++;
1187 #endif
1188 if (p->par.set_obj_upper_lim) {
1189 set_obj_upper_lim(p->lp_data, p->ub - p->par.granularity + lpetol);
1190 }
1191 if (!p->par.multi_criteria){
1192 p->best_sol.xlevel = p->bc_level;
1193 p->best_sol.xindex = p->bc_index;
1194 p->best_sol.xiter_num = p->iter_num;
1195 p->best_sol.xlength = cnt;
1196 p->best_sol.lpetol = lpetol;
1197 p->best_sol.objval = true_objval;
1198 FREE(p->best_sol.xind);
1199 FREE(p->best_sol.xval);
1200 if(cnt){
1201 p->best_sol.xind = (int *) malloc(cnt*ISIZE);
1202 p->best_sol.xval = (double *) malloc(cnt*DSIZE);
1203 memcpy((char *)p->best_sol.xind, (char *)indices, cnt*ISIZE);
1204 memcpy((char *)p->best_sol.xval, (char *)values, cnt*DSIZE);
1205 }
1206 if(!p->best_sol.has_sol)
1207 p->best_sol.has_sol = TRUE;
1208 PRINT(p->par.verbosity, 0,
1209 ("\n****** Found Better Feasible Solution !\n"));
1210 if (feasible == IP_HEUR_FEASIBLE){
1211 PRINT(p->par.verbosity, 2,
1212 ("****** After Calling Heuristics !\n"));
1213 }
1214 if (p->mip->obj_sense == SYM_MAXIMIZE){
1215 PRINT(p->par.verbosity, 0, ("****** Cost: %f\n\n", -true_objval
1216 + p->mip->obj_offset));
1217 }else{
1218 PRINT(p->par.verbosity, 0, ("****** Cost: %f\n\n", true_objval
1219 + p->mip->obj_offset));
1220 }
1221 }
1222 #ifdef COMPILE_IN_LP
1223 #pragma omp critical (new_ub)
1224 {
1225 install_new_ub(p->tm, p->ub, p->proc_index, p->bc_index, branching,
1226 feasible);
1227 }
1228 #if 0
1229 if (p->bc_index>0) {
1230 tighten_root_bounds(p);
1231 }
1232 #endif
1233 if (!p->par.multi_criteria){
1234 display_lp_solution_u(p, DISP_FEAS_SOLUTION);
1235 }
1236 sp_add_solution(p,cnt,indices,values,true_objval+p->mip->obj_offset,
1237 p->bc_index);
1238 #else
1239 s_bufid = init_send(DataInPlace);
1240 send_dbl_array(&true_objval, 1);
1241 send_int_array(&(p->bc_index), 1);
1242 send_int_array(&feasible, 1);
1243 send_char_array(&branching, 1);
1244 send_msg(p->tree_manager, UPPER_BOUND);
1245 freebuf(s_bufid);
1246 #endif
1247 #if !defined(COMPILE_IN_LP) || !defined(COMPILE_IN_TM)
1248 send_feasible_solution_u(p, p->bc_level, p->bc_index, p->iter_num,
1249 lpetol, true_objval, cnt, indices, values);
1250 #endif
1251 }
1252
1253 if (feasible == IP_FEASIBLE){
1254 lp_data->termcode = LP_OPT_FEASIBLE;
1255 p->lp_stat.lp_sols++;
1256 //#ifdef COMPILE_IN_LP
1257 // sp_add_solution(p,cnt,indices,values,true_objval+p->mip->obj_offset,
1258 // p->bc_index);
1259 //#endif
1260 }
1261
1262 #if 0
1263 if(is_last_iter){
1264 for (i=p->lp_data->mip->n-1; i>=0; i--){
1265 if (vars[i]->is_int)
1266 p->lp_data->si->setInteger(i);
1267 }
1268 write_mps(p->lp_data, "test");
1269 }
1270 #endif
1271 //printf("feasible: solution = %f\n", lp_data->objval);
1272 return(feasible);
1273 }
1274
1275 /*===========================================================================*/
1276
send_feasible_solution_u(lp_prob * p,int xlevel,int xindex,int xiter_num,double lpetol,double new_ub,int cnt,int * xind,double * xval)1277 void send_feasible_solution_u(lp_prob *p, int xlevel, int xindex,
1278 int xiter_num, double lpetol, double new_ub,
1279 int cnt, int *xind, double *xval)
1280 {
1281 int s_bufid, msgtag, user_res;
1282
1283 /* Send to solution to the master */
1284 s_bufid = init_send(DataInPlace);
1285 send_int_array(&xlevel, 1);
1286 send_int_array(&xindex, 1);
1287 send_int_array(&xiter_num, 1);
1288 send_dbl_array(&lpetol, 1);
1289 send_dbl_array(&new_ub, 1);
1290 send_int_array(&cnt, 1);
1291 if (cnt > 0){
1292 send_int_array(xind, cnt);
1293 send_dbl_array(xval, cnt);
1294 }
1295 #ifdef USE_SYM_APPLICATION
1296 user_res = user_send_feasible_solution(p->user, lpetol, cnt, xind, xval);
1297 #else
1298 user_res = USER_DEFAULT;
1299 #endif
1300
1301 switch (user_res){
1302 case USER_SUCCESS:
1303 case USER_AND_PP:
1304 case USER_NO_PP:
1305 break;
1306 case USER_ERROR: /* Error. Do the default */
1307 case USER_DEFAULT: /* set the default */
1308 user_res = p->par.send_feasible_solution_default;
1309 break;
1310 }
1311 switch (user_res){
1312 case SEND_NONZEROS:
1313 msgtag = FEASIBLE_SOLUTION_NONZEROS;
1314 break;
1315 default: /* Otherwise the user packed it */
1316 msgtag = FEASIBLE_SOLUTION_USER;
1317 break;
1318 }
1319 send_msg(p->master, msgtag);
1320 freebuf(s_bufid);
1321 }
1322
1323 /*===========================================================================*/
1324
1325 /*===========================================================================*\
1326 * This function invokes the user written function user_display_solution
1327 * that (graphically) displays the current solution.
1328 \*===========================================================================*/
1329
display_lp_solution_u(lp_prob * p,int which_sol)1330 void display_lp_solution_u(lp_prob *p, int which_sol)
1331 {
1332 int user_res;
1333 LPdata *lp_data = p->lp_data;
1334 double *x = lp_data->x;
1335 double lpetol = lp_data->lpetol;
1336
1337 int number = 0;
1338 int i, *xind = lp_data->tmp.i1; /* n */
1339 double tmpd, *xval = lp_data->tmp.d; /* n */
1340
1341 if (p->par.verbosity < 0) return;
1342
1343 number = collect_nonzeros(p, x, xind, xval);
1344
1345 /* Invoke user written function. */
1346 #ifdef USE_SYM_APPLICATION
1347 user_res = user_display_lp_solution(p->user, which_sol, number, xind, xval);
1348 #else
1349 user_res = USER_DEFAULT;
1350 #endif
1351
1352 switch(user_res){
1353 case USER_ERROR:
1354 /* SYMPHONY ignores error message. */
1355 return;
1356 case USER_AND_PP:
1357 case USER_NO_PP:
1358 /* User function terminated without problems. No post-processing. */
1359 return;
1360 case USER_DEFAULT:
1361 user_res = p->par.display_solution_default;
1362 break;
1363 default:
1364 break;
1365 }
1366
1367 switch(user_res){
1368 case DISP_NOTHING:
1369 break;
1370 case DISP_NZ_INT:
1371 if (p->mip->colname){
1372 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1373 printf(" Column names and values of nonzeros in the solution\n");
1374 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1375 for (i = 0; i < number; i++){
1376 if (xind[i] == p->mip->n) continue; /* For multi-criteria */
1377 printf("%-50s %10.7f\n", p->mip->colname[xind[i]], xval[i]);
1378 }
1379 printf("\n");
1380 }else{
1381 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1382 printf(" User indices and values of nonzeros in the solution\n");
1383 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1384 for (i = 0; i < number; i++){
1385 if (xind[i] == p->mip->n) continue; /* For multi-criteria */
1386 printf("%7d %10.7f\n", xind[i], xval[i]);
1387 }
1388 printf("\n");
1389 }
1390 break;
1391 case DISP_NZ_HEXA:
1392 printf("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1393 printf(" User indices (hexa) and values of nonzeros in the solution\n");
1394 printf("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1395 for (i = 0; i < number; i++){
1396 if (xind[i] == p->mip->n) continue; /* For multi-criteria */
1397 printf("%7x %10.7f ", xind[i], xval[i]);
1398 if (!(++i & 3)) printf("\n"); /* new line after every four pair*/
1399 }
1400 printf("\n");
1401 break;
1402 case DISP_FRAC_INT:
1403 if (p->mip->colname){
1404 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1405 printf(" Column names and values of fractional vars in solution\n");
1406 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1407 for (i = 0; i < number; i++){
1408 if (xind[i] == p->mip->n) continue; /* For multi-criteria */
1409 tmpd = xval[i];
1410 if ((tmpd > floor(tmpd)+lpetol) && (tmpd < ceil(tmpd)-lpetol)){
1411 printf("%-50s %10.7f\n", p->mip->colname[xind[i]], tmpd);
1412 }
1413 }
1414 printf("\n");
1415 }else{
1416 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1417 printf(" User indices and values of fractional vars in solution\n");
1418 printf("+++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1419 for (i = 0; i < number; i++){
1420 if (xind[i] == p->mip->n) continue; /* For multi-criteria */
1421 tmpd = xval[i];
1422 if ((tmpd > floor(tmpd)+lpetol) && (tmpd < ceil(tmpd)-lpetol)){
1423 printf("%7d %10.7f ", xind[i], tmpd);
1424 if (!(++i & 3)) printf("\n"); /* new line after every four*/
1425 }
1426 }
1427 }
1428 printf("\n");
1429 break;
1430 case DISP_FRAC_HEXA:
1431 printf("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1432 printf(" User indices (hexa) and values of frac vars in the solution\n");
1433 printf("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
1434 for (i = 0; i < number; i++){
1435 if (xind[i] == p->mip->n) continue; /* For multi-criteria */
1436 tmpd = xval[i];
1437 if ((tmpd > floor(tmpd)+lpetol) && (tmpd < ceil(tmpd)-lpetol)){
1438 printf("%7x %10.7f ", xind[i], tmpd);
1439 if (!(++i & 3)) printf("\n"); /* new line after every four pair*/
1440 }
1441 }
1442 printf("\n");
1443 break;
1444 default:
1445 /* Unexpected return value. Do something!! */
1446 break;
1447 }
1448 }
1449
1450 /*===========================================================================*/
1451
1452 /*===========================================================================*\
1453 * This function invokes the user written function user_branch that selects
1454 * candidates to branch on. It receives a number of arguments:
1455 * sim_num : slacks in matrix number (the
1456 \*===========================================================================*/
1457
select_candidates_u(lp_prob * p,int * cuts,int * new_vars,int * cand_num,branch_obj *** candidates)1458 int select_candidates_u(lp_prob *p, int *cuts, int *new_vars,
1459 int *cand_num, branch_obj ***candidates)
1460 {
1461 int user_res, action = USER__BRANCH_IF_MUST;
1462 LPdata *lp_data = p->lp_data;
1463 row_data *rows = lp_data->rows;
1464 int i, j = 0, m = lp_data->m;
1465 int *candidate_rows;
1466 branch_obj *can;
1467 cut_data **slacks_in_matrix = NULL; /* just to keep gcc quiet */
1468
1469 /* If the user might need to generate rows, we better have the
1470 * columns COLIND_ORDERED */
1471 colind_sort_extra(p);
1472
1473 candidate_rows = lp_data->tmp.i2; /* m */
1474 if (p->par.branch_on_cuts){
1475 slacks_in_matrix = (cut_data **)lp_data->tmp.p2; /* m */
1476 /* get a list of row that are candidates for branching */
1477 for (i=0; i<m; i++){ /* can't branch on original rows */
1478 if ((rows[i].cut->branch & CANDIDATE_FOR_BRANCH)){
1479 slacks_in_matrix[j] = rows[i].cut;
1480 candidate_rows[j++] = i;
1481 }
1482 }
1483 }
1484
1485 /* First decide if we are going to branch or not */
1486 #ifdef USE_SYM_APPLICATION
1487 user_res = user_shall_we_branch(p->user, lp_data->lpetol, *cuts, j,
1488 slacks_in_matrix, p->slack_cut_num,
1489 p->slack_cuts, lp_data->n, lp_data->vars,
1490 lp_data->x, lp_data->status, cand_num,
1491 candidates, &action);
1492 check_tailoff(p);
1493 #else
1494 user_res = USER_DEFAULT;
1495 #endif
1496
1497 switch (user_res){
1498 case USER_SUCCESS:
1499 case USER_AND_PP:
1500 case USER_NO_PP:
1501 break;
1502 case USER_ERROR: /* In case of error, default is used. */
1503 case USER_DEFAULT:
1504 action = p->par.shall_we_branch_default;
1505 break;
1506 }
1507
1508 if (p->bc_level <= p->par.load_balance_level &&
1509 p->node_iter_num >= p->par.load_balance_iterations)
1510 action = USER__DO_BRANCH;
1511
1512 if ((action == USER__DO_NOT_BRANCH) ||
1513 (p->bound_changes_in_iter>0) ||
1514 (action == USER__BRANCH_IF_TAILOFF && *cuts > 0 && p->has_tailoff==FALSE) ||
1515 (action == USER__BRANCH_IF_MUST && *cuts > 0))
1516 return(DO_NOT_BRANCH);
1517
1518 p->comp_times.strong_branching += used_time(&p->tt);
1519
1520 {
1521 /* it seems we are going to branch. Before doing that, we should invoke
1522 * heuristics. */
1523 if (p->bc_index < 1) {
1524 double oldobj = (p->has_ub ? p->ub : SYM_INFINITY);
1525 int feas_status = is_feasible_u(p, FALSE, TRUE);
1526 p->comp_times.primal_heur += used_time(&p->tt);
1527 if (feas_status == IP_FEASIBLE || (feas_status==IP_HEUR_FEASIBLE &&
1528 p->ub < oldobj - lp_data->lpetol)){// && //){
1529 // *cuts > 0)){
1530 return(DO_NOT_BRANCH__FEAS_SOL);
1531 }
1532 }
1533 }
1534
1535
1536 action = col_gen_before_branch(p, new_vars);
1537 /* vars might have been added, so tmp arrays might be freed/malloc'd,
1538 but only those where maxn plays any role in the size. Therefore tmp.i2
1539 and tmp.p2 do NOT change. Phew... */
1540
1541 if (action == DO_NOT_BRANCH__FATHOMED)
1542 return(DO_NOT_BRANCH__FATHOMED);
1543
1544 /* In the other two cases we may have to re-generate the rows
1545 corresponding to slacks not in the matrix (whether violated
1546 slacks or branching candidates), depending on new_vars */
1547 if (*new_vars > 0 && *cand_num > 0){
1548 cut_data **regen_cuts = (cut_data **) malloc(*cand_num*sizeof(cut_data));
1549 for (j = 0, i = 0; i < *cand_num; i++){
1550 can = (*candidates)[i];
1551 if (can->type == VIOLATED_SLACK ||
1552 can->type == CANDIDATE_CUT_NOT_IN_MATRIX){
1553 regen_cuts[j++] = can->row->cut;
1554 }
1555 }
1556 if (j > 0){
1557 int new_row_num;
1558 waiting_row **new_rows;
1559 unpack_cuts_u(p, CUT_FROM_TM, UNPACK_CUTS_SINGLE,
1560 j, regen_cuts, &new_row_num, &new_rows);
1561 for (j = 0, i = 0; i < *cand_num; i++){
1562 can = (*candidates)[i];
1563 if (can->type == VIOLATED_SLACK ||
1564 can->type == CANDIDATE_CUT_NOT_IN_MATRIX){
1565 free_waiting_row(&can->row);
1566 can->row = new_rows[j++];
1567 }
1568 }
1569 FREE(new_rows);
1570 }
1571 FREE(regen_cuts);
1572 }
1573
1574 if (action == DO_NOT_BRANCH)
1575 return(DO_NOT_BRANCH);
1576
1577 /* So the action from col_gen_before_branch is DO_BRANCH */
1578
1579 action = USER__DO_BRANCH;
1580
1581 /* before branching, update the control parameters for cut generation
1582 * --asm4
1583 */
1584 // if (p->bc_level==0) {
1585 //update_cut_parameters(p);
1586 // }
1587
1588 /* OK, so we got to branch */
1589 #ifdef USE_SYM_APPLICATION
1590 user_res = user_select_candidates(p->user, lp_data->lpetol, *cuts, j,
1591 slacks_in_matrix, p->slack_cut_num,
1592 p->slack_cuts, lp_data->n, lp_data->vars,
1593 lp_data->x, lp_data->status, cand_num,
1594 candidates, &action, p->bc_level);
1595 #else
1596 user_res = USER_DEFAULT;
1597 #endif
1598
1599 /* Get rid of any contsraint from slack_cuts which is listed in candidates
1600 * and rewrite the position of the CANDIDATE_CUT_IN_MATRIX ones */
1601 if (p->par.branch_on_cuts){
1602 for (i = 0; i < *cand_num; ){
1603 can = (*candidates)[i];
1604 switch (can->type){
1605 case CANDIDATE_VARIABLE:
1606 i++;
1607 break;
1608 case CANDIDATE_CUT_IN_MATRIX:
1609 can->position = candidate_rows[can->position];
1610 i++;
1611 break;
1612 case VIOLATED_SLACK:
1613 case CANDIDATE_CUT_NOT_IN_MATRIX:
1614 free_cut(p->slack_cuts + can->position);
1615 i++;
1616 break;
1617 case SLACK_TO_BE_DISCARDED:
1618 free_cut(p->slack_cuts + can->position);
1619 free_candidate(*candidates + i);
1620 (*candidates)[i] = (*candidates)[--(*cand_num)];
1621 break;
1622 }
1623 }
1624 compress_slack_cuts(p);
1625 }
1626
1627 if (action == USER__DO_NOT_BRANCH)
1628 return(DO_NOT_BRANCH);
1629
1630 switch(user_res){
1631 case USER_SUCCESS:
1632 case USER_AND_PP:
1633 case USER_NO_PP:
1634 if (! *cand_num){
1635 printf("Error! User didn't select branching candidates!\n");
1636 return(ERROR__NO_BRANCHING_CANDIDATE);
1637 }
1638 return(DO_BRANCH);
1639 case USER_ERROR: /* In case of error, default is used. */
1640 case USER_DEFAULT:
1641 user_res = p->par.select_candidates_default;
1642 break;
1643 default:
1644 break;
1645 }
1646
1647 i = (int) (p->par.strong_branching_cand_num_max -
1648 p->par.strong_branching_red_ratio * p->bc_level);
1649 i = MAX(i, p->par.strong_branching_cand_num_min);
1650
1651 switch(user_res){
1652 case USER__CLOSE_TO_HALF:
1653 branch_close_to_half(p, i, cand_num, candidates);
1654 break;
1655 case USER__CLOSE_TO_HALF_AND_EXPENSIVE:
1656 branch_close_to_half_and_expensive(p, i, cand_num, candidates);
1657 break;
1658 case USER__CLOSE_TO_ONE_AND_CHEAP:
1659 branch_close_to_one_and_cheap(p, i, cand_num, candidates);
1660 break;
1661
1662 default:
1663 /* Unexpected return value. Do something!! */
1664 break;
1665 }
1666
1667 if (! *cand_num){
1668 PRINT(p->par.verbosity, 2,
1669 ("No branching candidates found using default rule...\n"));
1670 return(DO_NOT_BRANCH);
1671 }
1672 return(DO_BRANCH);
1673 }
1674
1675 /*===========================================================================*/
1676
1677 /*===========================================================================*\
1678 * This function invokes the user written function user_compare_candidates
1679 * that compares to branching candidates.
1680 \*===========================================================================*/
1681
compare_candidates_u(lp_prob * p,double oldobjval,branch_obj * best,branch_obj * can)1682 int compare_candidates_u(lp_prob *p, double oldobjval,
1683 branch_obj *best, branch_obj *can)
1684 {
1685 int user_res;
1686 int i;
1687 double low0, low1, high0, high1;
1688 double lpetol = p->lp_data->lpetol;
1689 const double ub_minus_gran = p->ub - p->par.granularity;
1690 const double alpha = p->par.strong_branching_high_low_weight;
1691 const double infinity = SYM_INFINITY;
1692 #ifdef COMPILE_FRAC_BRANCHING
1693 int frl0, frl1, frh0, frh1;
1694 #endif
1695 for (i = can->child_num-1; i >= 0; i--){
1696 switch (can->termcode[i]){
1697 case LP_OPTIMAL:
1698 case LP_OPT_FEASIBLE_BUT_CONTINUE:
1699 #ifdef DO_TESTS
1700 if (can->objval[i] < oldobjval - .01){
1701 printf("#####Error: Branching candidate has lower objval ");
1702 printf("(%.3f) than parent (%.3f)\n", can->objval[i], oldobjval);
1703 }
1704 #endif
1705 break;
1706 case LP_OPT_FEASIBLE:
1707 case LP_D_UNBOUNDED:
1708 case LP_D_OBJLIM:
1709 can->objval[i] = MAXDOUBLE / 2;
1710 break;
1711 case LP_D_ITLIM:
1712 can->objval[i] = MAX(can->objval[i], oldobjval);
1713 break;
1714 case LP_D_INFEASIBLE:
1715 case LP_ABANDONED:
1716 can->objval[i] = oldobjval;
1717 break;
1718 }
1719 }
1720
1721 /*------------------------------------------------------------------------*\
1722 * If ALL descendants in cand terminated with primal infeasibility
1723 * or high cost, that proves that the current node can be fathomed,
1724 * so we select cand and force branching on it.
1725 *
1726 * MAYBE THIS SHOULD BE LEFT TO THE USER ?????????????????
1727 \*------------------------------------------------------------------------*/
1728
1729 for (i = can->child_num-1; i >= 0; i--){
1730 if (! (can->termcode[i] == LP_D_UNBOUNDED ||
1731 can->termcode[i] == LP_D_OBJLIM ||
1732 can->termcode[i] == LP_OPT_FEASIBLE ||
1733 can->termcode[i] == LP_OPT_FEASIBLE_BUT_CONTINUE ||
1734 (can->termcode[i] == LP_OPTIMAL && p->has_ub &&
1735 can->objval[i] > ub_minus_gran))){
1736 break;
1737 }
1738 }
1739
1740 if (i < 0){
1741 /* i.e., we did not break, i.e., we'll select this cand */
1742 return(SECOND_CANDIDATE_BETTER_AND_BRANCH_ON_IT);
1743 }
1744
1745 /* If this is the first, keep it */
1746 if (best == NULL){
1747 return(SECOND_CANDIDATE_BETTER);
1748 }
1749
1750 /* Otherwise, first give the choice to the user */
1751 #ifdef USE_SYM_APPLICATION
1752 user_res = user_compare_candidates(p->user, best, can, p->ub,
1753 p->par.granularity, &i);
1754
1755 #else
1756 user_res = USER_DEFAULT;
1757 #endif
1758
1759 switch(user_res){
1760 case USER_SUCCESS:
1761 case USER_AND_PP:
1762 case USER_NO_PP:
1763 /* User function terminated without problems. No post-processing. */
1764 return(i);
1765 case USER_ERROR:
1766 /* In case of error, default is used. */
1767 case USER_DEFAULT:
1768 user_res = p->par.compare_candidates_default;
1769 break;
1770 default:
1771 break;
1772 }
1773
1774 /* Well, the user let us make the choice.
1775 *
1776 * If something had gone wrong with at least one descendant in
1777 * can, then prefer to choose something else. */
1778 for (i = can->child_num-1; i >= 0; i--)
1779 if (can->termcode[i] == LP_ABANDONED)
1780 return(FIRST_CANDIDATE_BETTER);
1781
1782 /* OK, so all descendants in can finished fine. Just do whatever
1783 * built-in was asked */
1784 #ifdef COMPILE_FRAC_BRANCHING
1785 for (frl0 = frh0 = best->frac_num[0], i = best->child_num-1; i; i--){
1786 frl0 = MIN(frl0, best->frac_num[i]);
1787 frh0 = MAX(frh0, best->frac_num[i]);
1788 }
1789 for (frl1 = frh1 = can->frac_num[0], i = can->child_num-1; i; i--){
1790 frl1 = MIN(frl1, can->frac_num[i]);
1791 frh1 = MAX(frh1, can->frac_num[i]);
1792 }
1793 #endif
1794 for (low0 = high0 = best->objval[0], i = best->child_num-1; i; i--){
1795 low0 = MIN(low0, best->objval[i]);
1796 high0 = MAX(high0, best->objval[i]);
1797 }
1798 for (low1 = high1 = can->objval[0], i = can->child_num-1; i; i--){
1799 low1 = MIN(low1, can->objval[i]);
1800 high1 = MAX(high1, can->objval[i]);
1801 }
1802
1803 switch(user_res){
1804 case HIGH_LOW_COMBINATION:
1805 if (high0 > ub_minus_gran) {
1806 high0 = infinity;
1807 }
1808 if (low0 > ub_minus_gran) {
1809 low0 = infinity;
1810 }
1811 if (high1 > ub_minus_gran) {
1812 high1 = infinity;
1813 }
1814 if (low1 > ub_minus_gran) {
1815 low1 = infinity;
1816 }
1817 i = (alpha*low0 + (1 - alpha)*high0 > alpha*low1 + (1 - alpha)*high1) ?
1818 0 : 1;
1819 break;
1820 case BIGGEST_DIFFERENCE_OBJ:
1821 i = (high0 - low0 >= high1 - low1) ? 0 : 1;
1822 break;
1823 case LOWEST_LOW_OBJ:
1824 i = (fabs(low0-low1)<lpetol) ? (high0 <= high1 ? 0 : 1) : (low0 < low1 ? 0 : 1);
1825 break;
1826 case HIGHEST_LOW_OBJ:
1827 i = (fabs(low0-low1)<lpetol) ? (high0 >= high1 ? 0 : 1) : (low0 > low1 ? 0 : 1);
1828 break;
1829 case LOWEST_HIGH_OBJ:
1830 i = (fabs(high0-high1)<lpetol) ? (low0 <= low1 ? 0 : 1) : (high0 < high1 ? 0 : 1);
1831 break;
1832 case HIGHEST_HIGH_OBJ:
1833 i = (fabs(high0-high1)<lpetol) ? (low0 >= low1 ? 0 : 1) : (high0 > high1 ? 0 : 1);
1834 break;
1835 #ifdef COMPILE_FRAC_BRANCHING
1836 case HIGHEST_LOW_FRAC:
1837 i = (frl0 == frl1) ? (frh0 >= frh1 ? 0 : 1) : (frl0 > frl1 ? 0 : 1);
1838 break;
1839 case LOWEST_LOW_FRAC:
1840 i = (frl0 == frl1) ? (frh0 <= frh1 ? 0 : 1) : (frl0 < frl1 ? 0 : 1);
1841 break;
1842 case HIGHEST_HIGH_FRAC:
1843 i = (frh0 == frh1) ? (frl0 >= frl1 ? 0 : 1) : (frh0 > frh1 ? 0 : 1);
1844 break;
1845 case LOWEST_HIGH_FRAC:
1846 i = (frh0 == frh1) ? (frl0 <= frl1 ? 0 : 1) : (frh0 < frh1 ? 0 : 1);
1847 break;
1848 #endif
1849 default: /* Unexpected return value. Do something!! */
1850 break;
1851 }
1852 return(i == 0 ? FIRST_CANDIDATE_BETTER : SECOND_CANDIDATE_BETTER);
1853 }
1854
1855 /*===========================================================================*/
1856
1857 /*===========================================================================*\
1858 * This function invokes the user written function user_select_child that
1859 * selects one of the candidates after branching for further processing.
1860 \*===========================================================================*/
1861
select_child_u(lp_prob * p,branch_obj * can,char * action)1862 int select_child_u(lp_prob *p, branch_obj *can, char *action)
1863 {
1864 int user_res;
1865 int ind, i;
1866
1867 #ifdef DO_TESTS
1868 char sense;
1869 for (i = can->child_num-1; i >= 0; i--){
1870 sense = can->sense[i];
1871 if (sense != 'E' && sense != 'L' && sense != 'G' && sense != 'R'){
1872 printf("Error! The sense of a child doesn't make sense!");
1873 printf("(nonexistent)\n\n");
1874 return(ERROR__ILLEGAL_BRANCHING);
1875 }
1876 }
1877 #endif
1878
1879 for (ind = -1, i = 0; i < can->child_num; i++){
1880 action[i] = RETURN_THIS_CHILD;
1881 if (p->lp_data->nf_status == NF_CHECK_NOTHING){
1882 /*see which one is infeasible!*/
1883 if (can->termcode[i] == LP_OPTIMAL ||
1884 can->termcode[i] == LP_D_ITLIM){
1885 if (p->has_ub &&
1886 can->objval[i] > p->ub - p->par.granularity){
1887 action[i] = PRUNE_THIS_CHILD_FATHOMABLE;
1888 }
1889 }else if (can->termcode[i] == LP_OPT_FEASIBLE ||
1890 can->termcode[i] == LP_OPT_FEASIBLE_BUT_CONTINUE){
1891 action[i] = PRUNE_THIS_CHILD_FATHOMABLE;
1892 }else{
1893 action[i] = PRUNE_THIS_CHILD_INFEASIBLE;
1894 }
1895 }
1896 }
1897
1898 #ifdef USE_SYM_APPLICATION
1899 user_res = user_select_child(p->user, p->ub, can, action);
1900 #else
1901 user_res = USER_DEFAULT;
1902 #endif
1903
1904 switch(user_res){
1905 case USER_NO_PP:
1906 case USER_AND_PP:
1907 /* User function terminated without problems. Skip post-processing. */
1908 break;
1909 case USER_ERROR:
1910 /* In case of error, default is used. */
1911 case USER_DEFAULT:
1912 user_res = p->par.select_child_default;
1913 break;
1914 default:
1915 break;
1916 }
1917
1918 switch(user_res){
1919 case PREFER_LOWER_OBJ_VALUE:
1920 for (ind = 0, i = can->child_num-1; i; i--){
1921 if (can->objval[i] < can->objval[ind] - 1e-4)
1922 ind = i;
1923 }
1924 if (!p->has_ub ||
1925 (p->has_ub && can->objval[ind] < p->ub - p->par.granularity))
1926 action[ind] = KEEP_THIS_CHILD;
1927 /* Note that if the lowest objval child is fathomed then everything is */
1928 break;
1929
1930 case PREFER_HIGHER_OBJ_VALUE:
1931 for (ind = 0, i = can->child_num-1; i; i--){
1932 if ((can->objval[i] > can->objval[ind]) &&
1933 (! p->has_ub ||
1934 (p->has_ub && can->objval[i] < p->ub - p->par.granularity)))
1935 ind = i;
1936 }
1937 if (! p->has_ub ||
1938 (p->has_ub && can->objval[ind] < p->ub - p->par.granularity))
1939 action[ind] = KEEP_THIS_CHILD;
1940 /* Note that this selects the highest objval child NOT FATHOMED, thus
1941 * if the highest objval child is fathomed then so is everything */
1942 break;
1943
1944 #ifdef COMPILE_FRAC_BRANCHING
1945 case PREFER_MORE_FRACTIONAL:
1946 for (ind = 0, i = can->child_num-1; i; i--){
1947 if ((can->frac_num[i] > can->frac_num[ind]) &&
1948 (! p->has_ub ||
1949 (p->has_ub && can->objval[i] < p->ub - p->par.granularity)))
1950 ind = i;
1951 }
1952 if (! p->has_ub ||
1953 (p->has_ub && can->objval[ind] < p->ub - p->par.granularity))
1954 action[ind] = KEEP_THIS_CHILD;
1955 /* Note that this selects the most fractional child NOT FATHOMED, thus
1956 * if that child is fathomed then so is everything */
1957 break;
1958
1959 case PREFER_LESS_FRACTIONAL:
1960 for (ind = 0, i = can->child_num-1; i; i--){
1961 if ((can->frac_num[i] < can->frac_num[ind]) &&
1962 (! p->has_ub ||
1963 (p->has_ub && can->objval[i] < p->ub - p->par.granularity)))
1964 ind = i;
1965 }
1966 if (! p->has_ub ||
1967 (p->has_ub && can->objval[ind] < p->ub - p->par.granularity))
1968 action[ind] = KEEP_THIS_CHILD;
1969 /* Note that this selects the least fractional child NOT FATHOMED, thus
1970 * if that child is fathomed then so is everything */
1971 break;
1972 #endif
1973
1974 case USER_NO_PP:
1975 case USER_AND_PP:
1976 break;
1977
1978 default:
1979 /* Unexpected return value. Do something!! */
1980 break;
1981 }
1982
1983 return(FUNCTION_TERMINATED_NORMALLY);
1984 }
1985
1986 /*===========================================================================*/
1987
1988 /*===========================================================================*\
1989 * This function prints whatever statistics we want on branching
1990 \*===========================================================================*/
1991
print_branch_stat_u(lp_prob * p,branch_obj * can,char * action)1992 void print_branch_stat_u(lp_prob *p, branch_obj *can, char *action)
1993 {
1994 int i;
1995
1996 if (can->type == CANDIDATE_VARIABLE){
1997 if (p->mip){
1998 if (p->mip->colname){
1999 printf("Branching on variable %s \n children: ",
2000 p->mip->colname[p->lp_data->vars[can->position]->userind]);
2001 }
2002 }else{
2003 printf("Branching on variable %i ( %i )\n children: ",
2004 can->position, p->lp_data->vars[can->position]->userind);
2005 }
2006 }else{ /* must be CANDIDATE_CUT_IN_MATRIX */
2007 printf("Branching on a cut %i\n children: ",
2008 p->lp_data->rows[can->position].cut->name);
2009 }
2010 for (i=0; i<can->child_num; i++){
2011 if (can->objval[i] != MAXDOUBLE / 2){
2012 if (p->mip->obj_sense == SYM_MAXIMIZE){
2013 printf("[%.3f, %i,%i] ", -can->objval[i] + p->mip->obj_offset,
2014 can->termcode[i], can->iterd[i]);
2015 }else{
2016 printf("[%.3f, %i,%i] ", can->objval[i] + p->mip->obj_offset,
2017 can->termcode[i], can->iterd[i]);
2018 }
2019 }else{
2020 printf("[*, %i,%i] ", can->termcode[i], can->iterd[i]);
2021 }
2022 }
2023 printf("\n");
2024
2025 #ifdef USE_SYM_APPLICATION
2026 if (can->type == CANDIDATE_VARIABLE){
2027 user_print_branch_stat(p->user, can, NULL,
2028 p->lp_data->n, p->lp_data->vars, action);
2029 }else{
2030 user_print_branch_stat(p->user, can,
2031 p->lp_data->rows[can->position].cut,
2032 p->lp_data->n, p->lp_data->vars, action);
2033 }
2034 #endif
2035 }
2036
2037 /*===========================================================================*/
2038
2039 /*===========================================================================*\
2040 * Append additional information to the description of an active node
2041 * before it is sent back to the tree manager.
2042 \*===========================================================================*/
2043
add_to_desc_u(lp_prob * p,node_desc * desc)2044 void add_to_desc_u(lp_prob *p, node_desc *desc)
2045 {
2046 desc->desc_size = 0;
2047 desc->desc = NULL;
2048 #ifdef USE_SYM_APPLICATION
2049 user_add_to_desc(p->user, &desc->desc_size,
2050 &desc->desc);
2051 #endif
2052 }
2053
2054 /*===========================================================================*/
2055
same_cuts_u(lp_prob * p,waiting_row * wrow1,waiting_row * wrow2)2056 int same_cuts_u(lp_prob *p, waiting_row *wrow1, waiting_row *wrow2)
2057 {
2058 int user_res;
2059 int same_cuts = DIFFERENT_CUTS;
2060 cut_data *rcut1 = NULL, *rcut2 = NULL;
2061
2062 #ifdef USE_SYM_APPLICATION
2063 user_res = user_same_cuts(p->user, wrow1->cut, wrow2->cut, &same_cuts);
2064 #else
2065 user_res = USER_DEFAULT;
2066 #endif
2067
2068 switch (user_res){
2069 case USER_SUCCESS:
2070 case USER_NO_PP:
2071 case USER_AND_PP:
2072 break;
2073 case USER_ERROR: /* Error. Use the default */
2074 case USER_DEFAULT: /* the only default is to compare byte by byte */
2075 rcut1 = wrow1->cut;
2076 rcut2 = wrow2->cut;
2077 if (rcut1->type != rcut2->type || rcut1->sense != rcut2->sense ||
2078 rcut1->size != rcut2->size ||
2079 memcmp(rcut1->coef, rcut2->coef, rcut1->size))
2080 break; /* if LHS is different, then just break out. */
2081
2082 /* Otherwise the two cuts have the same left hand side. Test which
2083 * one is stronger */
2084 /********* something should be done about ranged constraints ***********/
2085 /* FIXME! */
2086 if (rcut1->sense == 'L'){
2087 same_cuts = rcut1->rhs > rcut2->rhs - p->lp_data->lpetol ?
2088 SECOND_CUT_BETTER : FIRST_CUT_BETTER;
2089 break;
2090 }else if (rcut1->sense == 'G'){
2091 same_cuts = rcut1->rhs < rcut2->rhs + p->lp_data->lpetol ?
2092 SECOND_CUT_BETTER : FIRST_CUT_BETTER;
2093 break;
2094 }
2095 same_cuts = wrow1->source_pid < wrow2->source_pid ?
2096 SECOND_CUT_BETTER : FIRST_CUT_BETTER;
2097 break;
2098 }
2099
2100 switch(same_cuts){
2101 case SECOND_CUT_BETTER: /* effective replace the old with the new, then..*/
2102 same_cuts = SAME_CUTS;
2103 wrow1->violation += fabs(rcut1->rhs - rcut2->rhs);
2104 rcut1->rhs = rcut2->rhs;
2105 rcut1->name = rcut2->name;
2106 case SAME_CUTS:
2107 case FIRST_CUT_BETTER: /* delete the new */
2108 FREE(rcut2->coef);
2109 break;
2110
2111 case DIFFERENT_CUTS:
2112 break;
2113 }
2114
2115 return(same_cuts);
2116 }
2117
2118 /*===========================================================================*/
2119
unpack_cuts_u(lp_prob * p,int from,int type,int cut_num,cut_data ** cuts,int * new_row_num,waiting_row *** new_rows)2120 void unpack_cuts_u(lp_prob *p, int from, int type,
2121 int cut_num, cut_data **cuts,
2122 int *new_row_num, waiting_row ***new_rows)
2123 {
2124 LPdata *lp_data = p->lp_data;
2125 int user_res;
2126 int i, j, k, l = 0, nzcnt, real_nzcnt, explicit_row_num = 0;
2127 const int n = lp_data->n;
2128 int *matind, *row_matind;
2129 double *matval, *row_matval;
2130 waiting_row **row_list = NULL;
2131 double *obj1 = p->mip->obj1;
2132 double *obj2 = p->mip->obj2;
2133 var_desc **vars = lp_data->vars;
2134 const int is_userind_in_order = p->par.is_userind_in_order;
2135
2136 colind_sort_extra(p);
2137
2138 if (cut_num > 0)
2139 row_list = (waiting_row **) calloc (cut_num, sizeof(waiting_row *));
2140
2141 /* First SYMPHONY looks for cut types that it knows */
2142 for (i = 0; i < cut_num; i++){
2143
2144 switch (cuts[i]->type){
2145
2146 case EXPLICIT_ROW:
2147 real_nzcnt = 0;
2148 row_list[explicit_row_num] =
2149 (waiting_row *) malloc(sizeof(waiting_row));
2150 row_list[explicit_row_num]->cut = cuts[i];
2151 nzcnt = ((int *) (cuts[i]->coef))[0];
2152 matval = (double *) (cuts[i]->coef + DSIZE);
2153 matind = (int *) (cuts[i]->coef + (nzcnt + 1)*DSIZE);
2154 row_matval = row_list[explicit_row_num]->matval =
2155 (double *) malloc(nzcnt * DSIZE);
2156 row_matind = row_list[explicit_row_num]->matind =
2157 (int *) malloc(nzcnt * ISIZE);
2158 if (is_userind_in_order) {
2159 memcpy(row_matind, matind, nzcnt*ISIZE);
2160 memcpy(row_matval, matval, nzcnt*DSIZE);
2161 real_nzcnt = nzcnt;
2162 } else {
2163 for (j = 0; j < n; j++){
2164 for (k = 0; k < nzcnt; k++){
2165 if (matind[k] == vars[j]->userind){
2166 row_matind[real_nzcnt] = j;
2167 row_matval[real_nzcnt++] = matval[k];
2168 }
2169 }
2170 }
2171 }
2172 row_list[explicit_row_num++]->nzcnt = real_nzcnt;
2173 cuts[i] = NULL;
2174 break;
2175
2176 case OPTIMALITY_CUT_FIRST:
2177 row_list[explicit_row_num] =
2178 (waiting_row *) malloc(sizeof(waiting_row));
2179 row_matind = row_list[explicit_row_num]->matind =
2180 (int *) malloc (lp_data->n * ISIZE);
2181 row_matval = row_list[explicit_row_num]->matval =
2182 (double *) malloc (lp_data->n * DSIZE);
2183 row_list[explicit_row_num]->cut = cuts[i];
2184 for (nzcnt = 0, j = 0; j < lp_data->n; j++){
2185 if (vars[j]->userind == p->mip->n)
2186 continue;
2187 row_matind[nzcnt] = j;
2188 row_matval[nzcnt++] = obj1[vars[j]->userind];
2189 }
2190 cuts[i]->sense = 'L';
2191 cuts[i]->deletable = FALSE;
2192 cuts[i]->branch = DO_NOT_BRANCH_ON_THIS_ROW;
2193 row_list[explicit_row_num++]->nzcnt = nzcnt;
2194 cuts[i] = NULL;
2195 break;
2196
2197 case OPTIMALITY_CUT_SECOND:
2198 row_list[explicit_row_num] =
2199 (waiting_row *) malloc(sizeof(waiting_row));
2200 row_list[explicit_row_num]->matind =
2201 (int *) malloc (lp_data->n * ISIZE);
2202 row_list[explicit_row_num]->matval =
2203 (double *) malloc (lp_data->n * DSIZE);
2204 row_list[explicit_row_num]->cut = cuts[i];
2205 for (nzcnt = 0, j = 0; j < lp_data->n; j++){
2206 if (vars[j]->userind == p->mip->n)
2207 continue;
2208 row_list[explicit_row_num]->matind[nzcnt] = j;
2209 row_list[explicit_row_num]->matval[nzcnt++] =
2210 obj2[vars[j]->userind];
2211 }
2212 cuts[i]->sense = 'L';
2213 cuts[i]->deletable = FALSE;
2214 cuts[i]->branch = DO_NOT_BRANCH_ON_THIS_ROW;
2215 row_list[explicit_row_num++]->nzcnt = nzcnt;
2216 cuts[i] = NULL;
2217 break;
2218
2219 default: /* A user cut type */
2220 #if defined(COMPILE_IN_CG) && defined(CHECK_CUT_VALIDITY)
2221 check_validity_of_cut_u(p->cgp, cuts[i]);
2222 #endif
2223 if (l != i){
2224 cuts[l++] = cuts[i];
2225 cuts[i] = NULL;
2226 }else{
2227 l++;
2228 }
2229 break;
2230 }
2231 }
2232
2233 *new_row_num = 0;
2234
2235 #ifdef USE_SYM_APPLICATION
2236 user_res = user_unpack_cuts(p->user, from, type,
2237 lp_data->n, lp_data->vars,
2238 l, cuts, new_row_num, new_rows);
2239 #else
2240 user_res = USER_DEFAULT;
2241 #endif
2242
2243 for (i = 0; i < l; i++){
2244 if (cuts[i]){
2245 (*new_rows)[i]->cut = cuts[i];
2246 cuts[i] = NULL;
2247 }
2248 }
2249
2250 switch(user_res){
2251 case USER_SUCCESS:
2252 case USER_AND_PP:
2253 case USER_NO_PP:
2254 case USER_DEFAULT:
2255
2256 /* Combine the user's rows with SYMPHONY's rows */
2257 if (*new_row_num == 0 && explicit_row_num == 0){
2258 FREE(row_list);
2259 *new_row_num = 0;
2260 *new_rows = NULL;
2261 }else if (*new_row_num == 0 && explicit_row_num > 0){
2262 *new_row_num = explicit_row_num;
2263 *new_rows = row_list;
2264 }else if (*new_row_num > 0 && explicit_row_num > 0){
2265 if (*new_row_num + explicit_row_num > cut_num){
2266 row_list = (waiting_row **) realloc(row_list, *new_row_num +
2267 explicit_row_num);
2268 }
2269 for (i = explicit_row_num; i < *new_row_num + explicit_row_num; i++){
2270 row_list[i] = (*new_rows)[i - explicit_row_num];
2271 }
2272
2273 FREE(*new_rows);
2274 *new_row_num += explicit_row_num;
2275 *new_rows = row_list;
2276 }else{
2277 FREE(row_list);
2278 }
2279
2280 break;
2281
2282 case USER_ERROR: /* Error. ??? what will happen ??? */
2283 *new_row_num = 0;
2284 FREE(*new_rows);
2285
2286 break;
2287
2288 default: /* No builtin possibility. Counts as ERROR. */
2289 break;
2290 }
2291
2292 free_cuts(cuts, cut_num);
2293 }
2294
2295 /*===========================================================================*/
2296
2297 /*===========================================================================*\
2298 * The user packs together and sends a message to the cut generator or
2299 * cut pool process to obtain violated cuts.
2300 * Default options: SEND_NONZEROS, SEND_FRACTIONS.
2301 * The function return 1 or 0, depending on whether the sending of the
2302 * lp solution was successful or not.
2303 \*===========================================================================*/
2304
send_lp_solution_u(lp_prob * p,int tid)2305 int send_lp_solution_u(lp_prob *p, int tid)
2306 {
2307 LPdata *lp_data = p->lp_data;
2308 double *x = lp_data->x;
2309 int user_res, nzcnt, s_bufid, msgtag = ANYTHING;
2310 int *xind = lp_data->tmp.i1; /* n */
2311 double *xval = lp_data->tmp.d; /* n */
2312
2313 s_bufid = init_send(DataInPlace);
2314 send_int_array(&p->bc_level, 1);
2315 send_int_array(&p->bc_index, 1);
2316 send_int_array(&p->iter_num, 1);
2317 send_dbl_array(&lp_data->lpetol, 1);
2318 if (tid == p->cut_gen){
2319 send_dbl_array(&lp_data->objval, 1);
2320 send_int_array(&p->has_ub, 1);
2321 if (p->has_ub)
2322 send_dbl_array(&p->ub, 1);
2323 }
2324 colind_sort_extra(p);
2325 #ifdef USE_SYM_APPLICATION
2326 user_res = user_send_lp_solution(p->user, lp_data->n, lp_data->vars, x,
2327 tid == p->cut_gen ?
2328 LP_SOL_TO_CG : LP_SOL_TO_CP);
2329 #else
2330 user_res = USER_DEFAULT;
2331 #endif
2332
2333 switch (user_res){
2334 case USER_ERROR: /* Error. Consider as couldn't send to cut_gen, i.e.,
2335 equivalent to NO_MORE_CUTS_FOUND */
2336 freebuf(s_bufid);
2337 return(0);
2338 case USER_SUCCESS:
2339 case USER_AND_PP:
2340 case USER_NO_PP:
2341 msgtag = LP_SOLUTION_USER;
2342 break;
2343 case USER_DEFAULT: /* set the default */
2344 user_res = p->par.pack_lp_solution_default; /* SEND_NONZEROS */
2345 break;
2346 }
2347
2348 if (msgtag == LP_SOLUTION_USER){
2349 send_msg(tid, LP_SOLUTION_USER);
2350 freebuf(s_bufid);
2351 return(1);
2352 }
2353
2354 switch(user_res){
2355 case SEND_NONZEROS:
2356 nzcnt = collect_nonzeros(p, x, xind, xval);
2357 msgtag = LP_SOLUTION_NONZEROS;
2358 break;
2359 case SEND_FRACTIONS:
2360 nzcnt = collect_fractions(p, x, xind, xval);
2361 msgtag = LP_SOLUTION_FRACTIONS;
2362 break;
2363 }
2364 /* send the data */
2365 send_int_array(&nzcnt, 1);
2366 send_int_array(xind, nzcnt);
2367 send_dbl_array(xval, nzcnt);
2368 send_msg(tid, msgtag);
2369 freebuf(s_bufid);
2370
2371 return(1);
2372 }
2373
2374 /*===========================================================================*/
2375
logical_fixing_u(lp_prob * p)2376 void logical_fixing_u(lp_prob *p)
2377 {
2378 char *status = p->lp_data->tmp.c; /* n */
2379 char *lpstatus = p->lp_data->status;
2380 char *laststat = status + p->lp_data->n;
2381 int fixed_num = 0, user_res;
2382
2383 colind_sort_extra(p);
2384 //memcpy(status, lpstatus, p->lp_data->n);
2385 memcpy(status, lpstatus, CSIZE*p->lp_data->n);
2386
2387 #ifdef USE_SYM_APPLICATION
2388 user_res = user_logical_fixing(p->user, p->lp_data->n, p->lp_data->vars,
2389 p->lp_data->x, status, &fixed_num);
2390 #else
2391 user_res = USER_DEFAULT;
2392 #endif
2393
2394 switch(user_res){
2395 case USER_SUCCESS:
2396 case USER_AND_PP:
2397 case USER_NO_PP:
2398 if (fixed_num > 0){
2399 while (status != laststat) {
2400 *lpstatus &= NOT_REMOVABLE;
2401 *lpstatus++ |= (*status++ & (NOT_FIXED |
2402 TEMP_FIXED_TO_LB | TEMP_FIXED_TO_UB |
2403 PERM_FIXED_TO_LB | PERM_FIXED_TO_UB));
2404 }
2405 }
2406 case USER_DEFAULT:
2407 break;
2408 }
2409 }
2410
2411 /*===========================================================================*/
2412
generate_column_u(lp_prob * p,int lpcutnum,cut_data ** cuts,int prevind,int nextind,int generate_what,double * colval,int * colind,int * collen,double * obj,double * lb,double * ub)2413 int generate_column_u(lp_prob *p, int lpcutnum, cut_data **cuts,
2414 int prevind, int nextind, int generate_what,
2415 double *colval, int *colind, int *collen, double *obj,
2416 double *lb, double *ub)
2417 {
2418 int real_nextind = nextind;
2419 #ifdef USE_SYM_APPLICATION
2420 CALL_USER_FUNCTION( user_generate_column(p->user, generate_what,
2421 p->lp_data->m - p->base.cutnum,
2422 cuts, prevind, nextind,
2423 &real_nextind, colval, colind,
2424 collen, obj, lb, ub) );
2425 #endif
2426 return(real_nextind);
2427 }
2428
2429 /*===========================================================================*/
2430
generate_cuts_in_lp_u(lp_prob * p)2431 int generate_cuts_in_lp_u(lp_prob *p)
2432 {
2433 LPdata *lp_data = p->lp_data;
2434 double *x = lp_data->x;
2435 int user_res, new_row_num = 0;
2436 waiting_row **new_rows = NULL;
2437 char deleted_cut;
2438 cut_data **cuts = NULL;
2439 int i, j;
2440
2441 colind_sort_extra(p);
2442
2443 #if defined(COMPILE_IN_CG) || defined(COMPILE_IN_CP)
2444 {
2445 #ifdef COMPILE_IN_CP
2446 int cp_new_row_num = 0;
2447 waiting_row **cp_new_rows = NULL;
2448 #endif
2449 #ifdef COMPILE_IN_CG
2450 int cg_new_row_num = 0;
2451 waiting_row **cg_new_rows = NULL;
2452 #endif
2453 int user_res2, xlength = 0, *xind = NULL;
2454 lp_sol *cur_sol = &(p->cgp->cur_sol);
2455 double *xval = NULL, lpetol = 0;
2456
2457 #ifdef USE_SYM_APPLICATION
2458 user_res2 = user_send_lp_solution(p->user,
2459 lp_data->n, lp_data->vars, x,
2460 LP_SOL_WITHIN_LP);
2461 #else
2462 user_res2 = USER_DEFAULT;
2463 #endif
2464
2465 if (user_res2 == USER_DEFAULT)
2466 user_res2 = p->par.pack_lp_solution_default;
2467
2468 switch (user_res2){
2469 case USER_ERROR:
2470 return(ERROR__USER);
2471 case USER_SUCCESS:
2472 case USER_AND_PP:
2473 case USER_NO_PP:
2474 break;
2475 case SEND_NONZEROS:
2476 case SEND_FRACTIONS:
2477 cur_sol->xind = xind = lp_data->tmp.i1; /* n */
2478 cur_sol->xval = xval = lp_data->tmp.d; /* n */
2479 cur_sol->lpetol = lpetol = lp_data->lpetol;
2480 cur_sol->xlevel = p->bc_level;
2481 cur_sol->xindex = p->bc_index;
2482 cur_sol->xiter_num = p->iter_num;
2483 cur_sol->objval = lp_data->objval;
2484 if (p->has_ub)
2485 p->cgp->ub = p->ub;
2486 cur_sol->xlength = xlength = user_res2 == SEND_NONZEROS ?
2487 collect_nonzeros(p, x, xind, xval) :
2488 collect_fractions(p, x, xind, xval);
2489 break;
2490 }
2491 #ifdef COMPILE_IN_CG
2492 if (p->cgp->par.do_findcuts && !new_row_num)
2493 find_cuts_u(p->cgp, p->lp_data, &cg_new_row_num);
2494 #endif
2495
2496 if (p->cgp->cuts_to_add_num){
2497 unpack_cuts_u(p, CUT_FROM_CG, UNPACK_CUTS_MULTIPLE,
2498 p->cgp->cuts_to_add_num, p->cgp->cuts_to_add,
2499 &cg_new_row_num, &cg_new_rows);
2500 p->cgp->cuts_to_add_num = 0;
2501 if (cg_new_row_num){
2502 for (i = 0; i < cg_new_row_num; i++){
2503 if (cg_new_rows[i]->cut->name != CUT__SEND_TO_CP)
2504 cg_new_rows[i]->cut->name = CUT__DO_NOT_SEND_TO_CP;
2505 cg_new_rows[i]->source_pid = INTERNAL_CUT_GEN;
2506 for (j = p->waiting_row_num - 1; j >= 0; j--){
2507 if (same_cuts_u(p, p->waiting_rows[j],
2508 cg_new_rows[i]) !=
2509 DIFFERENT_CUTS){
2510 free_waiting_row(cg_new_rows+i);
2511 break;
2512 }
2513 }
2514 if (j < 0){
2515 add_new_rows_to_waiting_rows(p, cg_new_rows+i, 1);
2516 }
2517 }
2518 FREE(cg_new_rows);
2519 }
2520 }
2521 #if defined(COMPILE_IN_CP) && defined(COMPILE_IN_LP)
2522
2523 if ((p->iter_num == 1 && (p->bc_level > 0 || p->phase==1)) ||
2524 (p->iter_num % p->par.cut_pool_check_freq == 0) ||
2525 (!cg_new_row_num)){
2526 cut_pool *cp = p->tm->cpp[p->cut_pool];
2527 p->comp_times.separation += used_time(&p->tt);
2528 cur_sol->lp = 0;
2529 #pragma omp critical(cut_pool)
2530 if (cp){
2531 cp_new_row_num = check_cuts_u(cp, cur_sol);
2532 if (++cp->reorder_count % 10 == 0){
2533 delete_duplicate_cuts(cp);
2534 order_cuts_by_quality(cp);
2535 cp->reorder_count = 0;
2536 }
2537 if (cp_new_row_num){
2538 unpack_cuts_u(p, CUT_FROM_CG, UNPACK_CUTS_MULTIPLE,
2539 cp->cuts_to_add_num, cp->cuts_to_add,
2540 &cp_new_row_num, &cp_new_rows);
2541 cp->cuts_to_add_num = 0;
2542 }
2543 }
2544 if (cp_new_row_num){
2545 for (i = 0; i < cp_new_row_num; i++){
2546 if (cp_new_rows[i]->cut->name != CUT__SEND_TO_CP)
2547 cp_new_rows[i]->cut->name = CUT__DO_NOT_SEND_TO_CP;
2548 cp_new_rows[i]->source_pid = INTERNAL_CUT_POOL;
2549 for (j = p->waiting_row_num - 1; j >= 0; j--){
2550 if (same_cuts_u(p, p->waiting_rows[j], cp_new_rows[i]) !=
2551 DIFFERENT_CUTS){
2552 free_waiting_row(cp_new_rows+i);
2553 break;
2554 }
2555 }
2556 if (j < 0){
2557 add_new_rows_to_waiting_rows(p, cp_new_rows+i, 1);
2558 }
2559 }
2560 FREE(cp_new_rows);
2561 }
2562 p->comp_times.cut_pool += used_time(&p->tt);
2563 }
2564 #endif
2565 }
2566 #endif
2567
2568 #ifdef USE_SYM_APPLICATION
2569 user_res = user_generate_cuts_in_lp(p->user, lp_data, lp_data->n,
2570 lp_data->vars, x,
2571 &new_row_num, &cuts);
2572 #else
2573 user_res = GENERATE_CGL_CUTS;
2574 #endif
2575
2576 switch(user_res){
2577 case USER_ERROR:
2578 FREE(cuts);
2579 return(ERROR__USER);
2580 case GENERATE_CGL_CUTS:
2581 case USER_DEFAULT:
2582 /* Add to the user's list of cuts */
2583 #ifdef USE_CGL_CUTS
2584 if (p->par.cgl.generate_cgl_cuts){
2585 int bound_changes = 0;
2586 /*
2587 double ub = p->has_ub ? p->ub : SYM_INFINITY;
2588 generate_cgl_cuts(lp_data, &new_row_num, &cuts, FALSE,
2589 p->bc_index, p->bc_level, p->node_iter_num,
2590 p->par.max_cut_num_per_iter_root,
2591 ub, &bound_changes, &(p->lp_stat), &(p->comp_times),
2592 p->par.verbosity);
2593 */
2594 generate_cgl_cuts_new(p, &new_row_num, &cuts, FALSE,
2595 &bound_changes);
2596 if (bound_changes>0) {
2597 p->bound_changes_in_iter += bound_changes;
2598 }
2599 // if(p->bc_index < 1 && p->iter_num == 1 ){
2600 // p->par.cgl = lp_data->cgl;
2601 // }
2602 }
2603 #endif
2604 /* Fall through to next case */
2605
2606 case DO_NOT_GENERATE_CGL_CUTS:
2607 case USER_SUCCESS:
2608 case USER_AND_PP:
2609 case USER_NO_PP:
2610 /* Process the generated cuts */
2611 if (new_row_num){
2612 unpack_cuts_u(p, CUT_FROM_CG, UNPACK_CUTS_MULTIPLE,
2613 new_row_num, cuts, &new_row_num, &new_rows);
2614 for (i = 0; i < new_row_num; i++){
2615 if (new_rows[i]->cut->name != CUT__SEND_TO_CP)
2616 new_rows[i]->cut->name = CUT__DO_NOT_SEND_TO_CP;
2617 new_rows[i]->source_pid = INTERNAL_CUT_GEN;
2618 }
2619 }
2620 /* Test whether any of the new cuts are identical to any of
2621 the old ones. */
2622 if (p->waiting_row_num && new_row_num){
2623 for (i = 0, deleted_cut = FALSE; i < new_row_num;
2624 deleted_cut = FALSE){
2625 for (j = p->waiting_row_num - 1; j >= 0; j--){
2626 if (same_cuts_u(p, p->waiting_rows[j], new_rows[i]) !=
2627 DIFFERENT_CUTS){
2628 free_waiting_row(new_rows+i);
2629 new_rows[i] = new_rows[--new_row_num];
2630 deleted_cut = TRUE;
2631 break;
2632 }
2633 }
2634 if (!deleted_cut) i++;
2635 }
2636 }
2637 if (new_row_num){
2638 add_new_rows_to_waiting_rows(p, new_rows, new_row_num);
2639 FREE(new_rows);
2640 }
2641 FREE(cuts);
2642 return(FUNCTION_TERMINATED_NORMALLY);
2643 default:
2644 /* Unexpected return value. Do something!! */
2645 FREE(cuts);
2646 return(ERROR__USER);
2647 }
2648 }
2649
2650 /*===========================================================================*/
2651
print_stat_on_cuts_added_u(lp_prob * p,int added_rows)2652 void print_stat_on_cuts_added_u(lp_prob *p, int added_rows)
2653 {
2654 int user_res;
2655
2656 #ifdef USE_SYM_APPLICATION
2657 user_res = user_print_stat_on_cuts_added(p->user, added_rows,
2658 p->waiting_rows);
2659 #else
2660 user_res = USER_DEFAULT;
2661 #endif
2662
2663 switch(user_res){
2664 case USER_ERROR:
2665 case USER_DEFAULT:
2666 /* print out how many cuts have been added */
2667 PRINT(p->par.verbosity, 5,
2668 ("Number of cuts added to the problem: %i\n", added_rows));
2669 break;
2670 case USER_SUCCESS:
2671 case USER_AND_PP:
2672 case USER_NO_PP:
2673 break;
2674 default:
2675 /* Unexpected return value. Do something!! */
2676 break;
2677 }
2678 }
2679
2680 /*===========================================================================*/
2681
purge_waiting_rows_u(lp_prob * p)2682 void purge_waiting_rows_u(lp_prob *p)
2683 {
2684 int user_res, i, j;
2685 waiting_row **wrows = p->waiting_rows;
2686 int wrow_num = p->waiting_row_num;
2687 char *delete_rows;
2688 int max_cut_num_per_iter;
2689
2690 REMALLOC(p->lp_data->tmp.cv, char, p->lp_data->tmp.cv_size, wrow_num,
2691 BB_BUNCH);
2692 delete_rows = p->lp_data->tmp.cv; /* wrow_num */
2693
2694 memset(delete_rows, 0, wrow_num);
2695
2696 #ifdef USE_SYM_APPLICATION
2697 user_res = user_purge_waiting_rows(p->user, wrow_num, wrows, delete_rows);
2698 #else
2699 user_res = USER_DEFAULT;
2700 #endif
2701
2702 switch (user_res){
2703 case USER_ERROR: /* purge all */
2704 free_waiting_rows(wrows, wrow_num);
2705 p->waiting_row_num = 0;
2706 break;
2707 case USER_DEFAULT: /* the only default is to keep enough for one
2708 iteration */
2709 max_cut_num_per_iter = (p->bc_level<1) ? p->par.max_cut_num_per_iter_root
2710 : p->par.max_cut_num_per_iter;
2711 if (wrow_num - max_cut_num_per_iter > 0){
2712 free_waiting_rows(wrows + max_cut_num_per_iter,
2713 wrow_num-max_cut_num_per_iter);
2714 p->waiting_row_num = max_cut_num_per_iter;
2715 }
2716 break;
2717 case USER_SUCCESS:
2718 case USER_AND_PP:
2719 case USER_NO_PP:
2720 for (i = j = 0; i < wrow_num; i++){
2721 if (delete_rows[i]){
2722 free_waiting_row(wrows + i);
2723 }else{
2724 wrows[j++] = wrows[i];
2725 }
2726 }
2727 p->waiting_row_num = j;
2728 break;
2729 default:
2730 /* Unexpected return value. Do something!! */
2731 break;
2732 }
2733 }
2734
2735 /*===========================================================================*/
2736 /*===========================================================================*\
2737 * This function invokes the user written function user_free_prob_dependent
2738 * that deallocates the user defined part of the data structure. Returns TRUE
2739 * if succeeded, FALSE otherwise.
2740 \*===========================================================================*/
2741
free_prob_dependent_u(lp_prob * p)2742 void free_prob_dependent_u(lp_prob *p)
2743 {
2744
2745 #ifdef USE_SYM_APPLICATION
2746 switch (user_free_lp(&p->user)){
2747 case USER_ERROR:
2748 /* SYMPHONY ignores error message */
2749 case USER_SUCCESS:
2750 case USER_AND_PP:
2751 case USER_NO_PP:
2752 /* User function terminated without problems. No post-processing. */
2753 return;
2754 default:
2755 /* Unexpected return value. Do something!! */
2756 break;
2757 }
2758 #endif
2759 }
2760
2761 /*===========================================================================*/
2762 /*===========================================================================*/
2763
analyze_multicriteria_solution(lp_prob * p,int * indices,double * values,int length,double * true_objval,double etol,char branching,int feasible)2764 int analyze_multicriteria_solution(lp_prob *p, int *indices, double *values,
2765 int length, double *true_objval,
2766 double etol, char branching,
2767 int feasible)
2768 {
2769 double obj[2] = {0.0, 0.0};
2770 int i;
2771 char new_solution = FALSE;
2772 int continue_with_node = FALSE;
2773 bool has_artificial = false;
2774
2775 for (i = 0; i < length; i++){
2776 if (indices[i] == p->mip->n){
2777 has_artificial = true;
2778 continue;
2779 }
2780 obj[0] += p->mip->obj1[indices[i]]*values[i];
2781 obj[1] += p->mip->obj2[indices[i]]*values[i];
2782 }
2783 if (has_artificial) length--;
2784
2785 if (p->has_mc_ub && *true_objval-p->par.mc_rho*(obj[0]+obj[1]) >
2786 p->mc_ub + etol + MAX(0, MIN(p->par.mc_gamma, p->par.mc_tau))){
2787 return(FALSE);
2788 }
2789
2790 if (p->par.mc_gamma == 1.0){
2791 if (!p->has_mc_ub || obj[0] < p->obj[0] + etol){
2792 if (!p->has_mc_ub || (obj[0] < p->obj[0] - etol ||
2793 (obj[0] >= p->obj[0] - etol
2794 && obj[1] < p->obj[1] - etol))){
2795 if (p->par.verbosity >= 1){
2796 if (feasible == IP_HEUR_FEASIBLE){
2797 printf("\n****** Better Solution Found (Heuristic):\n");
2798 }else{
2799 printf("\n****** Better Solution Found:\n");
2800 }
2801 if(p->mip->obj_sense == SYM_MAXIMIZE){
2802 printf("****** First Objective Cost: %.1f\n", -obj[0]);
2803 printf("****** Second Objective Cost: %.1f\n\n", -obj[1]);
2804 }else{
2805 printf("****** First Objective Cost: %.1f\n", obj[0]);
2806 printf("****** Second Objective Cost: %.1f\n\n", obj[1]);
2807 }
2808 }
2809 p->obj[1] = obj[1];
2810 p->obj[0] = obj[0];
2811 p->mc_ub = *true_objval-p->par.mc_rho*(obj[0]+obj[1]);
2812 p->has_mc_ub = TRUE;
2813 new_solution = TRUE;
2814 }
2815 /* Add an optimality cut for the second objective */
2816 if (!branching && p->par.mc_add_optimality_cuts){
2817 cut_data *new_cut = (cut_data *) calloc(1, sizeof(cut_data));
2818 new_cut->coef = NULL;
2819 new_cut->rhs = obj[1] - 1 + etol;
2820 new_cut->size = 0;
2821 new_cut->type = OPTIMALITY_CUT_SECOND;
2822 new_cut->name = CUT__DO_NOT_SEND_TO_CP;
2823 continue_with_node = cg_add_user_cut(new_cut,
2824 &p->cgp->cuts_to_add_num,
2825 &p->cgp->cuts_to_add_size,
2826 &p->cgp->cuts_to_add);
2827 FREE(new_cut);
2828 }else{
2829 continue_with_node = TRUE;
2830 }
2831 }
2832 }else if (p->par.mc_tau == 1.0){
2833 if (!p->has_mc_ub || obj[1] < p->obj[1] + etol){
2834 if (!p->has_mc_ub || (obj[1] < p->obj[1] - etol ||
2835 (obj[1] >= p->obj[1] - etol
2836 && obj[0] < p->obj[0] - etol))){
2837 if (p->par.verbosity >= 1){
2838 if (feasible == IP_HEUR_FEASIBLE){
2839 printf("\n****** Better Solution Found (Heuristic):\n");
2840 }else{
2841 printf("\n****** Better Solution Found:\n");
2842 }
2843 if(p->mip->obj_sense == SYM_MAXIMIZE){
2844 printf("****** First Objective Cost: %.1f\n", -obj[0]);
2845 printf("****** Second Objective Cost: %.1f\n\n", -obj[1]);
2846 }else{
2847 printf("****** First Objective Cost: %.1f\n", obj[0]);
2848 printf("****** Second Objective Cost: %.1f\n\n", obj[1]);
2849 }
2850 }
2851 p->obj[1] = obj[1];
2852 p->obj[0] = obj[0];
2853 p->mc_ub = *true_objval-p->par.mc_rho*(obj[0]+obj[1]);
2854 p->has_mc_ub = TRUE;
2855 new_solution = TRUE;
2856 }
2857 /* Add an optimality cut for the second objective */
2858 if (!branching && p->par.mc_add_optimality_cuts){
2859 cut_data *new_cut = (cut_data *) calloc(1, sizeof(cut_data));
2860 new_cut->coef = NULL;
2861 new_cut->rhs = obj[0] - 1 + etol;
2862 new_cut->size = 0;
2863 new_cut->type = OPTIMALITY_CUT_FIRST;
2864 new_cut->name = CUT__DO_NOT_SEND_TO_CP;
2865 continue_with_node = cg_add_user_cut(new_cut,
2866 &p->cgp->cuts_to_add_num,
2867 &p->cgp->cuts_to_add_size,
2868 &p->cgp->cuts_to_add);
2869 FREE(new_cut);
2870 }else{
2871 continue_with_node = TRUE;
2872 }
2873 }
2874 }else{
2875 if (!p->has_mc_ub ||
2876 (p->has_mc_ub && *true_objval-p->par.mc_rho*(obj[0]+obj[1]) <
2877 p->mc_ub - MIN(p->par.mc_gamma, p->par.mc_tau) + 100*etol) ||
2878 (obj[0] < p->obj[0] - etol &&
2879 obj[1] < p->obj[1] + etol + MIN(p->par.mc_gamma, p->par.mc_tau)) ||
2880 (obj[1] < p->obj[1] - etol &&
2881 obj[0] < p->obj[0] + etol + MIN(p->par.mc_gamma, p->par.mc_tau))){
2882 if (p->par.verbosity >= 1){
2883 if (feasible == IP_HEUR_FEASIBLE){
2884 printf("\n****** Better Solution Found (Heuristic):\n");
2885 }else{
2886 printf("\n****** Better Solution Found:\n");
2887 }
2888 if(p->mip->obj_sense == SYM_MAXIMIZE){
2889 printf("****** First Objective Cost: %.1f\n", -obj[0]);
2890 printf("****** Second Objective Cost: %.1f\n\n", -obj[1]);
2891 }else{
2892 printf("****** First Objective Cost: %.1f\n", obj[0]);
2893 printf("****** Second Objective Cost: %.1f\n\n", obj[1]);
2894 }
2895 }
2896 p->obj[1] = obj[1];
2897 p->obj[0] = obj[0];
2898 p->mc_ub = *true_objval-p->par.mc_rho*(obj[0]+obj[1]);
2899 p->has_mc_ub = TRUE;
2900 new_solution = TRUE;
2901 }
2902 if (!branching && !p->par.mc_find_supported_solutions &&
2903 p->par.mc_add_optimality_cuts){
2904 if (p->par.mc_gamma*(obj[0] - p->utopia[0]) >
2905 *true_objval-p->par.mc_rho*(obj[0]+obj[1])-etol){
2906 /* Add an optimality cut for the second objective */
2907 cut_data *new_cut = (cut_data *) calloc(1, sizeof(cut_data));
2908 new_cut->coef = NULL;
2909 new_cut->rhs = obj[1] - 1 + etol;
2910 new_cut->size = 0;
2911 new_cut->type = OPTIMALITY_CUT_SECOND;
2912 new_cut->name = CUT__DO_NOT_SEND_TO_CP;
2913 continue_with_node = cg_add_user_cut(new_cut,
2914 &p->cgp->cuts_to_add_num,
2915 &p->cgp->cuts_to_add_size,
2916 &p->cgp->cuts_to_add);
2917 FREE(new_cut);
2918 }else if (!p->par.mc_find_supported_solutions &&
2919 p->par.mc_add_optimality_cuts){
2920 /* Add an optimality cut for the second objective */
2921 cut_data *new_cut = (cut_data *) calloc(1, sizeof(cut_data));
2922 new_cut->coef = NULL;
2923 new_cut->rhs = obj[0] - 1 + etol;
2924 new_cut->size = 0;
2925 new_cut->type = OPTIMALITY_CUT_FIRST;
2926 new_cut->name = CUT__DO_NOT_SEND_TO_CP;
2927 continue_with_node = cg_add_user_cut(new_cut,
2928 &p->cgp->cuts_to_add_num,
2929 &p->cgp->cuts_to_add_size,
2930 &p->cgp->cuts_to_add);
2931 FREE(new_cut);
2932 }
2933 }else if (branching){
2934 continue_with_node = TRUE;
2935 }
2936 }
2937
2938 if (!new_solution){
2939 return(continue_with_node);
2940 }
2941
2942 p->best_sol.xlevel = p->bc_level;
2943 p->best_sol.xindex = p->bc_index;
2944 p->best_sol.xiter_num = p->iter_num;
2945 p->best_sol.xlength = length;
2946 p->best_sol.lpetol = etol;
2947 p->best_sol.objval = *true_objval-p->par.mc_rho*(obj[0]+obj[1]);
2948 FREE(p->best_sol.xind);
2949 FREE(p->best_sol.xval);
2950 p->best_sol.xind = (int *) malloc(length*ISIZE);
2951 p->best_sol.xval = (double *) malloc(length*DSIZE);
2952 memcpy((char *)p->best_sol.xind, (char *)indices, length * ISIZE);
2953 memcpy((char *)p->best_sol.xval, (char *)values, length * DSIZE);
2954
2955 if(!p->best_sol.has_sol){
2956 p->best_sol.has_sol = TRUE;
2957 }
2958
2959 #ifndef COMPILE_IN_TM
2960 send_feasible_solution_u(p, p->bc_level, p->bc_index, p->iter_num,
2961 lpetol, *true_objval-p->par.mc_rho*(obj[0]+obj[1]),
2962 length, indices, values);
2963 #endif
2964 display_lp_solution_u(p, DISP_FEAS_SOLUTION);
2965
2966 return(continue_with_node);
2967
2968 }
2969
2970