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 /* This software is licensed under the Eclipse Public License. Please see */
11 /* accompanying file for terms. */
12 /* */
13 /*===========================================================================*/
14
15 #define COMPILE_FOR_LP
16
17 #ifdef _OPENMP
18 #include "omp.h"
19 #endif
20 #include <stdlib.h>
21 #include <math.h>
22 #include <string.h>
23
24 #include "sym_proccomm.h"
25 #include "sym_qsort.h"
26 #include "sym_lp.h"
27 #include "sym_messages.h"
28 #include "sym_constants.h"
29 #include "sym_macros.h"
30 #include "sym_types.h"
31 #include "sym_pack_cut.h"
32
33 /*===========================================================================*/
34
35 /*===========================================================================*\
36 * This file contains general LP functions.
37 \*===========================================================================*/
38
39 /*===========================================================================*\
40 * This function receives the problem data (if we are running in parallel)
41 * and intitializes the data structures.
42 \*===========================================================================*/
43
lp_initialize(lp_prob * p,int master_tid)44 int lp_initialize(lp_prob *p, int master_tid)
45 {
46 #ifndef COMPILE_IN_LP
47 int msgtag, bytes, r_bufid;
48 #endif
49 #if !defined(COMPILE_IN_TM) || !defined(COMPILE_IN_LP)
50 int s_bufid;
51 #endif
52 int i, j;
53 row_data *rows;
54 var_desc **vars;
55
56 #ifdef COMPILE_IN_LP
57
58 p->master = master_tid;
59
60 #else
61
62 /* set stdout to be line buffered */
63 setvbuf(stdout, (char *)NULL, _IOLBF, 0);
64
65 register_process();
66
67 /*------------------------------------------------------------------------*\
68 * Receive tid info; request and receive problem specific data
69 \*------------------------------------------------------------------------*/
70 r_bufid = receive_msg(ANYONE, MASTER_TID_INFO);
71 bufinfo(r_bufid, &bytes, &msgtag, &p->tree_manager);
72 receive_int_array(&p->master, 1);
73 receive_int_array(&p->proc_index, 1);
74 freebuf(r_bufid);
75
76 #endif
77
78 p->lp_data = (LPdata *) calloc(1, sizeof(LPdata));
79 p->lp_data->mip = (MIPdesc *) calloc(1, sizeof(MIPdesc));
80
81 #pragma omp critical (lp_solver)
82 open_lp_solver(p->lp_data);
83
84 (void) used_time(&p->tt);
85
86 #if !defined(COMPILE_IN_TM) || !defined(COMPILE_IN_LP)
87 s_bufid = init_send(DataInPlace);
88 send_msg(p->master, REQUEST_FOR_LP_DATA);
89 freebuf(s_bufid);
90 int termcode;
91 CALL_WRAPPER_FUNCTION( receive_lp_data_u(p) );
92 #endif
93
94 if (p->par.tailoff_gap_backsteps > 0 ||
95 p->par.tailoff_obj_backsteps > 1){
96 i = MAX(5, MAX(p->par.tailoff_gap_backsteps, p->par.tailoff_obj_backsteps));
97 p->obj_history = (double *) malloc((i + 1) * DSIZE);
98 for (j = 0; j <= i; j++){
99 p->obj_history[j] = -DBL_MAX;
100 }
101 }
102 #ifndef COMPILE_IN_LP
103 if (p->par.use_cg){
104 r_bufid = receive_msg(p->tree_manager, LP__CG_TID_INFO);
105 receive_int_array(&p->cut_gen, 1);
106 freebuf(r_bufid);
107 }
108 #endif
109 p->lp_data->rows =
110 (row_data *) malloc((p->base.cutnum + BB_BUNCH) * sizeof(row_data));
111 rows = p->lp_data->rows;
112 for (i = p->base.cutnum - 1; i >= 0; i--){
113 ( rows[i].cut = (cut_data *) malloc(sizeof(cut_data)) )->coef = NULL;
114 }
115
116 if (p->base.varnum > 0){
117 vars = p->lp_data->vars = (var_desc **)
118 malloc(p->base.varnum * sizeof(var_desc *));
119 for (i = p->base.varnum - 1; i >= 0; i--){
120 vars[i] = (var_desc *) malloc( sizeof(var_desc) );
121 vars[i]->userind = p->base.userind[i];
122 vars[i]->colind = i;
123 }
124 }
125
126 /* Just to make sure this array is sufficently big */
127 p->lp_data->not_fixed = (int *) malloc(p->par.not_fixed_storage_size*ISIZE);
128 p->lp_data->tmp.iv = (int *) malloc(p->par.not_fixed_storage_size* 2*ISIZE);
129 p->lp_data->tmp.iv_size = 2*p->par.not_fixed_storage_size;
130 p->lp_data->cgl = p->par.cgl;
131
132 #ifdef COMPILE_IN_CG
133 if (!p->cgp){
134 p->cgp = (cg_prob *) calloc(1, sizeof(cg_prob));
135 }
136
137 cg_initialize(p->cgp, p->master);
138 #endif
139
140 return(FUNCTION_TERMINATED_NORMALLY);
141 }
142
143 /*===========================================================================*/
144
145 /*===========================================================================*\
146 * This function continues to dive down the current chain until told to stop
147 * by the tree manager.
148 \*===========================================================================*/
149
process_chain(lp_prob * p)150 int process_chain(lp_prob *p)
151 {
152 int termcode;
153
154 p->comp_times.lp += used_time(&p->tt);
155 /* Create the LP */
156 if ((termcode = create_subproblem_u(p)) < 0){
157 /* User had problems creating initial LP. Abandon node. */
158 p->comp_times.lp_setup+= used_time(&p->tt);
159 return(termcode);
160 }
161 p->comp_times.lp_setup += used_time(&p->tt);
162
163 p->last_gap = 0.0;
164 p->dive = CHECK_BEFORE_DIVE;
165
166 if (p->has_ub && p->par.set_obj_upper_lim) {
167 set_obj_upper_lim(p->lp_data, p->ub - p->par.granularity +
168 p->lp_data->lpetol);
169 }
170
171 if (p->colgen_strategy & COLGEN_REPRICING){
172 if (p->par.verbosity > 1){
173 printf("****************************************************\n");
174 printf("* Now repricing NODE %i LEVEL %i\n",
175 p->bc_index, p->bc_level);
176 printf("****************************************************\n\n");
177 }
178 termcode = repricing(p);
179 free_node_dependent(p);
180 }else{
181 if (p->par.verbosity > 1){
182 printf("****************************************************\n");
183 printf("* Now processing NODE %i LEVEL %i (from TM)\n",
184 p->bc_index, p->bc_level);
185 printf("****************************************************\n\n");
186 PRINT(p->par.verbosity, 4, ("Diving set to %i\n\n", p->dive));
187 }
188 termcode = fathom_branch(p);
189
190 #ifdef COMPILE_IN_LP
191 OPENMP_ATOMIC_UPDATE
192 p->tm->stat.chains++;
193 #pragma omp critical (tree_update)
194 {
195 OPENMP_ATOMIC_UPDATE
196 p->tm->active_node_num--;
197 //This should be unnecessary, as it is also done in purge_pruned_nodes
198 p->tm->active_nodes[p->proc_index] = NULL;
199 }
200 free_node_dependent(p);
201 #else
202 /* send_lp_is_free() calls free_node_dependent() */
203 send_lp_is_free(p);
204 #endif
205 }
206 p->lp_data->col_set_changed = TRUE;
207
208 p->comp_times.lp += used_time(&p->tt);
209
210 return(termcode);
211 }
212
213 /*===========================================================================*/
214
215 /*===========================================================================*\
216 * This function receives information for an active node, processes that *
217 * node and then decides which one of the children of that node should be *
218 * processed next. It then recursively processes the child until the branch *
219 * is pruned at point *
220 \*===========================================================================*/
221
fathom_branch(lp_prob * p)222 int fathom_branch(lp_prob *p)
223 {
224 LPdata *lp_data = p->lp_data;
225 node_times *comp_times = &p->comp_times;
226 char first_in_loop = TRUE;
227 int iterd, termcode, feas_status;
228 int cuts = 0, no_more_cuts_count;
229 int num_errors = 0;
230 int cut_term = 0;
231 double obj_before_cuts = 0;
232 double timeleft = 0.0;
233 int iterleft = 0;
234 const int verbosity = p->par.verbosity;
235 double now, then2, timeout2;
236 int rs_mode_enabled = FALSE;
237 #ifdef COMPILE_IN_LP
238 rs_mode_enabled = p->tm->par.rs_mode_enabled;
239 then2 = wall_clock(NULL);
240 timeout2 = p->tm->par.status_interval;
241 #endif
242 check_ub(p);
243 p->iter_num = p->node_iter_num = 0;
244
245 // TODO: replace check_bounds with a better preprocessor
246 termcode = LP_OPTIMAL; // just to initialize
247 check_bounds(p, &termcode);
248 if (termcode == LP_D_UNBOUNDED) {
249 PRINT(verbosity, 1, ("Feasibility lost -- "));
250 if (fathom(p, FALSE, FALSE)) {
251 comp_times->communication += used_time(&p->tt);
252 return(FUNCTION_TERMINATED_NORMALLY);
253 }
254 }
255
256
257 /*------------------------------------------------------------------------*\
258 * The main loop -- continue solving relaxations until no new cuts
259 * are found
260 \*------------------------------------------------------------------------*/
261
262 #ifdef COMPILE_IN_LP
263 while (p->tm->termcode == TM_UNFINISHED){
264 #else
265 while (TRUE){
266 #endif
267 if (p->par.branch_on_cuts && p->slack_cut_num > 0){
268 switch (p->par.discard_slack_cuts){
269 case DISCARD_SLACKS_WHEN_STARTING_NEW_NODE:
270 if (p->iter_num != 0)
271 break;
272 case DISCARD_SLACKS_BEFORE_NEW_ITERATION:
273 free_cuts(p->slack_cuts, p->slack_cut_num);
274 p->slack_cut_num = 0;
275 break;
276 }
277 }
278
279 #ifdef COMPILE_IN_LP
280
281 //set time limit here
282
283 if (p->tm->par.time_limit >= 0.0 &&
284 (timeleft = p->tm->par.time_limit - wall_clock(NULL) + p->tm->start_time) <= 0.0) {
285 if (fathom(p, TRUE, TRUE)){ //send in true for interrupted node
286 return(FUNCTION_TERMINATED_NORMALLY);
287 }else{
288 return(FUNCTION_TERMINATED_ABNORMALLY);
289 }
290 }
291
292 if (timeleft > 0.0){
293 set_timelim(lp_data, timeleft);
294 }
295
296
297 // set itlim here if we are in restricted search heuristic
298
299 if(rs_mode_enabled &&
300 (iterleft = p->tm->par.rs_lp_iter_limit - p->tm->lp_stat.lp_iter_num) <= 0) {
301 if (fathom(p, TRUE, FALSE)){ //send in true for interrupted node
302 return(FUNCTION_TERMINATED_NORMALLY);
303 }else{
304 return(FUNCTION_TERMINATED_ABNORMALLY);
305 }
306 }
307
308 if (iterleft > 0){
309 set_itlim(lp_data, iterleft);
310 }
311
312 #endif
313
314 p->iter_num++;
315 p->node_iter_num++;
316 lp_data->lp_count++;
317
318 PRINT(verbosity, 2,
319 ("\n\n**** Starting iteration %i ****\n\n", p->iter_num));
320
321 p->bound_changes_in_iter = 0;
322
323 if (!rs_mode_enabled && p->par.debug_lp){
324 char name[50] = "";
325 sprintf(name, "matrix.%i.%i", p->bc_index, p->iter_num);
326 write_lp(lp_data, name);
327 }
328 if ((p->iter_num < 2 && (p->par.should_warmstart_chain == FALSE ||
329 p->bc_level < 1))) {
330 if (p->bc_index == 0) {
331 PRINT(verbosity, 0, ("solving root lp relaxation\n"));
332 }
333 termcode = initial_lp_solve(lp_data, &iterd);
334 } else {
335 termcode = dual_simplex(lp_data, &iterd);
336 }
337 if (p->bc_index < 1 && p->iter_num < 2) {
338 p->root_objval = lp_data->objval;
339 if (p->par.should_reuse_lp == TRUE) {
340 save_lp(lp_data);
341 }
342 }
343 p->lp_stat.lp_calls++;
344 p->lp_stat.lp_node_calls++;
345
346 #ifdef COMPILE_IN_LP
347 OPENMP_ATOMIC_UPDATE
348 p->tm->lp_stat.lp_iter_num += iterd;
349 #endif
350
351 p->lp_stat.lp_total_iter_num += iterd;
352
353 if(iterd > p->lp_stat.lp_max_iter_num){
354 p->lp_stat.lp_max_iter_num = iterd;
355 }
356
357 /* Get relevant data */
358 //get_dj_pi(lp_data);
359 //get_slacks(lp_data);
360 //get_x(lp_data);
361
362 if(p->bc_level > 0 && p->node_iter_num < 2 && termcode == LP_OPTIMAL){
363 p->lp_stat.node_cuts_tried = 0;
364 p->lp_stat.node_cuts_forced = 0;
365 //update_solve_parameters(p);
366 update_cut_parameters(p);
367 }else if(p->bc_level < 1){
368 p->lp_stat.node_cuts_tried = TRUE;
369 if (p->node_iter_num) {
370 p->cgl_init_obj = lp_data->objval;
371 }
372 }
373
374 #if 1
375 if(p->par.use_sos_branching && p->mip->opt_sol){
376 double *opt_sol = p->mip->opt_sol;
377 double ub, lb;
378 int is_feas = TRUE;
379 for(int i = 0; i < lp_data->n; i++){
380 get_lb(lp_data, i, &lb);
381 get_ub(lp_data, i, &ub);
382 if(opt_sol[i] < lb - lp_data->lpetol || opt_sol[i] > ub + lp_data->lpetol){
383 is_feas = FALSE;
384 break;
385 }
386 }
387 if(is_feas){
388 printf("bc_ind %i termcode %i\n", p->bc_index, termcode);
389 }
390 }
391 #endif
392
393 /* display the current solution */
394 if (p->mip->obj_sense == SYM_MAXIMIZE){
395 if (termcode == LP_OPTIMAL &&
396 ((p->bc_level < 1 && p->iter_num == 1) || verbosity > 2)) {
397 PRINT(verbosity, 0, ("The LP value is: %.3f [%i,%i]\n\n",
398 -lp_data->objval + p->mip->obj_offset,
399 termcode, iterd));
400 }
401
402 }else{
403 if (termcode == LP_OPTIMAL &&
404 ((p->bc_level < 1 && p->iter_num == 1) || verbosity > 2)) {
405 PRINT(verbosity, 0, ("The LP value is: %.3f [%i,%i]\n\n",
406 lp_data->objval+ p->mip->obj_offset,
407 termcode, iterd));
408 }
409 }
410 switch (termcode){
411 case LP_D_INFEASIBLE: /* this is impossible (?) as of now */
412 return(ERROR__DUAL_INFEASIBLE);
413 case LP_D_ITLIM:
414 case LP_TIME_LIMIT:
415 /* now, we set time limit - solver returns the same termcode with itlim */
416 /* also, we might set iter limit if we are in search heuristics */
417 if (fathom(p, TRUE, FALSE)){ //send in true for interrupted node
418 return(FUNCTION_TERMINATED_NORMALLY);
419 }else{
420 return(FUNCTION_TERMINATED_ABNORMALLY);
421 }
422 case LP_ABANDONED:
423 if (!rs_mode_enabled){
424 printf("####### Unexpected termcode: %i \n", termcode);
425 }
426 if (p->par.try_to_recover_from_error && (++num_errors == 1)){
427 /* Try to resolve it from scratch */
428 if (!rs_mode_enabled){
429 printf("####### Trying to recover by resolving from scratch...\n");
430 }
431 continue;
432 }else{
433 if (!rs_mode_enabled){
434 char name[50] = "";
435 printf("####### Recovery failed. %s%s",
436 "LP solver is having numerical difficulties :(.\n",
437 "####### Dumping current LP to MPS file and exiting.\n\n");
438 sprintf(name, "matrix.%i.%i", p->bc_index, p->iter_num);
439 write_mps(lp_data, name);
440 }
441 return(ERROR__NUMERICAL_INSTABILITY);
442 }
443
444 case LP_D_UNBOUNDED: /* the primal problem is infeasible */
445 case LP_D_OBJLIM:
446 case LP_OPTIMAL:
447 if (num_errors == 1 && !rs_mode_enabled){
448 printf("####### Recovery succeeded! Continuing with node...\n\n");
449 num_errors = 0;
450 }
451 if (termcode == LP_D_UNBOUNDED){
452 PRINT(verbosity, 1, ("Feasibility lost -- "));
453 #if 0
454 char name[50] = "";
455 sprintf(name, "matrix.%i.%i", p->bc_index, p->iter_num);
456 write_mps(lp_data, name);
457 #endif
458 }else if ((p->has_ub && lp_data->objval > p->ub - p->par.granularity +
459 p->lp_data->lpetol) ||
460 termcode == LP_D_OBJLIM){
461 PRINT(verbosity, 1, ("Terminating due to high cost -- "));
462 }else{ /* optimal and not too high cost */
463 #ifdef COMPILE_IN_LP
464 #ifdef DO_TESTS
465 if (lp_data->objval < p->tm->lb - .001 && p->bc_index > 0){
466 printf("#####Warning: lower bound corruption detected\n");
467 }
468 #endif
469 p->tm->active_nodes[p->proc_index]->lower_bound = lp_data->objval;
470 if (p->node_iter_num < 2 && p->bc_index > 0 &&
471 p->par.should_use_rel_br) {
472 update_pcost(p);
473 }
474 if (cuts > 0) {
475 p->lp_stat.cuts_added_to_lps += cuts;
476 }
477 if (p->node_iter_num > 0 && p->bc_level > 0) {
478 if (cuts > 0) {
479 p->lp_stat.num_cuts_added_in_path += cuts;
480 }
481 if (p->lp_stat.avg_cuts_obj_impr_in_path > 0) {
482 p->lp_stat.avg_cuts_obj_impr_in_path =
483 (p->lp_stat.avg_cuts_obj_impr_in_path *
484 (p->lp_stat.num_cut_iters_in_path-1) + p->lp_data->objval -
485 obj_before_cuts)/p->lp_stat.num_cut_iters_in_path;
486 }
487 }
488
489 if(p->node_iter_num > 1){
490 p->lp_stat.end_objval = lp_data->objval;
491 }else{
492 p->lp_stat.end_objval = p->lp_stat.start_objval =
493 lp_data->objval;
494 }
495
496 obj_before_cuts = lp_data->objval;
497 comp_times->lp += used_time(&p->tt);
498 #endif
499 break;
500 }
501 comp_times->lp += used_time(&p->tt);
502 if (fathom(p, (termcode != LP_D_UNBOUNDED), FALSE)){
503 comp_times->communication += used_time(&p->tt);
504 return(FUNCTION_TERMINATED_NORMALLY);
505 }else{
506 first_in_loop = FALSE;
507 comp_times->communication += used_time(&p->tt);
508 continue;
509 }
510 }
511
512 /* If come to here, the termcode must have been OPTIMAL and the
513 * cost cannot be too high. */
514 /* is_feasible_u() fills up lp_data->x, too!! */
515 feas_status = is_feasible_u(p, FALSE, FALSE);
516 if (feas_status == IP_FEASIBLE ||
517 (feas_status == IP_HEUR_FEASIBLE && p->par.find_first_feasible)){
518 cuts = -1;
519 }else{
520 /*------------------------------------------------------------------*\
521 * send the current solution to the cut generator, and also to the
522 * cut pool if we are either
523 * - at the beginning of a chain (but not in the root in the
524 * first phase)
525 * - or this is the cut_pool_check_freq-th iteration.
526 \*------------------------------------------------------------------*/
527 cuts = 0;
528 no_more_cuts_count = 0;
529 if (p->cut_pool &&
530 ((first_in_loop && (p->bc_level>0 || p->phase==1)) ||
531 (p->iter_num % p->par.cut_pool_check_freq == 0)) ){
532 no_more_cuts_count += send_lp_solution_u(p, p->cut_pool);
533 }
534 if (p->cut_gen){
535 no_more_cuts_count += send_lp_solution_u(p, p->cut_gen);
536 }
537
538 if (verbosity > 4){
539 printf ("Now displaying the relaxed solution ...\n");
540 display_lp_solution_u(p, DISP_RELAXED_SOLUTION);
541 }
542
543 comp_times->lp += used_time(&p->tt);
544
545 tighten_bounds(p);
546
547 comp_times->fixing += used_time(&p->tt);
548
549 if (!first_in_loop){
550 cuts = check_row_effectiveness(p);
551 }
552
553 /*------------------------------------------------------------------*\
554 * receive the cuts from the cut generator and the cut pool
555 \*------------------------------------------------------------------*/
556
557 #ifdef USE_SYM_APPLICATION
558 if ((cut_term = receive_cuts(p, first_in_loop,
559 no_more_cuts_count)) >=0 ){
560 cuts += cut_term;
561 }else{
562 return(ERROR__USER);
563 }
564 #else
565 if (!check_tailoff(p)) {
566 if ((cut_term = receive_cuts(p, first_in_loop,
567 no_more_cuts_count)) >=0 ){
568 cuts += cut_term;
569 }else{
570 return(ERROR__USER);
571 }
572 }
573 #endif
574 }
575
576 comp_times->lp += used_time(&p->tt);
577 if (cuts < 0){ /* i.e. feasible solution is found */
578 if (fathom(p, TRUE, FALSE)){
579 return(FUNCTION_TERMINATED_NORMALLY);
580 }else{
581 first_in_loop = FALSE;
582 check_ub(p);
583 continue;
584 }
585 }
586
587 PRINT(verbosity, 2,
588 ("\nIn iteration %i, before calling branch()\n", p->iter_num));
589 if (cuts == 0){
590 PRINT(verbosity, 2, ("... no cuts were added.\n"));
591 if (verbosity > 4){
592 printf("Now displaying final relaxed solution...\n\n");
593 display_lp_solution_u(p, DISP_FINAL_RELAXED_SOLUTION);
594 }
595 }else{
596 PRINT(verbosity, 2, ("... %i violated cuts were added\n", cuts));
597 }
598
599 comp_times->lp += used_time(&p->tt);
600
601 switch (cuts = branch(p, cuts)){
602
603 case NEW_NODE:
604 #ifndef ROOT_NODE_ONLY
605 if (verbosity > 1){
606 printf("*************************************************\n");
607 printf("* Now processing NODE %i LEVEL %i\n",
608 p->bc_index, p->bc_level);
609 printf("*************************************************\n\n");
610 }
611 p->node_iter_num = 0;
612
613 #ifdef COMPILE_IN_LP
614 #pragma omp master
615 {
616 now = wall_clock(NULL);
617 if (now - then2 > timeout2){
618 if(verbosity >= -1 ){
619 print_tree_status(p->tm);
620 }
621 then2 = now;
622 }
623 }
624 #endif
625 /*
626 printf("node = %d\n", p->bc_index);
627 printf("cut iters = %d\n", p->lp_stat.num_cut_iters_in_path);
628 printf("cuts added = %d\n", p->lp_stat.num_cuts_added_in_path);
629 printf("cut removed = %d\n", p->lp_stat.num_cuts_slacked_out_in_path);
630 printf("cut obj impr = %f\n", p->lp_stat.avg_cuts_obj_impr_in_path);
631
632 printf("strong br cands = %d\n", p->lp_stat.num_str_br_cands_in_path);
633 printf("str br impr = %f\n", p->lp_stat.avg_br_obj_impr_in_path);
634
635 printf("fp calls = %d\n", p->lp_stat.num_fp_calls_in_path);
636 */
637 break;
638 #endif
639 case FATHOMED_NODE:
640 comp_times->strong_branching += used_time(&p->tt);
641 return(FUNCTION_TERMINATED_NORMALLY);
642
643 case BRANCHING_INF_NODE:
644 comp_times->strong_branching += used_time(&p->tt);
645 if (fathom(p, FALSE, FALSE)){
646 return(FUNCTION_TERMINATED_NORMALLY);
647 }else{
648 return(FUNCTION_TERMINATED_ABNORMALLY);
649 }
650
651 case ERROR__NO_BRANCHING_CANDIDATE: /* Something went wrong */
652 return(ERROR__NO_BRANCHING_CANDIDATE);
653
654 case FEAS_SOL_FOUND:
655 PRINT(verbosity,2,("solution found before branching\n"));
656 if(p->par.find_first_feasible){
657 if(fathom(p, TRUE, FALSE)){ //send in true for interrupted node
658 return(FUNCTION_TERMINATED_NORMALLY);
659 }else{
660 return(FUNCTION_TERMINATED_ABNORMALLY);
661 }
662 }
663 default: /* the return value is the number of cuts added */
664 if (verbosity > 2){
665 printf("Continue with this node.");
666 if (cuts > 0)
667 printf(" %i cuts added altogether in iteration %i\n",
668 cuts, p->iter_num);
669 if (p->bound_changes_in_iter > 0) {
670 printf(" %i bounds added altogether in iteration %i\n",
671 p->bound_changes_in_iter, p->iter_num);
672 }
673 printf("\n\n");
674 }
675 #ifdef DO_TESTS
676 if (cuts == 0 && p->bound_changes_in_iter == 0){
677 printf("Error! Told not to branch, but there are no new cuts or ");
678 printf("bound changes!\n");
679 return(ERROR__NO_BRANCHING_CANDIDATE);
680 }
681 #endif
682 break;
683 }
684 comp_times->strong_branching += used_time(&p->tt);
685
686 check_ub(p);
687 first_in_loop = FALSE;
688
689 #ifdef COMPILE_IN_LP
690 char gap_limit_reached = FALSE;
691 if(p->has_ub && p->tm->par.gap_limit >= 0.0 &&
692 (p->tm->samephase_candnum > 1 || p->tm->active_node_num > 1)){
693 //find_tree_lb(p->tm);
694 if (d_gap(p->tm->ub, MIN(p->tm->lb, lp_data->objval), p->mip->obj_offset, p->mip->obj_sense) <= p->tm->par.gap_limit){
695 gap_limit_reached = TRUE;
696 }
697 }
698 //if(p->par.rs_mode_enabled)
699 // printf("tm-lp-iter %i %i \n", p->tm->lp_stat.lp_iter_num, p->tm->par.rs_lp_iter_limit);
700 if(p->par.rs_mode_enabled && p->tm->lp_stat.lp_iter_num > p->par.rs_lp_iter_limit){
701 gap_limit_reached = TRUE;
702 }
703
704 if (gap_limit_reached ||
705 (p->tm->par.time_limit >= 0.0 &&
706 wall_clock(NULL) - p->tm->start_time >= p->tm->par.time_limit)){
707 if (fathom(p, TRUE, ((gap_limit_reached) ? FALSE : TRUE))){
708 return(FUNCTION_TERMINATED_NORMALLY);
709 }else{
710 return(FUNCTION_TERMINATED_ABNORMALLY);
711 }
712 }
713 #else
714 if (p->par.time_limit >= 0.0 &&
715 wall_clock(NULL) - p->start_time >= p->par.time_limit){
716 if (fathom(p, TRUE, TRUE)){
717 return(FUNCTION_TERMINATED_NORMALLY);
718 }else{
719 return(FUNCTION_TERMINATED_ABNORMALLY);
720 }
721 }
722 #endif
723 }
724
725 comp_times->lp += used_time(&p->tt);
726
727 return(FUNCTION_TERMINATED_NORMALLY);
728 }
729
730 /*===========================================================================*/
731
732 /* fathom() returns true if it has really fathomed the node, false otherwise
733 (i.e., if it had added few variables) */
734
735 int fathom(lp_prob *p, int primal_feasible, int time_limit_reached)
736 {
737 LPdata *lp_data = p->lp_data;
738 our_col_set *new_cols = NULL;
739 int new_vars;
740 int colgen = p->colgen_strategy & COLGEN__FATHOM;
741 int termcode = p->lp_data->termcode;
742
743 #ifdef COMPILE_IN_LP
744 if(p->branch_dir == 'L' && p->branch_var >= 0){
745 p->br_inf_down[p->branch_var]++;
746 }else{
747 p->br_inf_up[p->branch_var]++;
748 }
749 #endif
750
751 if (p->lp_data->nf_status == NF_CHECK_NOTHING){
752 PRINT(p->par.verbosity, 1,
753 ("fathoming node (no more cols to check)\n\n"));
754 if (primal_feasible){
755 if (time_limit_reached) {
756 send_node_desc(p, TIME_LIMIT);
757 } else {
758 switch (termcode){
759 case LP_OPT_FEASIBLE:
760 send_node_desc(p, FEASIBLE_PRUNED);
761 break;
762 case LP_OPTIMAL:
763 send_node_desc(p, OVER_UB_PRUNED);
764 break;
765 case LP_D_ITLIM:
766 send_node_desc(p, ITERATION_LIMIT);
767 break;
768 case LP_TIME_LIMIT:
769 send_node_desc(p, TIME_LIMIT);
770 break;
771 default:
772 send_node_desc(p, OVER_UB_PRUNED);
773 break;
774 }
775 }
776 }else{
777 send_node_desc(p, INFEASIBLE_PRUNED);
778 }
779 return(TRUE);
780 }
781
782 if (p->colgen_strategy & COLGEN_REPRICING)
783 colgen = FATHOM__GENERATE_COLS__RESOLVE;
784
785 switch (colgen){
786 case FATHOM__DO_NOT_GENERATE_COLS__DISCARD:
787 PRINT(p->par.verbosity, 1, ("Pruning node\n\n"));
788 send_node_desc(p, termcode == LP_OPT_FEASIBLE ? FEASIBLE_PRUNED :
789 DISCARDED_NODE);
790 return(TRUE);
791
792 case FATHOM__DO_NOT_GENERATE_COLS__SEND:
793 PRINT(p->par.verbosity, 1, ("Sending node for pricing\n\n"));
794 send_node_desc(p, primal_feasible ? OVER_UB_HOLD_FOR_NEXT_PHASE :
795 INFEASIBLE_HOLD_FOR_NEXT_PHASE);
796 return(TRUE);
797
798 case FATHOM__GENERATE_COLS__RESOLVE:
799 check_ub(p);
800 /* Note that in case of COLGEN_REPRICING we must have UB. */
801 if (! p->has_ub){
802 PRINT(p->par.verbosity, 1,
803 ("\nCan't generate cols before sending (no UB)\n"));
804 send_node_desc(p, primal_feasible ? OVER_UB_HOLD_FOR_NEXT_PHASE :
805 INFEASIBLE_HOLD_FOR_NEXT_PHASE);
806 return(TRUE);
807 }
808 PRINT(p->par.verbosity, 1,
809 ("\nGenerating columns before fathoming/resolving\n"));
810 new_cols = price_all_vars(p);
811 p->comp_times.pricing += used_time(&p->tt);
812 new_vars = new_cols->num_vars + new_cols->rel_ub + new_cols->rel_lb;
813 if (new_cols->dual_feas == NOT_TDF){
814 /* Don't have total dual feasibility. The non-dual-feasible vars
815 * have already been added. Go back and resolve. */
816 PRINT(p->par.verbosity, 2,
817 ("%i variables added in price-out.\n", new_vars));
818 free_col_set(&new_cols);
819 return(FALSE);
820 }
821 /* Now we know that we have total dual feasibility */
822 if ((p->has_ub && lp_data->objval > p->ub - p->par.granularity +
823 p->lp_data->lpetol) ||
824 termcode == LP_D_OBJLIM || termcode == LP_OPT_FEASIBLE){
825 /* fathomable */
826 if (termcode == LP_D_OBJLIM ||
827 (p->has_ub && lp_data->objval > p->ub - p->par.granularity +
828 p->lp_data->lpetol)){
829 PRINT(p->par.verbosity, 1,
830 ("Fathoming node (discovered tdf & high cost)\n\n"));
831 }else{
832 PRINT(p->par.verbosity, 1,
833 ("Fathoming node (discovered tdf & feasible)\n\n"));
834 }
835 send_node_desc(p, termcode == LP_OPT_FEASIBLE ? FEASIBLE_PRUNED :
836 OVER_UB_PRUNED);
837 free_col_set(&new_cols);
838 return(TRUE);
839 }
840 /* If we ever arrive here then we must have tdf and the function
841 * was called with a primal infeasible LP.
842 *
843 * Again, note that in case of COLGEN_REPRICING, since we do that
844 * only in the root node, the lp relaxation MUST be primal feasible,
845 *
846 * If TDF_HAS_ALL, then whatever can be used to restore
847 * primal feasibility is already in the matrix so don't bother
848 * to figure out restorability, just return and resolve the problem
849 * (if new_vars == 0 then even returning is unnecessary, the node
850 * can be fathomed, nothing can restore feasibility).
851 */
852 if (new_cols->dual_feas == TDF_HAS_ALL){
853 if (new_vars == 0){
854 PRINT(p->par.verbosity, 1,
855 ("fathoming node (no more cols to check)\n\n"));
856 send_node_desc(p, INFEASIBLE_PRUNED);
857 free_col_set(&new_cols);
858 return(TRUE);
859 }else{
860 free_col_set(&new_cols);
861 return(FALSE);
862 }
863 }
864 /* Sigh. There were too many variables not fixable even though we have
865 * proved tdf. new_cols contains a good many of the non-fixables, use
866 * new_cols to start with in restore_lp_feasibility(). */
867 if (! restore_lp_feasibility(p, new_cols)){
868 PRINT(p->par.verbosity, 1,
869 ("Fathoming node (discovered tdf & not restorable inf.)\n\n"));
870 send_node_desc(p, INFEASIBLE_PRUNED);
871 free_col_set(&new_cols);
872 return(TRUE);
873 }
874 /* So primal feasibility is restorable. Exactly one column has been
875 * added (released or a new variable) to destroy the proof of
876 * infeasibility */
877 free_col_set(&new_cols);
878 p->comp_times.pricing += used_time(&p->tt);
879 return(FALSE);
880 }
881
882 return(TRUE); /* fake return */
883 }
884
885 /*****************************************************************************/
886 /*****************************************************************************/
887 /* NOTE: this version of repricing works ONLY for repricing in the root node */
888 /*****************************************************************************/
889 /*****************************************************************************/
890
891 int repricing(lp_prob *p)
892 {
893 LPdata *lp_data = p->lp_data;
894 node_times *comp_times = &p->comp_times;
895 int iterd, termcode;
896 int num_errors = 0;
897 our_col_set *new_cols = NULL;
898 int dual_feas, new_vars, cuts, no_more_cuts_count;
899 int cut_term = 0;
900
901 check_ub(p);
902 p->iter_num = 0;
903
904 /*------------------------------------------------------------------------*\
905 * The main loop -- continue solving relaxations until TDF
906 \*------------------------------------------------------------------------*/
907
908 while (TRUE){
909 p->iter_num++;
910
911 PRINT(p->par.verbosity, 2,
912 ("\n\n**** Starting iteration %i ****\n\n", p->iter_num));
913
914 termcode = dual_simplex(lp_data, &iterd);
915 p->lp_stat.lp_calls++;
916 /* Get relevant data */
917 get_dj_pi(lp_data);
918 get_slacks(lp_data);
919
920 /* display the current solution */
921 if (p->mip->obj_sense == SYM_MAXIMIZE){
922 PRINT(p->par.verbosity, 2, ("The LP value is: %.3f [%i,%i]\n\n",
923 -lp_data->objval + p->mip->obj_offset,
924 termcode, iterd));
925
926 }else{
927 PRINT(p->par.verbosity, 2, ("The LP value is: %.3f [%i,%i]\n\n",
928 lp_data->objval+ p->mip->obj_offset,
929 termcode, iterd));
930 }
931 comp_times->lp += used_time(&p->tt);
932
933 switch (termcode){
934 case LP_D_ITLIM: /* impossible, since itlim is set to infinity */
935 case LP_D_INFEASIBLE: /* this is impossible (?) as of now */
936 case LP_ABANDONED:
937 printf("######## Unexpected termcode: %i \n", termcode);
938 if (p->par.try_to_recover_from_error && (++num_errors == 1)){
939 /* Try to resolve it from scratch */
940 printf("######## Trying to recover by resolving from scratch...\n");
941
942 continue;
943 }else{
944 char name[50] = "";
945 printf("######## Recovery failed. %s%s",
946 "LP solver is having numerical difficulties :(.\n",
947 "######## Dumping current LP to MPS file and exiting.\n\n");
948 sprintf(name, "matrix.%i.%i", p->bc_index, p->iter_num);
949 write_mps(lp_data, name);
950 return(ERROR__NUMERICAL_INSTABILITY);
951 }
952
953 case LP_D_UNBOUNDED: /* the primal problem is infeasible */
954 case LP_D_OBJLIM:
955 case LP_OPTIMAL:
956 if (termcode == LP_D_UNBOUNDED){
957 PRINT(p->par.verbosity, 1, ("Feasibility lost -- "));
958 }else if ((p->has_ub && lp_data->objval > p->ub - p->par.granularity +
959 p->lp_data->lpetol)
960 || termcode == LP_D_OBJLIM){
961 PRINT(p->par.verbosity, 1, ("Terminating due to high cost -- "));
962 }else{ /* optimal and not too high cost */
963 break;
964 }
965 comp_times->lp += used_time(&p->tt);
966 if (fathom(p, (termcode != LP_D_UNBOUNDED), FALSE)){
967 comp_times->communication += used_time(&p->tt);
968 return(FUNCTION_TERMINATED_NORMALLY);
969 }else{
970 comp_times->communication += used_time(&p->tt);
971 continue;
972 }
973 }
974
975 /* If come to here, the termcode must have been OPTIMAL and the
976 * cost cannot be too high. */
977 /* is_feasible_u() fills up lp_data->x, too!! */
978 if (is_feasible_u(p, FALSE, FALSE) == IP_FEASIBLE){
979 if (p->par.verbosity > 2){
980 printf ("Now displaying the feasible solution ...\n");
981 display_lp_solution_u(p, DISP_FEAS_SOLUTION);
982 }
983 cuts = -1;
984 }else{
985
986 /*------------------------------------------------------------------*\
987 * send the current solution to the cut generator, and also to the
988 * cut pool if this is the 1st or cut_pool_check_freq-th iteration.
989 \*------------------------------------------------------------------*/
990
991 no_more_cuts_count = 0;
992 if (p->cut_pool &&
993 ((p->iter_num-1) % p->par.cut_pool_check_freq == 0) ){
994 no_more_cuts_count += send_lp_solution_u(p, p->cut_pool);
995 }
996 if (p->cut_gen){
997 no_more_cuts_count += send_lp_solution_u(p, p->cut_gen);
998 }
999
1000 if (p->par.verbosity > 4){
1001 printf ("Now displaying the relaxed solution ...\n");
1002 display_lp_solution_u(p, DISP_RELAXED_SOLUTION);
1003 }
1004
1005 comp_times->lp += used_time(&p->tt);
1006
1007 tighten_bounds(p);
1008
1009 comp_times->fixing += used_time(&p->tt);
1010
1011 cuts = 0;
1012 if (p->cut_gen || p->cut_pool){
1013 cuts = check_row_effectiveness(p);
1014 }
1015
1016 /*------------------------------------------------------------------*\
1017 * receive the cuts from the cut generator and the cut pool
1018 \*------------------------------------------------------------------*/
1019 if ((cut_term = receive_cuts(p, TRUE, no_more_cuts_count)) >= 0){
1020 cuts += cut_term;
1021 }else{
1022 return(ERROR__USER);
1023 }
1024 }
1025
1026 comp_times->lp += used_time(&p->tt);
1027 if (cuts < 0){ /* i.e. feasible solution is found */
1028 if (fathom(p, TRUE, FALSE)){
1029 comp_times->communication += used_time(&p->tt);
1030 return(FUNCTION_TERMINATED_NORMALLY);
1031 }else{
1032 comp_times->communication += used_time(&p->tt);
1033 check_ub(p);
1034 continue;
1035 }
1036 }
1037
1038 if (cuts == 0){
1039 PRINT(p->par.verbosity, 2,
1040 ("\nIn iteration %i ... no cuts were added.\n", p->iter_num));
1041 }else{
1042 /* Go back to top */
1043 PRINT(p->par.verbosity, 2,
1044 ("\nIn iteration %i ... %i violated cuts were added.\n",
1045 p->iter_num, cuts));
1046 continue;
1047 }
1048
1049 comp_times->lp += used_time(&p->tt);
1050
1051 /* So no cuts were found. Price out everything */
1052 new_cols = price_all_vars(p);
1053 new_vars = new_cols->num_vars + new_cols->rel_ub + new_cols->rel_lb;
1054 dual_feas = new_cols->dual_feas;
1055 free_col_set(&new_cols);
1056 comp_times->pricing += used_time(&p->tt);
1057 if (dual_feas != NOT_TDF)
1058 break;
1059
1060 /* Don't have total dual feasibility. The non-dual-feasible vars
1061 * have already been added. Go back and resolve. */
1062 PRINT(p->par.verbosity, 2,
1063 ("%i variables added in price-out.\n", new_vars));
1064 }
1065
1066 /* Now we know that we have TDF, just send back the node */
1067 comp_times->lp += used_time(&p->tt);
1068 send_node_desc(p, REPRICED_NODE);
1069 comp_times->communication += used_time(&p->tt);
1070
1071 return(FUNCTION_TERMINATED_NORMALLY);
1072 }
1073
1074 /*===========================================================================*/
1075
1076 int bfind(int key, int *table, int size)
1077 {
1078 int i = 0, k = size;
1079 int j = size >> 1; /* the element to be probed */
1080 while ( i < k ){
1081 if (table[j] == key){
1082 return(j);
1083 }else if (table[j] < key){
1084 i = j + 1;
1085 }else{
1086 k = j;
1087 }
1088 j = (i + k) >> 1;
1089 }
1090 return(j-1); /* key is not found and it is between the (j-1)st and j-th */
1091 }
1092
1093 /*===========================================================================*/
1094
1095 int collect_nonzeros(lp_prob *p, double *x, int *tind, double *tx)
1096 {
1097 var_desc **vars = p->lp_data->vars;
1098 int n = p->lp_data->n;
1099 int i, cnt = 0;
1100 double lpetol = p->lp_data->lpetol;
1101
1102 if (p->par.is_userind_in_order != TRUE) {
1103 colind_sort_extra(p);
1104 for (i = 0; i < n; i++){
1105 if (x[i] > lpetol || x[i] < -lpetol){
1106 tind[cnt] = vars[i]->userind;
1107 tx[cnt++] = x[i];
1108 }
1109 }
1110 /* order indices and values according to indices */
1111 qsort_id(tind, tx, cnt);
1112 } else {
1113 for (i = 0; i < n; i++){
1114 if (x[i] > lpetol || x[i] < -lpetol){
1115 tind[cnt] = i;
1116 tx[cnt++] = x[i];
1117 }
1118 }
1119 }
1120 return(cnt);
1121 }
1122
1123 /*===========================================================================*/
1124
1125 int collect_fractions(lp_prob *p, double *x, int *tind, double *tx)
1126 {
1127 var_desc **vars = p->lp_data->vars;
1128 int n = p->lp_data->n;
1129 int i, cnt = 0;
1130 double lpetol = p->lp_data->lpetol, xi;
1131
1132 colind_sort_extra(p);
1133 for (i = 0; i < n; i++){
1134 xi = x[i];
1135 if (xi - floor(xi) > lpetol && ceil(xi) - xi > lpetol){
1136 tind[cnt] = vars[i]->userind;
1137 tx[cnt++] = x[i];
1138 }
1139 }
1140 /* order indices and values according to indices */
1141 qsort_id(tind, tx, cnt);
1142 return(cnt);
1143 }
1144
1145 /*===========================================================================*/
1146
1147 int collect_int_fractions(lp_prob *p, double *x, int *tind, double *tx, int *int_cnt)
1148 {
1149 var_desc **vars = p->lp_data->vars;
1150 int n = p->lp_data->n;
1151 int i, cnt = 0, i_cnt = 0;
1152 double lpetol = p->lp_data->lpetol, xi;
1153
1154 for (i = 0; i < n; i++){
1155 if (vars[i]->is_int){
1156 i_cnt++;
1157 xi = x[i];
1158 if (xi - floor(xi) > lpetol && ceil(xi) - xi > lpetol){
1159 tind[cnt] = vars[i]->userind;
1160 tx[cnt++] = x[i];
1161 }
1162 }
1163 }
1164 *int_cnt = i_cnt;
1165 return(cnt);
1166 }
1167
1168 /*===========================================================================*/
1169
1170 node_desc *create_explicit_node_desc(lp_prob *p)
1171 {
1172 LPdata *lp_data = p->lp_data;
1173 int m = lp_data->m, n = lp_data->n;
1174
1175 int bvarnum = p->base.varnum;
1176 var_desc **extravars = lp_data->vars + bvarnum;
1177 int extravarnum = n - bvarnum;
1178
1179 int bcutnum = p->base.cutnum;
1180 row_data *rows = lp_data->rows;
1181 int extrarownum = m - bcutnum;
1182 int cutindsize;
1183
1184 node_desc *desc = (node_desc *) calloc(1, sizeof(node_desc));
1185
1186 /* Will need these anyway for basis */
1187 int *rstat = (int *) malloc(m * ISIZE);
1188 int *cstat = (int *) malloc(n * ISIZE);
1189 int *erstat = (extrarownum == 0) ? NULL : (int *) malloc(extrarownum*ISIZE);
1190 int *ecstat = (extravarnum == 0) ? NULL : (int *) malloc(extravarnum*ISIZE);
1191
1192 int *ulist, *clist; /* this later uses tmp.i1 */
1193 int cutcnt, i, j;
1194 #ifndef COMPILE_IN_LP
1195 int s_bufid, r_bufid;
1196 #endif
1197
1198 get_basis(lp_data, cstat, rstat);
1199 if (extrarownum > 0)
1200 memcpy(erstat, rstat + bcutnum, extrarownum * ISIZE);
1201 if (extravarnum > 0)
1202 memcpy(ecstat, cstat + bvarnum, extravarnum * ISIZE);
1203
1204 /* To start with, send the non-indexed cuts (only those which will be
1205 saved) to the treemanager and ask for names */
1206 for (cutcnt = cutindsize = 0, i = bcutnum; i < m; i++){
1207 if ((rows[i].cut->branch & CUT_BRANCHED_ON) ||
1208 !rows[i].free || (rows[i].free && rstat[i] != SLACK_BASIC)){
1209 cutindsize++;
1210 if (rows[i].cut->name < 0)
1211 cutcnt++;
1212 }
1213 }
1214 if (cutcnt > 0){
1215 #ifdef COMPILE_IN_LP
1216 row_data *tmp_rows = (row_data *) malloc(cutcnt*sizeof(row_data));
1217
1218 for (j = 0, i = bcutnum; j < cutcnt; i++){
1219 if (rows[i].cut->name < 0 &&
1220 (!rows[i].free || (rows[i].free && rstat[i] != SLACK_BASIC)))
1221 tmp_rows[j++] = rows[i];
1222 }
1223 unpack_cut_set(p->tm, 0, cutcnt, tmp_rows);
1224 FREE(tmp_rows);
1225 #else
1226 s_bufid = init_send(DataInPlace);
1227 send_int_array(&cutcnt, 1);
1228 for (i = bcutnum; i < m; i++){
1229 if (rows[i].cut->name < 0 &&
1230 (!rows[i].free || (rows[i].free && rstat[i] != SLACK_BASIC)))
1231 pack_cut(rows[i].cut);
1232 }
1233 send_msg(p->tree_manager, LP__CUT_NAMES_REQUESTED);
1234 freebuf(s_bufid);
1235 #endif
1236 }
1237
1238 /* create the uind list and the extravars basis description */
1239 desc->uind.type = EXPLICIT_LIST;
1240 desc->uind.added = 0;
1241 desc->uind.size = extravarnum;
1242 desc->basis.extravars.type = EXPLICIT_LIST;
1243 desc->basis.extravars.size = extravarnum;
1244 desc->basis.extravars.list = NULL;
1245 if (extravarnum > 0){
1246 desc->uind.list = ulist = (int *) malloc(extravarnum * ISIZE);
1247 desc->basis.extravars.stat = ecstat;
1248 for (i = extravarnum - 1; i >= 0; i--)
1249 ulist[i] = extravars[i]->userind;
1250 if (lp_data->ordering == COLIND_ORDERED)
1251 qsort_ii(ulist, ecstat, extravarnum);
1252 }else{
1253 desc->uind.list = NULL;
1254 desc->basis.extravars.stat = NULL;
1255 }
1256 /* create the basevars basis description */
1257 desc->basis.basevars.type = EXPLICIT_LIST;
1258 desc->basis.basevars.size = bvarnum;
1259 desc->basis.basevars.list = NULL;
1260 if (bvarnum)
1261 desc->basis.basevars.stat = cstat;
1262 else
1263 FREE(cstat);
1264
1265 /* create the not_fixed list */
1266 desc->nf_status = lp_data->nf_status;
1267 if (desc->nf_status == NF_CHECK_AFTER_LAST ||
1268 desc->nf_status == NF_CHECK_UNTIL_LAST){
1269 desc->not_fixed.type = EXPLICIT_LIST;
1270 desc->not_fixed.added = 0;
1271 if ((desc->not_fixed.size = lp_data->not_fixed_num) > 0){
1272 desc->not_fixed.list = (int *) malloc(desc->not_fixed.size * ISIZE);
1273 memcpy(desc->not_fixed.list, lp_data->not_fixed,
1274 lp_data->not_fixed_num * ISIZE);
1275 }else{
1276 desc->not_fixed.list = NULL;
1277 }
1278 }
1279
1280 #ifndef COMPILE_IN_LP
1281 /* At this point we will need the missing names */
1282 if (cutcnt > 0){
1283 static struct timeval tout = {15, 0};
1284 int *names = lp_data->tmp.i1; /* m */
1285 double start = wall_clock(NULL);
1286 do{
1287 r_bufid = treceive_msg(p->tree_manager, LP__CUT_NAMES_SERVED, &tout);
1288 if (! r_bufid){
1289 if (pstat(p->tree_manager) != PROCESS_OK){
1290 printf("TM has died -- LP exiting\n\n");
1291 exit(-301);
1292 }
1293 }
1294 }while (! r_bufid);
1295 p->comp_times.idle_names += wall_clock(NULL) - start;
1296 receive_int_array(names, cutcnt);
1297 for (j = 0, i = bcutnum; j < cutcnt; i++){
1298 if (rows[i].cut->name < 0 &&
1299 (!rows[i].free || (rows[i].free && rstat[i] != SLACK_BASIC)))
1300 rows[i].cut->name = names[j++];
1301 }
1302 }
1303 #endif
1304
1305 /* create the cutind list and the extrarows basis description */
1306 desc->cutind.type = EXPLICIT_LIST;
1307 desc->cutind.added = 0;
1308 desc->cutind.size = cutindsize;
1309 desc->basis.extrarows.type = EXPLICIT_LIST;
1310 desc->basis.extrarows.list = NULL;
1311 desc->basis.extrarows.size = cutindsize;
1312 if (cutindsize > 0){
1313 desc->cutind.list = clist = (int *) malloc(cutindsize * ISIZE);
1314 desc->basis.extrarows.stat = erstat;
1315 for (cutindsize = 0, i = bcutnum; i < m; i++){
1316 if ((rows[i].cut->branch & CUT_BRANCHED_ON) ||
1317 !rows[i].free || (rows[i].free && rstat[i] != SLACK_BASIC)){
1318 clist[cutindsize] = rows[i].cut->name;
1319 erstat[cutindsize++] = rstat[i];
1320 }
1321 }
1322 qsort_ii(clist, erstat, cutindsize);
1323 }else{
1324 desc->cutind.list = NULL;
1325 desc->basis.extrarows.stat = NULL;
1326 }
1327 /* create the baserows basis description */
1328 desc->basis.baserows.type = EXPLICIT_LIST;
1329 desc->basis.baserows.size = bcutnum;
1330 desc->basis.baserows.list = NULL;
1331 if (bcutnum)
1332 desc->basis.baserows.stat = rstat;
1333 else
1334 FREE(rstat);
1335
1336 /* Mark that there is a basis */
1337 desc->basis.basis_exists = TRUE;
1338
1339 /* Add user description */
1340 add_to_desc_u(p, desc);
1341
1342 return(desc);
1343 }
1344
1345 /*===========================================================================*/
1346
1347 int check_tailoff(lp_prob *p)
1348 {
1349 int gap_backsteps = p->par.tailoff_gap_backsteps;
1350 int obj_backsteps = p->par.tailoff_obj_backsteps;
1351 double *obj_hist = p->obj_history;
1352 double tailoff_obj_frac = p->par.tailoff_obj_frac;
1353 double tailoff_gap_frac = p->par.tailoff_gap_frac;
1354
1355 int i;
1356 double sum, ub;
1357
1358 if(p->bc_index < 1){
1359 tailoff_gap_frac *= 1.0091;
1360 tailoff_obj_frac /= 7.333;
1361 }else{
1362 tailoff_gap_frac *= 0.877;
1363 tailoff_obj_frac *= 1.133;
1364 }
1365
1366 if((p->lp_data->m - p->mip->m)/(1.0*p->mip->m) < 0.2
1367 #ifdef COMPILE_IN_LP
1368 && p->tm->stat.analyzed < 100
1369 #endif
1370 ){
1371 //tailoff_gap_frac *= 1.0091;
1372 //tailoff_obj_frac /= 7.333;
1373 gap_backsteps = 4;
1374 obj_backsteps = 5;
1375 }
1376
1377 int maxsteps = MAX(gap_backsteps, obj_backsteps);
1378
1379 //if(p->tm->stat.analyzed > 1000 && p->node_iter_num > 1) return TRUE;
1380
1381 p->has_tailoff = TRUE;
1382 if (gap_backsteps >= 1 || obj_backsteps >= 2) {
1383
1384 /* shift the data in obj_hist by one to the right and insert the
1385 most recent objval to be the 0th */
1386 for (i = MIN(p->node_iter_num-1, maxsteps) - 1; i >= 0; i--) {
1387 obj_hist[i+1] = obj_hist[i];
1388 }
1389 obj_hist[0] = p->lp_data->objval;
1390
1391 if (p->bc_index == 0) {
1392
1393 /*
1394 * root policy: generate cuts for min_root_cut_rounds and then stop.
1395 * if obj value doesnt improve in last
1396 * tailoff_max_no_impr_iters_root, then stop.
1397 */
1398
1399 //tailoff_obj_frac /= 2;
1400 double obj_gap = 0.0;
1401
1402 if(obj_hist[0] >= obj_hist[1] + p->lp_data->lpetol){
1403 obj_gap = fabs(obj_hist[1]/obj_hist[0] - 1.0);
1404 }
1405
1406 int weighted_iter = p->lp_stat.lp_total_iter_num/(p->iter_num + 1);
1407 if(p->mip->nz > 2.5e4){
1408 weighted_iter = (int) ((weighted_iter * p->mip->nz) / 2.5e4);
1409 }
1410
1411 if (obj_gap <= 1e-5 || (obj_gap <= 1e-4 && weighted_iter >= 1e4)){
1412 p->obj_no_impr_iters++;
1413 } else {
1414 if(p->obj_no_impr_iters > 0){
1415 p->obj_no_impr_iters--;
1416 }
1417 }
1418 //if(p->iter_num > 1 && p->par.verbosity > -1)
1419 //printf("w-iter - obj_gap - no_iter : %i %f %i\n", weighted_iter, obj_gap, p->obj_no_impr_iters);
1420
1421 if(weighted_iter <= 400){
1422 if (p->obj_no_impr_iters >
1423 p->par.tailoff_max_no_iterative_impr_iters_root) {
1424 for(i = 7; i >=0; --i){
1425 if(weighted_iter >= 50*i &&
1426 p->obj_no_impr_iters >= (9-i)){
1427 p->has_tailoff = TRUE;
1428 return (TRUE);
1429 }
1430 }
1431 }
1432
1433 if (p->node_iter_num >= p->par.min_root_cut_rounds) {
1434 p->has_tailoff = TRUE;
1435 return (TRUE);
1436 }else{
1437 p->has_tailoff = FALSE;
1438 return (FALSE);
1439 }
1440 }
1441
1442 if(weighted_iter >= 1e3){
1443 if (p->obj_no_impr_iters >=
1444 p->par.tailoff_max_no_iterative_impr_iters_root) {
1445 p->has_tailoff = TRUE;
1446 return (TRUE);
1447 }
1448 }
1449
1450 if (p->node_iter_num >= p->par.min_root_cut_rounds) {
1451 p->has_tailoff = TRUE;
1452 return (TRUE);
1453 }
1454 }
1455
1456 /* if there is an upper bound and we want gap based tailoff:
1457 tailoff_gap is false if the average of the consecutive gap ratios is
1458 less than gap_frac */
1459 if (p->node_iter_num>gap_backsteps && p->has_ub && gap_backsteps > 0) {
1460 ub = p->ub;
1461 for (i = 1, sum = 0; i <= gap_backsteps; i++) {
1462 sum += (ub - obj_hist[i-1]) / (ub - obj_hist[i]);
1463 }
1464 //printf("tailoff-gap: %f %f\n", sum/gap_backsteps, tailoff_gap_frac);
1465 if (sum / gap_backsteps > tailoff_gap_frac) {
1466 PRINT(p->par.verbosity, 3, ("Branching because of tailoff in gap!\n"));
1467 return(TRUE); /* there is tailoff */
1468 }
1469 }
1470
1471 /* if we want objective value based tailoff:
1472 tailoff_obj is true if the average of the objective difference
1473 ratios is smaller than par.tailoff_obj_frac */
1474 if (p->node_iter_num>obj_backsteps){
1475 for (i = 2, sum = 0; i <= obj_backsteps; i++){
1476 if (obj_hist[i-1] - obj_hist[i] > p->lp_data->lpetol){
1477 sum += (obj_hist[i-2]-obj_hist[i-1]) / (obj_hist[i-1]-obj_hist[i]);
1478 }else if (obj_hist[i-2] - obj_hist[i-1] > p->lp_data->lpetol){
1479 sum += obj_backsteps;
1480 }
1481 }
1482 //printf("tailoff-obj-gap: %f %f\n", sum/(obj_backsteps-1), tailoff_obj_frac);
1483 double init_obj = obj_hist[MIN(p->node_iter_num-1, maxsteps)];
1484 double prog = 10*p->par.tailoff_absolute;
1485 if(init_obj > p->lp_data->lpetol || init_obj < -p->lp_data->lpetol){
1486 prog = (obj_hist[0] - init_obj)/(fabs(init_obj));
1487 }
1488
1489 if (sum / (obj_backsteps - 1) < tailoff_obj_frac && prog < 5*p->par.tailoff_absolute){
1490 PRINT(p->par.verbosity, 3, ("Branching because of tailoff in "
1491 "objective function!\n"));
1492 PRINT(p->par.verbosity, 3, ("sum/n = %f, tailoff_obj_frac = %f\n",sum /
1493 (obj_backsteps - 1) , tailoff_obj_frac));
1494 return(TRUE); /* there is tailoff */
1495 }
1496 }
1497
1498 /* Another check. All other checks seem to show that there is no
1499 * tailoff yet.
1500 */
1501 if (p->bc_level > 0 && ((p->node_iter_num > 1 && fabs(obj_hist[0]) > p->lp_data->lpetol) || p->node_iter_num > maxsteps) &&
1502 (obj_hist[0] - obj_hist[1] < p->par.tailoff_absolute)){
1503 PRINT(p->par.verbosity, 3, ("Branching because of tailoff in "
1504 "value of objective function!\n"));
1505 return(TRUE);
1506 }
1507
1508 //if(p->bc_level > 0 && p->node_iter_num > maxsteps && init_obj > p->lp_data->lpetol &&
1509 // (obj_hist[0] - init_obj)/(fabs(init_obj)) < 5*p->par.tailoff_absolute){
1510 // PRINT(p->par.verbosity, 3, ("Branching because of tailoff in "
1511 // "value of objective function II!\n"));
1512 // return(TRUE);
1513 //}
1514 //printf("tailoff-absolute: %f %f\n", obj_hist[0] - obj_hist[1], p->par.tailoff_absolute);
1515 } else {
1516 /* Both gap_backsteps and obj_backsteps are too small to procede with
1517 check_tailoff. The user asks for tailoff (since we came to this
1518 function) yet doesn't want to check any kind of tailoff (since this
1519 condition is true). Report no tailoff. */
1520 p->has_tailoff=FALSE;
1521 return(FALSE); /* no tailoff */
1522 }
1523
1524 p->has_tailoff=FALSE;
1525 return(FALSE); /* gone thru everything ==> no tailoff */
1526 }
1527
1528
1529 /*===========================================================================*/
1530
1531 void lp_exit(lp_prob *p)
1532 {
1533 int s_bufid;
1534
1535 s_bufid = init_send(DataInPlace);
1536 send_msg(p->tree_manager, SOMETHING_DIED);
1537 freebuf(s_bufid);
1538 comm_exit();
1539 exit(-1);
1540 }
1541
1542 /*===========================================================================*/
1543
1544 void lp_close(lp_prob *p)
1545 {
1546 #ifndef COMPILE_IN_LP
1547 int s_bufid;
1548
1549 /* Send back the timing data for the whole algorithm */
1550 s_bufid = init_send(DataInPlace);
1551 send_char_array((char *)&(p->comp_times), sizeof(node_times));
1552 send_char_array((char *)&(p->lp_stat), sizeof(lp_stat_desc));
1553 send_msg(p->tree_manager, LP__TIMING);
1554 freebuf(s_bufid);
1555 #else
1556 #pragma omp critical (timing_update)
1557 {
1558 int i;
1559 p->tm->comp_times.communication += p->comp_times.communication;
1560 p->tm->comp_times.lp += p->comp_times.lp;
1561 p->tm->comp_times.lp_setup += p->comp_times.lp_setup;
1562 p->tm->comp_times.separation += p->comp_times.separation;
1563 p->tm->comp_times.fixing += p->comp_times.fixing;
1564 p->tm->comp_times.pricing += p->comp_times.pricing;
1565 p->tm->comp_times.strong_branching += p->comp_times.strong_branching;
1566 p->tm->comp_times.fp += p->comp_times.fp;
1567 p->tm->comp_times.rh += p->comp_times.rh;
1568 p->tm->comp_times.sh += p->comp_times.sh;
1569 p->tm->comp_times.ls += p->comp_times.ls;
1570 p->tm->comp_times.ds += p->comp_times.ds;
1571 p->tm->comp_times.fr += p->comp_times.fr;
1572 p->tm->comp_times.lb += p->comp_times.lb;
1573 p->tm->comp_times.rs += p->comp_times.rs;
1574 p->tm->comp_times.primal_heur += p->comp_times.primal_heur;
1575
1576 for(i = 0; i < DIVING_HEURS_CNT; i++){
1577 p->tm->comp_times.ds_type[i] += p->comp_times.ds_type[i];
1578 }
1579
1580 p->tm->comp_times.cuts += p->comp_times.cuts;
1581 p->tm->comp_times.gomory_cuts += p->comp_times.gomory_cuts;
1582 p->tm->comp_times.knapsack_cuts += p->comp_times.knapsack_cuts;
1583 p->tm->comp_times.oddhole_cuts += p->comp_times.oddhole_cuts;
1584 p->tm->comp_times.clique_cuts += p->comp_times.clique_cuts;
1585 p->tm->comp_times.probing_cuts += p->comp_times.probing_cuts;
1586 p->tm->comp_times.mir_cuts += p->comp_times.mir_cuts;
1587 p->tm->comp_times.twomir_cuts += p->comp_times.twomir_cuts;
1588 p->tm->comp_times.rounding_cuts += p->comp_times.rounding_cuts;
1589 p->tm->comp_times.landp_cuts += p->comp_times.landp_cuts;
1590 p->tm->comp_times.flowcover_cuts += p->comp_times.flowcover_cuts;
1591 p->tm->comp_times.lift_and_project_cuts +=
1592 p->comp_times.lift_and_project_cuts;
1593 p->tm->comp_times.redsplit_cuts += p->comp_times.redsplit_cuts;
1594 p->tm->comp_times.dupes_and_bad_coeffs_in_cuts +=
1595 p->comp_times.dupes_and_bad_coeffs_in_cuts;
1596
1597 p->tm->lp_stat.lp_calls += p->lp_stat.lp_calls;
1598 p->tm->lp_stat.lp_node_calls += p->lp_stat.lp_node_calls;
1599 p->tm->lp_stat.str_br_lp_calls += p->lp_stat.str_br_lp_calls;
1600 p->tm->lp_stat.lp_sols += p->lp_stat.lp_sols;
1601 p->tm->lp_stat.ip_sols += p->lp_stat.ip_sols;
1602 p->tm->lp_stat.str_br_bnd_changes += p->lp_stat.str_br_bnd_changes;
1603 p->tm->lp_stat.str_br_nodes_pruned += p->lp_stat.str_br_nodes_pruned;
1604 p->tm->lp_stat.prep_bnd_changes += p->lp_stat.prep_bnd_changes;
1605 p->tm->lp_stat.prep_nodes_pruned += p->lp_stat.prep_nodes_pruned;
1606 p->tm->lp_stat.lp_iter_num += p->lp_stat.lp_iter_num;
1607
1608 p->tm->lp_stat.cuts_generated += p->lp_stat.cuts_generated;
1609 p->tm->lp_stat.gomory_cuts += p->lp_stat.gomory_cuts;
1610 p->tm->lp_stat.knapsack_cuts += p->lp_stat.knapsack_cuts;
1611 p->tm->lp_stat.oddhole_cuts += p->lp_stat.oddhole_cuts;
1612 p->tm->lp_stat.clique_cuts += p->lp_stat.clique_cuts;
1613 p->tm->lp_stat.probing_cuts += p->lp_stat.probing_cuts;
1614 p->tm->lp_stat.mir_cuts += p->lp_stat.mir_cuts;
1615 p->tm->lp_stat.twomir_cuts += p->lp_stat.twomir_cuts;
1616 p->tm->lp_stat.rounding_cuts += p->lp_stat.rounding_cuts;
1617 p->tm->lp_stat.landp_cuts += p->lp_stat.landp_cuts;
1618 p->tm->lp_stat.flowcover_cuts += p->lp_stat.flowcover_cuts;
1619 p->tm->lp_stat.lift_and_project_cuts += p->lp_stat.lift_and_project_cuts;
1620 p->tm->lp_stat.redsplit_cuts += p->lp_stat.redsplit_cuts;
1621
1622 p->tm->lp_stat.cuts_root += p->lp_stat.cuts_root;
1623 p->tm->lp_stat.gomory_cuts_root += p->lp_stat.gomory_cuts_root;
1624 p->tm->lp_stat.knapsack_cuts_root += p->lp_stat.knapsack_cuts_root;
1625 p->tm->lp_stat.oddhole_cuts_root += p->lp_stat.oddhole_cuts_root;
1626 p->tm->lp_stat.clique_cuts_root += p->lp_stat.clique_cuts_root;
1627 p->tm->lp_stat.probing_cuts_root += p->lp_stat.probing_cuts_root;
1628 p->tm->lp_stat.mir_cuts_root += p->lp_stat.mir_cuts_root;
1629 p->tm->lp_stat.twomir_cuts_root += p->lp_stat.twomir_cuts_root;
1630 p->tm->lp_stat.rounding_cuts_root += p->lp_stat.rounding_cuts_root;
1631 p->tm->lp_stat.landp_cuts_root += p->lp_stat.landp_cuts_root;
1632 p->tm->lp_stat.flowcover_cuts_root += p->lp_stat.flowcover_cuts_root;
1633 p->tm->lp_stat.lift_and_project_cuts_root +=
1634 p->lp_stat.lift_and_project_cuts_root;
1635 p->tm->lp_stat.redsplit_cuts_root +=
1636 p->lp_stat.redsplit_cuts_root;
1637
1638 p->tm->lp_stat.num_poor_cuts += p->lp_stat.num_poor_cuts;
1639 p->tm->lp_stat.num_duplicate_cuts += p->lp_stat.num_duplicate_cuts;
1640 p->tm->lp_stat.num_unviolated_cuts += p->lp_stat.num_unviolated_cuts;
1641 p->tm->lp_stat.cuts_deleted_from_lps += p->lp_stat.cuts_deleted_from_lps;
1642 p->tm->lp_stat.cuts_added_to_lps += p->lp_stat.cuts_added_to_lps;
1643
1644 p->tm->lp_stat.gomory_calls += p->lp_stat.gomory_calls;
1645 p->tm->lp_stat.knapsack_calls += p->lp_stat.knapsack_calls;
1646 p->tm->lp_stat.oddhole_calls += p->lp_stat.oddhole_calls;
1647 p->tm->lp_stat.clique_calls += p->lp_stat.clique_calls;
1648 p->tm->lp_stat.probing_calls += p->lp_stat.probing_calls;
1649 p->tm->lp_stat.mir_calls += p->lp_stat.mir_calls;
1650 p->tm->lp_stat.twomir_calls += p->lp_stat.twomir_calls;
1651 p->tm->lp_stat.rounding_calls += p->lp_stat.rounding_calls;
1652 p->tm->lp_stat.landp_calls += p->lp_stat.landp_calls;
1653 p->tm->lp_stat.flowcover_calls += p->lp_stat.flowcover_calls;
1654 p->tm->lp_stat.lift_and_project_calls += p->lp_stat.lift_and_project_calls;
1655 p->tm->lp_stat.redsplit_calls += p->lp_stat.redsplit_calls;
1656
1657 p->tm->lp_stat.fp_calls += p->lp_stat.fp_calls;
1658 p->tm->lp_stat.fp_lp_calls += p->lp_stat.fp_lp_calls;
1659 p->tm->lp_stat.fp_num_sols += p->lp_stat.fp_num_sols;
1660 p->tm->lp_stat.fp_num_iter += p->lp_stat.fp_num_iter;
1661 p->tm->lp_stat.fp_last_call_ind = p->lp_stat.fp_last_call_ind;
1662
1663 p->tm->lp_stat.rh_calls += p->lp_stat.rh_calls;
1664 p->tm->lp_stat.rh_num_sols += p->lp_stat.rh_num_sols;
1665 p->tm->lp_stat.rh_last_call_ind = p->lp_stat.rh_last_call_ind;
1666
1667 p->tm->lp_stat.sh_calls += p->lp_stat.sh_calls;
1668 p->tm->lp_stat.sh_num_sols += p->lp_stat.sh_num_sols;
1669 p->tm->lp_stat.sh_last_call_ind = p->lp_stat.sh_last_call_ind;
1670
1671 p->tm->lp_stat.ls_calls += p->lp_stat.ls_calls;
1672 p->tm->lp_stat.ls_num_sols += p->lp_stat.ls_num_sols;
1673 p->tm->lp_stat.ls_last_call_ind = p->lp_stat.ls_last_call_ind;
1674
1675 p->tm->lp_stat.ds_calls += p->lp_stat.ds_calls;
1676 p->tm->lp_stat.ds_num_sols += p->lp_stat.ds_num_sols;
1677 p->tm->lp_stat.ds_num_iter += p->lp_stat.ds_num_iter;
1678 p->tm->lp_stat.ds_last_call_ind = p->lp_stat.ds_last_call_ind;
1679
1680 p->tm->lp_stat.fr_calls += p->lp_stat.fr_calls;
1681 p->tm->lp_stat.fr_num_sols += p->lp_stat.fr_num_sols;
1682 p->tm->lp_stat.fr_last_call_ind = p->lp_stat.fr_last_call_ind;
1683 p->tm->lp_stat.fr_analyzed_nodes += p->lp_stat.fr_analyzed_nodes;
1684 p->tm->lp_stat.fr_last_sol_call = p->lp_stat.fr_last_sol_call;
1685
1686 p->tm->lp_stat.rs_calls += p->lp_stat.rs_calls;
1687 p->tm->lp_stat.rs_num_sols += p->lp_stat.rs_num_sols;
1688 p->tm->lp_stat.rs_last_call_ind = p->lp_stat.rs_last_call_ind;
1689 p->tm->lp_stat.rs_analyzed_nodes += p->lp_stat.rs_analyzed_nodes;
1690 p->tm->lp_stat.rs_last_sol_call = p->lp_stat.rs_last_sol_call;
1691
1692 p->tm->lp_stat.lb_calls += p->lp_stat.lb_calls;
1693 p->tm->lp_stat.lb_num_sols += p->lp_stat.lb_num_sols;
1694 p->tm->lp_stat.lb_last_call_ind = p->lp_stat.lb_last_call_ind;
1695 p->tm->lp_stat.lb_analyzed_nodes += p->lp_stat.lb_analyzed_nodes;
1696 p->tm->lp_stat.lb_last_sol_call = p->lp_stat.lb_last_sol_call;
1697
1698 for(i = 0; i < DIVING_HEURS_CNT; i++){
1699 p->tm->lp_stat.ds_type_calls[i] += p->lp_stat.ds_type_calls[i];
1700 p->tm->lp_stat.ds_type_num_sols[i] += p->lp_stat.ds_type_num_sols[i];
1701 p->tm->lp_stat.ds_type_num_iter[i] += p->lp_stat.ds_type_num_iter[i];
1702 }
1703 }
1704 #endif
1705 #ifdef COMPILE_IN_CG
1706 cg_close(p->cgp);
1707 #endif
1708 #ifndef COMPILE_IN_TM
1709 free_lp(p);
1710 #endif
1711 }
1712
1713 /*===========================================================================*/
1714 /*
1715 * save the changes in bounds that occurred while processing the current node
1716 * into current-node's node_desc. These changes are available by comparing
1717 * vars[i]->lb and vars[i]->new_lb etc. After saving the changes, vars[i]->lb,
1718 * vars[i]->ub are changed to new_lb and new_ub so that the same changes are
1719 * not saved in the child-node's desc.
1720 */
1721 int add_bound_changes_to_desc(node_desc *desc, lp_prob *p)
1722 {
1723 #ifdef COMPILE_IN_LP
1724 LPdata *lp_data = p->lp_data;
1725 var_desc **vars = lp_data->vars;
1726 int i, num_bnd_changes, cnt;
1727 bounds_change_desc *bnd_change;
1728 int *index;
1729 char *lbub;
1730 double *value;
1731
1732 num_bnd_changes = 0;
1733 for (i=0;i<lp_data->n;i++) {
1734 if (vars[i]->new_lb>vars[i]->lb) {
1735 num_bnd_changes++;
1736 }
1737 if (vars[i]->new_ub<vars[i]->ub) {
1738 num_bnd_changes++;
1739 }
1740 }
1741 if (num_bnd_changes>0) {
1742 bnd_change = desc->bnd_change = (bounds_change_desc *)
1743 calloc (1, sizeof(bounds_change_desc));
1744 bnd_change->num_changes = num_bnd_changes;
1745 index = bnd_change->index = (int *)malloc(num_bnd_changes*ISIZE);
1746 lbub = bnd_change->lbub = (char *)malloc(num_bnd_changes*CSIZE);
1747 value = bnd_change->value = (double *)malloc(num_bnd_changes*DSIZE);
1748 cnt = 0;
1749 for (i=0;i<lp_data->n;i++) {
1750 if (vars[i]->new_lb>vars[i]->lb) {
1751 index[cnt] = vars[i]->userind;
1752 lbub[cnt] = 'L';
1753 value[cnt] = vars[i]->new_lb;
1754 cnt++;
1755 vars[i]->lb = vars[i]->new_lb;
1756 }
1757 if (vars[i]->new_ub<vars[i]->ub) {
1758 index[cnt] = vars[i]->userind;
1759 lbub[cnt] = 'U';
1760 value[cnt] = vars[i]->new_ub;
1761 cnt++;
1762 vars[i]->ub = vars[i]->new_ub;
1763 }
1764 }
1765 } else {
1766 if (desc->bnd_change) {
1767 FREE(desc->bnd_change->index);
1768 FREE(desc->bnd_change->lbub);
1769 FREE(desc->bnd_change->value);
1770 FREE(desc->bnd_change);
1771 }
1772 desc->bnd_change = NULL;
1773 }
1774 #endif
1775
1776 return 0;
1777 }
1778
1779 /*===========================================================================*/
1780 int str_br_bound_changes(lp_prob *p, int num_bnd_changes, double *bnd_val,
1781 int *bnd_ind, char *bnd_sense)
1782 {
1783 #ifdef COMPILE_IN_LP
1784 bounds_change_desc *bnd_change;
1785 int i, j;
1786 var_desc **vars = p->lp_data->vars;
1787 int *index;
1788 double *value;
1789 char *lbub;
1790
1791 if (num_bnd_changes<1) {
1792 return 0;
1793 }
1794 if (p->tm->active_nodes[p->proc_index]->desc.bnd_change == NULL) {
1795 bnd_change = (bounds_change_desc *)calloc(1, sizeof(bounds_change_desc));
1796 index = bnd_change->index = (int *)malloc(num_bnd_changes*ISIZE);
1797 lbub = bnd_change->lbub = (char *)malloc(num_bnd_changes*CSIZE);
1798 value = bnd_change->value = (double *)malloc(num_bnd_changes*DSIZE);
1799 bnd_change->num_changes = num_bnd_changes;
1800 j = 0;
1801 } else {
1802 bnd_change = p->tm->active_nodes[p->proc_index]->desc.bnd_change;
1803 j = bnd_change->num_changes;
1804 bnd_change->num_changes += num_bnd_changes;
1805 index = bnd_change->index = (int *)realloc(bnd_change->index,
1806 bnd_change->num_changes*ISIZE);
1807 lbub = bnd_change->lbub = (char *)realloc(bnd_change->lbub,
1808 bnd_change->num_changes*CSIZE);
1809 value = bnd_change->value = (double *)realloc(bnd_change->value,
1810 bnd_change->num_changes*DSIZE);
1811 }
1812 for (i = 0; i<num_bnd_changes; i++) {
1813 index[i+j] = vars[bnd_ind[i]]->userind;
1814 lbub[i+j] = (bnd_sense[i] == 'L') ? 'U' : 'L';
1815 value[i+j] = bnd_val[i];
1816 }
1817 p->tm->active_nodes[p->proc_index]->desc.bnd_change = bnd_change;
1818
1819 #endif
1820 return 0;
1821 }
1822
1823 /*===========================================================================*/
1824
1825 int update_solve_parameters(lp_prob *p)
1826 {
1827 /* check if feasibility problem */
1828
1829 LPdata *lp_data = p->lp_data;
1830 var_desc **vars = lp_data->vars;
1831 int i, n = lp_data->n;
1832 double ub, lb, obj, etol = 1e-12;
1833 //int obj_coeff_cnt = 0;
1834 double *x = lp_data->x;
1835
1836 for(i = 0; i < n; i++){
1837 ub = vars[i]->ub;
1838 lb = vars[i]->lb;
1839 get_objcoef(lp_data, i, &obj);
1840
1841 if(ub > lb + lp_data->lpetol &&
1842 (obj > etol || obj < -etol)){
1843 if(x[i] < ub - etol || x[i] > lb + etol){
1844 break;//obj_coeff_cnt++;
1845 }
1846 }
1847 }
1848
1849 //if(obj_coeff_cnt < 1){
1850 if(i >= n){
1851 //printf("obj disabled %i\n", p->bc_index);
1852 p->par.disable_obj = TRUE;
1853 }
1854 else
1855 p->par.disable_obj = FALSE;
1856
1857 p->par.no_impr_in_obj = FALSE;
1858
1859 #ifdef COMPILE_IN_LP
1860 bc_node * node = p->tm->active_nodes[p->proc_index];
1861 int backtrack = 0;
1862 etol = 100*p->lp_data->lpetol;
1863 while(node->parent){
1864 if(node->parent->start_objval > node->start_objval - etol){
1865 backtrack++;
1866 }else break;
1867 if(backtrack > 4) {
1868 p->par.no_impr_in_obj = TRUE;
1869 break;
1870 }
1871 node = node->parent;
1872 }
1873 #endif
1874
1875 return 0;
1876 }
1877 /*===========================================================================*/
1878 /* this function is called after root node has been processed. we update
1879 * frequency of cut generation for different cuts depending upon how many cuts
1880 * were generated and how much time was used
1881 */
1882 int update_cut_parameters(lp_prob *p)
1883 {
1884 #ifdef USE_CGL_CUTS
1885 /* TODO: check (a) time (b) if any cuts are actually in the LP */
1886 lp_stat_desc lp_stat = p->lp_stat;
1887 cgl_params *par = &(p->par.cgl);
1888 cgl_params *data_par = &(p->lp_data->cgl);
1889
1890 #ifdef COMPILE_IN_LP
1891
1892 if(data_par->use_chain_strategy){
1893
1894 int init_chain_trial_freq = p->par.cgl.chain_trial_freq;
1895
1896 #if 0
1897 double dual_gap = 100.0;
1898 if(p->has_ub){
1899 dual_gap = d_gap(p->ub, p->lp_data->objval, p->mip->obj_offset, p->mip->obj_sense);
1900 }
1901
1902 if(dual_gap < 0.25) data_par->chain_status = CGL_CHAIN_STOP;
1903
1904 #endif
1905
1906
1907 #if 1
1908
1909 if(data_par->chain_status == CGL_CHAIN_START){
1910 data_par->max_chain_trial_num = p->par.cgl.max_chain_trial_num -
1911 p->lp_stat.chain_cuts_trial_num;
1912 if(data_par->max_chain_trial_num < 0) {
1913 data_par->chain_status = CGL_CHAIN_STOP;
1914 }
1915 }
1916
1917 double b_prog, cut_prog = 0.0;
1918 char cuts_tried = FALSE;
1919 double start_objval, end_objval;
1920 double act_cut_ratio = (1.0*(p->lp_data->m - p->mip->m))/(p->mip->m);
1921 //printf("act-cut %f\n", act_cut_ratio);
1922 if(data_par->chain_status != CGL_CHAIN_STOP){
1923 bc_node * node = p->tm->active_nodes[p->proc_index];
1924
1925 data_par->chain_check_index = node->bc_index;
1926 b_prog = p->lp_data->objval;
1927 node = node->parent;
1928 b_prog -= node->end_objval;
1929 cuts_tried = node->cuts_tried;
1930 if(cuts_tried){
1931 cut_prog = (node->end_objval - node->start_objval);///node->iter_num;
1932 }
1933 start_objval = node->start_objval;
1934 end_objval = node->end_objval;
1935 }
1936
1937 /* TODO: Have these for each cut separately */
1938 if(data_par->chain_status == CGL_CHAIN_START ||
1939 data_par->chain_status == CGL_CHAIN_CONTINUE ||
1940 data_par->chain_status == CGL_CHAIN_CHECK){
1941 /* here, we are at the top of the chain, or keep generating
1942 due to improvement or we just passed a check_point after
1943 paused for a while*/
1944 if(cuts_tried){
1945 if((b_prog >= 4*cut_prog || fabs(cut_prog/(start_objval + 1e-4)) < data_par->chain_weighted_gap ||
1946 act_cut_ratio > 0.2)){
1947 if(data_par->max_chain_trial_num >= 0){
1948 data_par->chain_status = CGL_CHAIN_PAUSE;
1949 data_par->chain_trial_freq = init_chain_trial_freq;
1950 }else{
1951 data_par->chain_status = CGL_CHAIN_STOP;
1952 }
1953 }else{
1954 data_par->chain_status = CGL_CHAIN_CONTINUE;
1955 //data_par->max_chain_trial_num = p->par.cgl.max_chain_trial_num;
1956 }
1957 }else{
1958 if(fabs(b_prog/(end_objval + 1e-4)) < 10*par->chain_br_weighted_gap || act_cut_ratio < 0.05){
1959 //data_par->max_chain_trial_num--;
1960 data_par->chain_status = CGL_CHAIN_CHECK;
1961 }else{
1962 data_par->chain_status = CGL_CHAIN_PAUSE;
1963 data_par->chain_trial_freq = init_chain_trial_freq;
1964 }
1965 }
1966 }else if(data_par->chain_status == CGL_CHAIN_PAUSE){
1967 if(fabs(b_prog/(end_objval + 1e-4)) < 10*par->chain_br_weighted_gap){
1968 data_par->chain_trial_freq--;
1969 if(data_par->chain_trial_freq <= 0){
1970 data_par->max_chain_trial_num--;
1971 data_par->chain_trial_freq = init_chain_trial_freq;
1972 data_par->chain_status = CGL_CHAIN_CHECK;
1973 data_par->chain_check_index =
1974 p->tm->active_nodes[p->proc_index]->bc_index;
1975 }
1976 }
1977 }
1978
1979 #if 0
1980 if(data_par->chain_status == CGL_CHAIN_START){
1981 printf("%i CGL-START\n", p->bc_index);
1982 }else if(data_par->chain_status == CGL_CHAIN_CHECK){
1983 printf("\t%i CGL-CHECK\n", p->bc_index);
1984 }else if(data_par->chain_status == CGL_CHAIN_STOP){
1985 printf("\t%i CGL-STOP\n", p->bc_index);
1986 }else if(data_par->chain_status == CGL_CHAIN_PAUSE){
1987 printf("\t%i CGL-PAUSE\n", p->bc_index);
1988 }else if(data_par->chain_status == CGL_CHAIN_CONTINUE){
1989 printf("\t%i CGL-CONT\n", p->bc_index);
1990 }else {
1991 printf("\t%i CGL-ELSE\n", p->bc_index);
1992 }
1993 #endif
1994 #endif
1995
1996 if(data_par->chain_status == CGL_CHAIN_CHECK ||
1997 data_par->chain_status == CGL_CHAIN_CONTINUE){
1998 p->lp_stat.node_cuts_tried = TRUE;
1999 if(data_par->chain_status == CGL_CHAIN_CHECK){
2000 p->lp_stat.node_cuts_forced = TRUE;
2001 }
2002 }
2003 }
2004
2005 #endif
2006
2007 /* probing cuts */
2008 if (data_par->generate_cgl_probing_cuts == GENERATE_IF_IN_ROOT &&
2009 lp_stat.probing_cuts_root<1) {
2010 data_par->generate_cgl_probing_cuts_freq = -1;
2011 }
2012 if (data_par->generate_cgl_probing_cuts == GENERATE_DEFAULT) {
2013
2014 #ifdef COMPILE_IN_LP
2015 if(data_par->use_chain_strategy){
2016 if(p->bc_level > 0 && p->tm->lp_stat.probing_calls +
2017 p->lp_stat.probing_calls > 100 &&
2018 p->tm->lp_stat.probing_cuts + p->lp_stat.probing_cuts < 10){
2019 data_par->generate_cgl_probing_cuts = DO_NOT_GENERATE;
2020 }else{
2021 if((data_par->chain_status == CGL_CHAIN_CONTINUE ||
2022 data_par->chain_status == CGL_CHAIN_CHECK)){
2023 if(lp_stat.probing_cuts_root >= 1){
2024 if(p->mip->mip_inf){
2025 if(p->mip->mip_inf->cont_var_num > 0){
2026 if(p->mip->mip_inf->bin_row_ratio > 0.05){
2027 if(p->par.cgl.probing_root_max_look < 21 &&
2028 p->mip->nz > 1e5 &&
2029 p->mip->mip_inf->cont_var_ratio > 0.5){
2030 //probably isn't worth it...
2031 if(p->bc_level <= 10){
2032 data_par->generate_cgl_probing_cuts_freq = 1;
2033 }else{
2034 data_par->generate_cgl_probing_cuts_freq = -1;
2035 }
2036 }else{
2037 data_par->generate_cgl_probing_cuts_freq = 1;
2038 }
2039 }else{
2040 data_par->generate_cgl_probing_cuts_freq = -1;
2041 }
2042 }else{
2043 data_par->generate_cgl_probing_cuts_freq = 1;
2044 }
2045 }else{
2046 data_par->generate_cgl_probing_cuts_freq = 1;
2047 }
2048 }else{
2049 if(p->mip->mip_inf){
2050 if(p->mip->m - p->mip->mip_inf->cont_row_num > 0 &&
2051 p->mip->mip_inf->bin_row_ratio > 0.05){
2052 if(p->par.cgl.probing_root_max_look < 21 &&
2053 p->mip->nz > 1e5 &&
2054 p->mip->mip_inf->cont_var_ratio > 0.5){
2055 if(p->bc_level <= 10){
2056 data_par->generate_cgl_probing_cuts_freq = 1;
2057 }else{
2058 data_par->generate_cgl_probing_cuts_freq = -1;
2059 }
2060 }else{
2061 if(p->bc_level <= 20){
2062 data_par->generate_cgl_probing_cuts_freq = 1;
2063 }else{
2064 data_par->generate_cgl_probing_cuts_freq = -1;
2065 }
2066 }
2067 }else{
2068 data_par->generate_cgl_probing_cuts_freq = -1;
2069 }
2070 }else{
2071 data_par->generate_cgl_probing_cuts_freq = -1;
2072 }
2073 }
2074 }else if(data_par->chain_status == CGL_CHAIN_STOP){
2075 data_par->generate_cgl_probing_cuts = DO_NOT_GENERATE;
2076 }else{
2077 data_par->generate_cgl_probing_cuts_freq = -1;
2078 }
2079 }
2080 }else{
2081 #endif
2082 if (lp_stat.probing_cuts_root<1) {
2083 data_par->generate_cgl_probing_cuts_freq =
2084 par->generate_cgl_probing_cuts_freq = 1000;
2085 } else if(p->bc_level < 20){
2086 data_par->generate_cgl_probing_cuts_freq =
2087 par->generate_cgl_probing_cuts_freq = 50;
2088 } else{
2089 data_par->generate_cgl_probing_cuts_freq =
2090 par->generate_cgl_probing_cuts_freq = 100;
2091 }
2092 #ifdef COMPILE_IN_LP
2093 }
2094 #endif
2095 }
2096
2097 /* twomir cuts */
2098 if (data_par->generate_cgl_twomir_cuts == GENERATE_IF_IN_ROOT &&
2099 lp_stat.twomir_cuts_root<1) {
2100 data_par->generate_cgl_twomir_cuts_freq = -1;
2101 }
2102 if (data_par->generate_cgl_twomir_cuts == GENERATE_DEFAULT) {
2103 #ifdef COMPILE_IN_LP
2104 if(data_par->use_chain_strategy){
2105 if(p->bc_level > 0 && p->tm->lp_stat.twomir_calls +
2106 p->lp_stat.twomir_calls > 50 &&
2107 p->tm->lp_stat.twomir_cuts + p->lp_stat.twomir_cuts < 10){
2108 data_par->generate_cgl_twomir_cuts = DO_NOT_GENERATE;
2109 }else{
2110 if((data_par->chain_status == CGL_CHAIN_CONTINUE ||
2111 data_par->chain_status == CGL_CHAIN_CHECK) &&
2112 lp_stat.twomir_cuts_root >= 1){
2113 data_par->generate_cgl_twomir_cuts_freq = 1;
2114 }else if(data_par->chain_status == CGL_CHAIN_STOP){
2115 data_par->generate_cgl_twomir_cuts = DO_NOT_GENERATE;
2116 }else{
2117 data_par->generate_cgl_twomir_cuts_freq = -1;
2118 }
2119 }
2120 }else{
2121 #endif
2122 if (lp_stat.twomir_cuts_root<1) {
2123 data_par->generate_cgl_twomir_cuts_freq =
2124 par->generate_cgl_twomir_cuts_freq = 1000;
2125 } else if(p->bc_level < 20){
2126 data_par->generate_cgl_twomir_cuts_freq =
2127 par->generate_cgl_twomir_cuts_freq = 50;
2128 } else{
2129 data_par->generate_cgl_twomir_cuts_freq =
2130 par->generate_cgl_twomir_cuts_freq = 100;
2131 }
2132 #ifdef COMPILE_IN_LP
2133 }
2134 #endif
2135 }
2136
2137 /* cliques cuts */
2138
2139 if (data_par->generate_cgl_clique_cuts == GENERATE_IF_IN_ROOT &&
2140 lp_stat.clique_cuts_root<1) {
2141 data_par->generate_cgl_clique_cuts_freq = -1;
2142 }
2143 if (data_par->generate_cgl_clique_cuts == GENERATE_DEFAULT) {
2144 #ifdef COMPILE_IN_LP
2145 if(data_par->use_chain_strategy){
2146 if(p->bc_level > 0 && p->tm->lp_stat.clique_calls + p->lp_stat.clique_calls > 50 &&
2147 p->tm->lp_stat.clique_cuts + p->lp_stat.clique_cuts < 10){
2148 data_par->generate_cgl_clique_cuts = DO_NOT_GENERATE;
2149 }else{
2150 if((data_par->chain_status == CGL_CHAIN_CONTINUE ||
2151 data_par->chain_status == CGL_CHAIN_CHECK) &&
2152 lp_stat.clique_cuts_root >= 1) {
2153 data_par->generate_cgl_clique_cuts_freq = 1;
2154 }else if(data_par->chain_status == CGL_CHAIN_STOP){
2155 data_par->generate_cgl_clique_cuts = DO_NOT_GENERATE;
2156 }else{
2157 data_par->generate_cgl_clique_cuts_freq = -1;
2158 }
2159 }
2160 }else{
2161 #endif
2162 if (lp_stat.clique_cuts_root<1) {
2163 data_par->generate_cgl_clique_cuts_freq = 200;
2164 } else {
2165 if(p->bc_level < 10){
2166 data_par->generate_cgl_clique_cuts_freq = 5;
2167 }else {
2168 data_par->generate_cgl_clique_cuts_freq = 10;
2169 }
2170 }
2171 #ifdef COMPILE_IN_LP
2172 }
2173 #endif
2174 }
2175
2176 /* flow and cover cuts */
2177 if (data_par->generate_cgl_flowcover_cuts == GENERATE_IF_IN_ROOT &&
2178 lp_stat.flowcover_cuts_root<1) {
2179 data_par->generate_cgl_flowcover_cuts_freq = -1;
2180 }
2181
2182 if (data_par->generate_cgl_flowcover_cuts == GENERATE_DEFAULT) {
2183 #ifdef COMPILE_IN_LP
2184 if(data_par->use_chain_strategy){
2185 if(p->bc_level > 0 && p->tm->lp_stat.flowcover_calls +
2186 p->lp_stat.flowcover_calls > 50 &&
2187 p->tm->lp_stat.flowcover_cuts + p->lp_stat.flowcover_cuts < 10){
2188 data_par->generate_cgl_flowcover_cuts = DO_NOT_GENERATE;
2189 }else{
2190 if((data_par->chain_status == CGL_CHAIN_CONTINUE ||
2191 data_par->chain_status == CGL_CHAIN_CHECK)){
2192 if(lp_stat.flowcover_cuts_root >= 1) {
2193 data_par->generate_cgl_flowcover_cuts_freq = 1;
2194 }else{
2195 data_par->generate_cgl_flowcover_cuts_freq = -1;
2196 }
2197 }else if(data_par->chain_status == CGL_CHAIN_STOP){
2198 data_par->generate_cgl_flowcover_cuts = DO_NOT_GENERATE;
2199 }else{
2200 data_par->generate_cgl_flowcover_cuts_freq = -1;
2201 }
2202 }
2203 }else{
2204 #endif
2205 if (lp_stat.flowcover_cuts_root<1) {
2206 data_par->generate_cgl_flowcover_cuts_freq = -1;
2207 } else {
2208 if(p->bc_level < 10){
2209 data_par->generate_cgl_flowcover_cuts_freq = 50;
2210 }else {
2211 data_par->generate_cgl_flowcover_cuts_freq = 100;
2212 }
2213 }
2214 #ifdef COMPILE_IN_LP
2215 }
2216 #endif
2217 }
2218
2219 /* knapsack */
2220
2221 if (data_par->generate_cgl_knapsack_cuts == GENERATE_IF_IN_ROOT &&
2222 lp_stat.knapsack_cuts_root<1) {
2223 data_par->generate_cgl_knapsack_cuts_freq = -1;
2224 }
2225
2226 if (data_par->generate_cgl_knapsack_cuts == GENERATE_DEFAULT) {
2227 #ifdef COMPILE_IN_LP
2228 if(data_par->use_chain_strategy){
2229 if(p->bc_level > 0 && p->tm->lp_stat.knapsack_calls + p->lp_stat.knapsack_calls > 50 &&
2230 p->tm->lp_stat.knapsack_cuts + p->lp_stat.knapsack_cuts < 10){
2231 data_par->generate_cgl_knapsack_cuts = DO_NOT_GENERATE;
2232 }else{
2233 if((data_par->chain_status == CGL_CHAIN_CONTINUE ||
2234 data_par->chain_status == CGL_CHAIN_CHECK)){
2235 if(lp_stat.knapsack_cuts_root >= 1 ) {
2236 data_par->generate_cgl_knapsack_cuts_freq = 1;
2237 }else{
2238 data_par->generate_cgl_knapsack_cuts_freq = -1;
2239 }
2240 }else if(data_par->chain_status == CGL_CHAIN_STOP){
2241 data_par->generate_cgl_knapsack_cuts = DO_NOT_GENERATE;
2242 }else{
2243 data_par->generate_cgl_knapsack_cuts_freq = -1;
2244 }
2245 }
2246 }else{
2247 #endif
2248 if (lp_stat.knapsack_cuts_root<1) {
2249 data_par->generate_cgl_knapsack_cuts_freq = 200;
2250 } else {
2251 if(p->bc_level < 10){
2252 data_par->generate_cgl_knapsack_cuts_freq = 10;
2253 }else {
2254 data_par->generate_cgl_knapsack_cuts_freq = 20;
2255 }
2256 }
2257 #ifdef COMPILE_IN_LP
2258 }
2259 #endif
2260 }
2261
2262 /* gomory cuts */
2263
2264 if (data_par->generate_cgl_gomory_cuts == GENERATE_IF_IN_ROOT &&
2265 lp_stat.gomory_cuts_root<1) {
2266 data_par->generate_cgl_gomory_cuts_freq = -1;
2267 }
2268
2269 if (data_par->generate_cgl_gomory_cuts == GENERATE_DEFAULT) {
2270 #ifdef COMPILE_IN_LP
2271 if(data_par->use_chain_strategy){
2272
2273 //printf("gomory_nz: %.2f\n", p->gomory_nz);
2274 if (p->lp_stat.gomory_nz > 5e6){
2275 data_par->generate_cgl_gomory_cuts = DO_NOT_GENERATE;
2276 }
2277 if(p->bc_level > 0 && p->tm->lp_stat.gomory_calls + p->lp_stat.gomory_calls > 200 &&
2278 p->tm->lp_stat.gomory_cuts + p->lp_stat.gomory_cuts < 10){
2279 data_par->generate_cgl_gomory_cuts = DO_NOT_GENERATE;
2280 }else{
2281 if((data_par->chain_status == CGL_CHAIN_CONTINUE ||
2282 data_par->chain_status == CGL_CHAIN_CHECK)){
2283 data_par->generate_cgl_gomory_cuts_freq = 1;
2284 }else if(data_par->chain_status == CGL_CHAIN_STOP){
2285 data_par->generate_cgl_gomory_cuts = DO_NOT_GENERATE;
2286 }else{
2287 data_par->generate_cgl_gomory_cuts_freq = -1;
2288 }
2289 }
2290 }else{
2291 #endif
2292 if (lp_stat.gomory_cuts_root<1) {
2293 data_par->generate_cgl_gomory_cuts_freq = 100;
2294 } else {
2295 if(p->bc_level < 10){
2296 data_par->generate_cgl_gomory_cuts_freq = 5;
2297 }else {
2298 data_par->generate_cgl_gomory_cuts_freq = 10;
2299 }
2300 }
2301 #ifdef COMPILE_IN_LP
2302 }
2303 #endif
2304 }
2305
2306 #endif
2307 return 0;
2308 }
2309
2310 /*===========================================================================*/
2311 int generate_cgl_cuts_new(lp_prob *p, int *num_cuts, cut_data ***cuts,
2312 int send_to_pool, int *bound_changes)
2313 {
2314
2315 #ifdef USE_CGL_CUTS
2316 int i, should_stop = FALSE, repeat_with_long = TRUE, max_cut_length;
2317 OsiCuts cutlist;
2318 const int n = p->lp_data->n;
2319 OsiXSolverInterface *si = p->lp_data->si;
2320 var_desc **vars = p->lp_data->vars;
2321 int was_tried = FALSE;
2322
2323 if (p->iter_num < 2) {
2324 for (i = 0; i < n; i++) {
2325 if (vars[i]->is_int) { // integer or binary
2326 si->setInteger(i);
2327 }
2328 }
2329 }
2330
2331 #ifdef COMPILE_IN_LP
2332 if(p->bc_level < 1 && p->iter_num < 2){
2333 int row_den = (int)(1.0*p->mip->nz/p->mip->m) + 1;
2334 /* all previous */
2335 if(p->mip->mip_inf){
2336 //printf("max_col_size: %i\t", p->mip->mip_inf->max_col_size);
2337 //printf("row den: %i\t, max_row_size: %i\t", row_den,
2338 //p->mip->mip_inf->max_row_size);
2339
2340 //printf("sos_ratio %f \t", bin_sos_ratio);
2341 //printf("cont_bin_ratio %f\n", cont_ratio);
2342
2343 if(p->mip->mip_inf->sos_bin_row_ratio > 0.6 &&
2344 p->mip->mip_inf->sos_bin_row_ratio < 0.9){
2345 p->par.max_cut_length *= 2;
2346 }
2347
2348 if(p->mip->mip_inf->max_row_ratio < 0.01 &&
2349 p->mip->mip_inf->prob_type != BIN_CONT_TYPE){
2350 p->par.cgl.chain_trial_freq = (int)1.5*p->par.cgl.chain_trial_freq;
2351 }
2352 if(p->mip->mip_inf->cont_var_ratio > 0.1 &&
2353 p->mip->mip_inf->max_row_ratio > 0.1)
2354 p->par.max_cut_length = p->par.max_cut_length/3 + 1;
2355
2356 if(p->mip->mip_inf->max_row_size <= 500){
2357 int max_const_size = p->mip->mip_inf->max_row_size;
2358 if(p->mip->mip_inf->prob_type == BINARY_TYPE ||
2359 p->mip->mip_inf->prob_type == BIN_CONT_TYPE){
2360 if(p->mip->mip_inf->max_row_ratio < 0.05){
2361 max_const_size = 4*max_const_size;
2362 }else {
2363 max_const_size = 5*max_const_size;
2364 }
2365 }else{
2366 if(p->mip->mip_inf->max_row_ratio < 0.01){
2367 max_const_size += row_den;
2368 }else {
2369 max_const_size = (int)(max_const_size * 3.5);
2370 }
2371 }
2372
2373 p->par.max_cut_length =
2374 MIN(MAX(p->mip->mip_inf->max_row_size,
2375 MIN(((int)(1.0133 * p->mip->mip_inf->mat_density *
2376 (p->mip->m + 1)* p->mip->n) -
2377 p->mip->nz + row_den) + 6,
2378 max_const_size)),
2379 p->par.max_cut_length);
2380 }else{
2381 if(1.0*p->mip->mip_inf->max_row_size/p->mip->n > 0.5){
2382 p->par.max_cut_length =
2383 MIN(p->mip->mip_inf->max_row_size,
2384 (int)(1.0*p->par.max_cut_length *
2385 p->mip->mip_inf->max_row_size/500.0) + row_den);
2386
2387 }else{
2388 p->par.max_cut_length = MAX(2*p->mip->mip_inf->max_row_size,
2389 (int)(1.0*p->par.max_cut_length *
2390 p->mip->mip_inf->max_row_size/
2391 500.0) + row_den);
2392 }
2393 }
2394 }else{
2395 p->par.max_cut_length =
2396 MIN(p->par.max_cut_length,
2397 (int)(5.0*row_den*p->mip->n/(row_den + p->mip->n)) + 5);
2398
2399 }
2400 // printf("sos/m %f\n", (1.0*p->mip->mip_inf->binary_sos_row_num)/p->mip->m);
2401 // printf("max_cut_length %i\n", p->par.max_cut_length);
2402 }
2403 #endif
2404 if(p->bc_level < 1 && p->iter_num < 2){
2405
2406 for (i=0; i<CGL_NUM_GENERATORS; i++) {
2407 p->par.best_violation[i] = 0.0;
2408 p->par.best_violation_length[i] = p->par.max_cut_length;
2409 }
2410 //p->par.best_violation_length = p->par.max_cut_length;
2411 #ifdef COMPILE_IN_LP
2412 if(p->par.verbosity > 1){
2413 printf("c-length - max_row - max-col - dens: %i - %i - %i - %f\n", p->par.max_cut_length,
2414 p->mip->mip_inf->max_row_size, p->mip->mip_inf->max_col_size,
2415 p->mip->mip_inf->mat_density);
2416 }
2417 #endif
2418 }
2419
2420 max_cut_length = p->par.max_cut_length;
2421 p->par.tried_long_cuts = TRUE;
2422 if (p->par.tried_long_cuts == TRUE) {
2423 repeat_with_long = FALSE;
2424 }
2425
2426 i = 0;
2427
2428 for (; i<CGL_NUM_GENERATORS; i++) {
2429 //printf("c_l: %i %i \n", i, p->par.max_cut_length);
2430 if(i > -1) generate_cgl_cut_of_type(p, i, &cutlist, &was_tried);
2431 //if(cutlist.sizeRowCuts() > 0){
2432 check_and_add_cgl_cuts(p, i, cuts, num_cuts, bound_changes, &cutlist,
2433 send_to_pool);
2434
2435 should_stop_adding_cgl_cuts(p, i, &should_stop);
2436 if(i < 0 && *num_cuts > 0) should_stop = TRUE;
2437 //}
2438 if (should_stop == TRUE) {
2439 break;
2440 }
2441 if (i==CGL_NUM_GENERATORS-1 && p->bc_index < 1 && *num_cuts < 1 &&
2442 repeat_with_long == TRUE) {
2443 p->par.max_cut_length = 1000;
2444 i = -1;
2445 repeat_with_long = FALSE;
2446 p->par.tried_long_cuts = TRUE;
2447 }
2448 }
2449
2450 p->par.max_cut_length = max_cut_length;
2451
2452 add_col_cuts(p, &cutlist, bound_changes);
2453 if (was_tried == TRUE && p->bc_index > 0) {
2454 p->lp_stat.num_cut_iters_in_path++;
2455 }
2456
2457 #endif
2458 return 0;
2459 }
2460
2461 /*===========================================================================*/
2462 int should_use_cgl_generator(lp_prob *p, int *should_generate,
2463 int which_generator, void *generator)
2464 {
2465
2466 #ifdef USE_CGL_CUTS
2467 int bc_index = p->bc_index;
2468 int bc_level = p->bc_level;
2469 int max_cut_length = p->par.max_cut_length;
2470 cgl_params *data_par = &(p->lp_data->cgl);
2471
2472 *should_generate = FALSE;
2473
2474 switch (which_generator) {
2475 case CGL_PROBING_GENERATOR:
2476 {
2477 CglProbing *probing = (CglProbing *)generator;
2478 int param = p->lp_data->cgl.generate_cgl_probing_cuts;
2479 int freq = p->lp_data->cgl.generate_cgl_probing_cuts_freq;
2480 int max_bc_level = p->par.cgl.probing_max_depth;
2481 if (param < 0) {
2482 *should_generate = FALSE;
2483 break;
2484 } else if (param == GENERATE_DEFAULT &&
2485 (bc_level > max_bc_level ||
2486 freq < 1 || bc_index % freq != 0 ||
2487 data_par->chain_status == CGL_CHAIN_PAUSE)){
2488 *should_generate = FALSE;
2489 break;
2490 } else if (param == GENERATE_ONLY_IN_ROOT && bc_index > 0) {
2491 *should_generate = FALSE;
2492 break;
2493 } else if (param == GENERATE_IF_IN_ROOT && (freq < 1 ||
2494 bc_index % freq != 0)) {
2495 *should_generate = FALSE;
2496 break;
2497 } else if (param == GENERATE_PERIODICALLY && (freq < 1 ||
2498 bc_index % freq != 0)) {
2499 *should_generate = FALSE;
2500 break;
2501 }
2502
2503
2504 #ifdef COMPILE_IN_LP
2505 if(data_par->use_chain_strategy){
2506 probing->setRowCuts(3);
2507 probing->setMode(2);
2508 probing->setUsingObjective(1);
2509
2510 probing->setMaxPassRoot(1);
2511 if(p->bc_level < 1){
2512 if(p->iter_num < 2){
2513 probing->setMaxElementsRoot(10000);
2514 if(p->mip->nz > 2e5){
2515 probing->setMaxProbeRoot(25);
2516 }else if(p->mip->nz > 1e5){
2517 probing->setMaxProbeRoot(50);
2518 }else if(p->mip->nz > 0.75e5){
2519 probing->setMaxProbeRoot(75);
2520 }else if(p->mip->nz > 0.5e5){
2521 probing->setMaxProbeRoot(100);
2522 }else{
2523 probing->setMaxProbeRoot(200);
2524 }
2525
2526 if(p->mip->mip_inf){
2527 p->par.cgl.probing_root_max_look =
2528 (int)((1e5/p->mip->nz) *
2529 (5e4/p->mip->mip_inf->max_row_size)) + 1;
2530 if(p->mip->mip_inf->binary_sos_row_num > 0) {
2531 if(p->mip->mip_inf->sos_bin_row_ratio > 0.05){
2532 p->par.cgl.probing_root_max_look =
2533 (int)(p->par.cgl.probing_root_max_look/
2534 (200.0*p->mip->mip_inf->sos_bin_row_ratio)) + 1;
2535 }
2536 }
2537
2538 p->par.cgl.probing_root_max_look =
2539 MIN(200,MAX(p->par.cgl.probing_root_max_look, 20));
2540
2541 }else{
2542 p->par.cgl.probing_root_max_look =
2543 MIN(200,MAX((int)(1e5/p->mip->nz * 5e4/p->mip->n) + 1,
2544 10));
2545 }
2546 }else{
2547 if(p->par.cgl.probing_is_expensive){
2548 p->par.cgl.probing_root_max_look =
2549 MIN(50,MAX((int)p->par.cgl.probing_root_max_look/2 + 10,
2550 5));
2551 }
2552 }
2553 probing->setMaxLookRoot(p->par.cgl.probing_root_max_look);
2554 //printf("max_look: %i\n", p->par.cgl.probing_root_max_look);
2555 // printf("bin_row_num %i\n", p->mip->mip_inf->binary_row_num);
2556 }else{
2557 if(p->mip->nz > 1e5){
2558 probing->setMaxProbeRoot(50);
2559 }else if(p->mip->nz > 0.75e5){
2560 probing->setMaxProbeRoot(75);
2561 }else{
2562 probing->setMaxProbeRoot(100);
2563 }
2564
2565 probing->setMaxElementsRoot(1000);
2566 probing->setMaxLookRoot
2567 (MAX(11, (int)(p->par.cgl.probing_root_max_look)/2 + 10));
2568
2569 if(p->par.cgl.probing_is_expensive){
2570 probing->setMaxLookRoot
2571 (MAX(5,(int)(p->par.cgl.probing_root_max_look)/5 + 1));
2572 }
2573 }
2574 }else{
2575 #endif
2576 if(p->bc_index < 1){
2577 if((p->lp_stat.lp_max_iter_num < 1000 &&
2578 p->comp_times.probing_cuts > 10*p->comp_times.lp) ||
2579 (p->lp_stat.lp_max_iter_num >= 1000 &&
2580 p->comp_times.probing_cuts > 2*p->comp_times.lp)){
2581 p->par.cgl.probing_is_expensive = TRUE;
2582 }else{
2583 p->par.cgl.probing_is_expensive = FALSE;
2584 }
2585 }else{
2586 if (p->comp_times.probing_cuts > 2*p->comp_times.lp){
2587 p->par.cgl.probing_is_expensive = TRUE;
2588 }else{
2589 p->par.cgl.probing_is_expensive = FALSE;
2590 }
2591 }
2592
2593 probing->setRowCuts(3);
2594 probing->setMode(2);
2595 probing->setUsingObjective(1);
2596
2597 if (p->bc_index < 1 &&
2598 !p->lp_data->cgl.probing_is_expensive) {
2599 probing->setMaxPass(10); /* default is 3 */
2600 probing->setMaxPassRoot(10); /* default is 3 */
2601 probing->setMaxElements(10000); /* default is 1000 */
2602 probing->setMaxElementsRoot(10000); /* default is 10000 */
2603 probing->setMaxLook(100); /* default is 50 */
2604 probing->setMaxLookRoot(100); /* default is 50 */
2605 probing->setMaxProbe(200); /* default is 100 */
2606 probing->setMaxProbeRoot(200); /* default is 100 */
2607 if(p->bc_level > 0){
2608 probing->setMaxElementsRoot(1000); /* default is 1000 */
2609 probing->setMaxLookRoot(50); /* default is 50 */
2610 }
2611 }
2612 #ifdef COMPILE_IN_LP
2613 }
2614 #endif
2615 *should_generate = TRUE;
2616 p->lp_stat.probing_calls++;
2617 break;
2618 }
2619 case CGL_CLIQUE_GENERATOR:
2620 {
2621 CglClique *clique = (CglClique *)generator;
2622 int param = p->lp_data->cgl.generate_cgl_clique_cuts;
2623 int freq = p->lp_data->cgl.generate_cgl_clique_cuts_freq;
2624 int max_bc_level = p->par.cgl.clique_max_depth;
2625 if (param < 0) {
2626 *should_generate = FALSE;
2627 break;
2628 } else if (param == GENERATE_DEFAULT &&
2629 (bc_level > max_bc_level ||
2630 freq < 0 || bc_index % freq != 0 ||
2631 data_par->chain_status == CGL_CHAIN_PAUSE)){
2632 *should_generate = FALSE;
2633 break;
2634 } else if (param == GENERATE_ONLY_IN_ROOT && bc_index > 0) {
2635 *should_generate = FALSE;
2636 break;
2637 } else if (param == GENERATE_IF_IN_ROOT && (freq < 0 ||
2638 bc_index % freq != 0)) {
2639 *should_generate = FALSE;
2640 break;
2641 } else if (param == GENERATE_PERIODICALLY && (freq < 0 ||
2642 bc_index % freq != 0)) {
2643 *should_generate = FALSE;
2644 break;
2645 }
2646 *should_generate = TRUE;
2647 clique->setStarCliqueReport(FALSE);
2648 clique->setRowCliqueReport(FALSE);
2649 //clique->setDoStarClique(FALSE);
2650 //clique->setStarCliqueCandidateLengthThreshold(6);
2651 //clique->setRowCliqueCandidateLengthThreshold(6);
2652 p->lp_stat.clique_calls++;
2653 break;
2654 }
2655 case CGL_KNAPSACK_GENERATOR:
2656 {
2657 CglKnapsackCover *knapsack = (CglKnapsackCover *)generator;
2658 int param = p->lp_data->cgl.generate_cgl_knapsack_cuts;
2659 int freq = p->lp_data->cgl.generate_cgl_knapsack_cuts_freq;
2660 int max_bc_level = p->par.cgl.knapsack_max_depth;
2661 if (param < 0) {
2662 *should_generate = FALSE;
2663 break;
2664 } else if (param == GENERATE_DEFAULT &&
2665 (bc_level > max_bc_level ||
2666 freq < 1 || bc_index % freq != 0 ||
2667 data_par->chain_status == CGL_CHAIN_PAUSE)) {
2668 *should_generate = FALSE;
2669 break;
2670 } else if (param == GENERATE_ONLY_IN_ROOT && bc_index > 0) {
2671 *should_generate = FALSE;
2672 break;
2673 } else if (param == GENERATE_IF_IN_ROOT && (freq < 1 ||
2674 bc_index % freq != 0)) {
2675 *should_generate = FALSE;
2676 break;
2677 } else if (param == GENERATE_PERIODICALLY && (freq < 1 ||
2678 bc_index % freq != 0)) {
2679 *should_generate = FALSE;
2680 break;
2681 }
2682 *should_generate = TRUE;
2683 knapsack->setMaxInKnapsack(max_cut_length); // default is 50
2684 knapsack->switchOffExpensive(); // gets into infinite loop if on
2685 p->lp_stat.knapsack_calls++;
2686 break;
2687 }
2688 case CGL_GOMORY_GENERATOR:
2689 {
2690 CglGomory *gomory = (CglGomory *)generator;
2691 int param = p->lp_data->cgl.generate_cgl_gomory_cuts;
2692 int freq = p->lp_data->cgl.generate_cgl_gomory_cuts_freq;
2693 int max_bc_level = p->par.cgl.gomory_max_depth;
2694 if (param < 0) {
2695 *should_generate = FALSE;
2696 break;
2697 } else if (param == GENERATE_DEFAULT &&
2698 (bc_level > max_bc_level ||
2699 freq < 1 || bc_index % freq != 0 ||
2700 data_par->chain_status == CGL_CHAIN_PAUSE)){
2701 *should_generate = FALSE;
2702 break;
2703 } else if (param == GENERATE_ONLY_IN_ROOT && bc_index > 0) {
2704 *should_generate = FALSE;
2705 break;
2706 } else if (param == GENERATE_IF_IN_ROOT && (freq < 1 ||
2707 bc_index % freq != 0)) {
2708 *should_generate = FALSE;
2709 break;
2710 } else if (param == GENERATE_PERIODICALLY && (freq < 1 ||
2711 bc_index % freq != 0)) {
2712 *should_generate = FALSE;
2713 break;
2714 }
2715 gomory->setLimit(max_cut_length);
2716 //if(p->bc_index < 1) {
2717 // gomory->setAway(100*p->lp_data->lpetol);
2718 //}
2719 //gomory->setAwayAtRoot(100*p->lp_data->lpetol);
2720 *should_generate = TRUE;
2721 p->lp_stat.gomory_calls++;
2722 break;
2723 }
2724 case CGL_TWOMIR_GENERATOR:
2725 {
2726 CglTwomir *twomir = (CglTwomir *)generator;
2727 int param = p->lp_data->cgl.generate_cgl_twomir_cuts;
2728 int freq = p->lp_data->cgl.generate_cgl_twomir_cuts_freq;
2729 int max_bc_level = p->par.cgl.twomir_max_depth;
2730 if (param < 0) {
2731 *should_generate = FALSE;
2732 break;
2733 } else if (param == GENERATE_DEFAULT &&
2734 (bc_level > max_bc_level ||
2735 freq < 1 || bc_index % freq != 0 ||
2736 data_par->chain_status == CGL_CHAIN_PAUSE)){
2737 *should_generate = FALSE;
2738 break;
2739 } else if (param == GENERATE_ONLY_IN_ROOT && bc_index > 0) {
2740 *should_generate = FALSE;
2741 break;
2742 } else if (param == GENERATE_IF_IN_ROOT && (freq < 1 ||
2743 bc_index % freq != 0)) {
2744 *should_generate = FALSE;
2745 break;
2746 } else if (param == GENERATE_PERIODICALLY && (freq < 1 ||
2747 bc_index % freq != 0)) {
2748 *should_generate = FALSE;
2749 break;
2750 }
2751 *should_generate = TRUE;
2752 twomir->setMaxElements(max_cut_length);
2753 twomir->setCutTypes (TRUE, TRUE, TRUE, TRUE);
2754 p->lp_stat.twomir_calls++;
2755 break;
2756 }
2757 case CGL_FLOWCOVER_GENERATOR:
2758 {
2759 CglFlowCover *flowcover = (CglFlowCover *)generator;
2760 int param = p->lp_data->cgl.generate_cgl_flowcover_cuts;
2761 int freq = p->lp_data->cgl.generate_cgl_flowcover_cuts_freq;
2762 int max_bc_level = p->par.cgl.flowcover_max_depth;
2763 if (param < 0) {
2764 *should_generate = FALSE;
2765 break;
2766 } else if (param == GENERATE_DEFAULT &&
2767 (bc_level > max_bc_level ||
2768 freq < 1 || bc_index % freq != 0 ||
2769 data_par->chain_status == CGL_CHAIN_PAUSE)) {
2770 *should_generate = FALSE;
2771 break;
2772 } else if (param == GENERATE_ONLY_IN_ROOT && bc_index > 0) {
2773 *should_generate = FALSE;
2774 break;
2775 } else if (param == GENERATE_IF_IN_ROOT && (freq < 1 ||
2776 bc_index % freq != 0)) {
2777 *should_generate = FALSE;
2778 break;
2779 } else if (param == GENERATE_PERIODICALLY && (freq < 1 ||
2780 bc_index % freq != 0)) {
2781 *should_generate = FALSE;
2782 break;
2783 }
2784 *should_generate = TRUE;
2785 flowcover->setNumFlowCuts(0); //needs to be called because static
2786 p->lp_stat.flowcover_calls++;
2787 break;
2788 }
2789 case CGL_ODDHOLE_GENERATOR:
2790 {
2791 CglOddHole *oddhole = (CglOddHole *)generator;
2792 int param = p->lp_data->cgl.generate_cgl_oddhole_cuts;
2793 int freq = p->lp_data->cgl.generate_cgl_oddhole_cuts_freq;
2794 int max_bc_level = p->par.cgl.oddhole_max_depth;
2795 if (param < 0) {
2796 *should_generate = FALSE;
2797 break;
2798 } else if (param == GENERATE_DEFAULT &&
2799 (bc_level > max_bc_level ||
2800 freq < 1 || bc_index % freq != 0 ||
2801 data_par->chain_status == CGL_CHAIN_PAUSE)){
2802 *should_generate = FALSE;
2803 break;
2804 } else if (param == GENERATE_ONLY_IN_ROOT && bc_index > 0) {
2805 *should_generate = FALSE;
2806 break;
2807 } else if (param == GENERATE_IF_IN_ROOT && (freq < 1 ||
2808 bc_index % freq != 0)) {
2809 *should_generate = FALSE;
2810 break;
2811 } else if (param == GENERATE_PERIODICALLY && (freq < 1 ||
2812 bc_index % freq != 0)) {
2813 *should_generate = FALSE;
2814 break;
2815 }
2816 *should_generate = TRUE;
2817 oddhole->setMinimumViolation(0.005);
2818 oddhole->setMinimumViolationPer(0.00002);
2819 oddhole->setMaximumEntries(max_cut_length);
2820 p->lp_stat.oddhole_calls++;
2821 break;
2822 }
2823 }
2824 #endif
2825 return 0;
2826 }
2827
2828 /*===========================================================================*/
2829 #ifdef USE_CGL_CUTS
2830 int generate_cgl_cut_of_type(lp_prob *p, int i, OsiCuts *cutlist_p,
2831 int *was_tried)
2832 {
2833 OsiCuts cutlist = *cutlist_p;
2834 int should_generate = FALSE;
2835 double total_time, cut_time;
2836
2837 /* two times is necessary */
2838 cut_time = used_time(&total_time);
2839 cut_time = used_time(&total_time);
2840
2841 switch (i) {
2842 case CGL_PROBING_GENERATOR:
2843 {
2844 double mark_time = 0;
2845 CglProbing *probing = new CglProbing;
2846 should_use_cgl_generator(p, &should_generate, i, (void *)probing);
2847 if (should_generate == TRUE) {
2848 probing->generateCuts(*(p->lp_data->si), cutlist);
2849 *was_tried = TRUE;
2850 }
2851 delete probing;
2852 cut_time = used_time(&total_time);
2853 p->comp_times.probing_cuts += cut_time - mark_time;
2854 break;
2855 }
2856 case CGL_CLIQUE_GENERATOR:
2857 {
2858 CglClique *clique = new CglClique;
2859 should_use_cgl_generator(p, &should_generate, i, (void *)clique);
2860 if (should_generate == TRUE) {
2861 clique->generateCuts(*(p->lp_data->si), cutlist);
2862 *was_tried = TRUE;
2863 }
2864 delete clique;
2865 cut_time = used_time(&total_time);
2866 p->comp_times.clique_cuts += cut_time;
2867 break;
2868 }
2869 case CGL_KNAPSACK_GENERATOR:
2870 {
2871 CglKnapsackCover *knapsack = new CglKnapsackCover;
2872 should_use_cgl_generator(p, &should_generate, i, (void *)knapsack);
2873 if (should_generate == TRUE) {
2874 knapsack->generateCuts(*(p->lp_data->si), cutlist);
2875 *was_tried = TRUE;
2876 }
2877 delete knapsack;
2878 cut_time = used_time(&total_time);
2879 p->comp_times.knapsack_cuts += cut_time;
2880 break;
2881 }
2882 case CGL_GOMORY_GENERATOR:
2883 {
2884 CglGomory *gomory = new CglGomory;
2885 should_use_cgl_generator(p, &should_generate, i, (void *)gomory);
2886 if (should_generate == TRUE) {
2887 gomory->generateCuts(*(p->lp_data->si), cutlist);
2888 *was_tried = TRUE;
2889 }
2890 delete gomory;
2891 cut_time = used_time(&total_time);
2892 p->comp_times.gomory_cuts += cut_time;
2893 break;
2894 }
2895 case CGL_TWOMIR_GENERATOR:
2896 {
2897 CglTwomir *twomir = new CglTwomir;
2898 should_use_cgl_generator(p, &should_generate, i, (void *)twomir);
2899 if (should_generate == TRUE) {
2900 twomir->generateCuts(*(p->lp_data->si), cutlist);
2901 *was_tried = TRUE;
2902 }
2903 delete twomir;
2904 cut_time = used_time(&total_time);
2905 p->comp_times.twomir_cuts += cut_time;
2906 break;
2907 }
2908 case CGL_FLOWCOVER_GENERATOR:
2909 {
2910 CglFlowCover *flowcover = new CglFlowCover;
2911 should_use_cgl_generator(p, &should_generate, i, (void *)flowcover);
2912 if (should_generate == TRUE) {
2913 flowcover->generateCuts(*(p->lp_data->si), cutlist);
2914 *was_tried = TRUE;
2915 }
2916 delete flowcover;
2917 cut_time = used_time(&total_time);
2918 p->comp_times.flowcover_cuts += cut_time;
2919 break;
2920 }
2921 case CGL_ODDHOLE_GENERATOR:
2922 {
2923 CglOddHole *oddhole = new CglOddHole;
2924 should_use_cgl_generator(p, &should_generate, i, (void *)oddhole);
2925 if (should_generate == TRUE) {
2926 oddhole->generateCuts(*(p->lp_data->si), cutlist);
2927 *was_tried = TRUE;
2928 }
2929 delete oddhole;
2930 cut_time = used_time(&total_time);
2931 p->comp_times.oddhole_cuts += cut_time;
2932 break;
2933 }
2934 }
2935 *cutlist_p = cutlist;
2936 p->comp_times.cuts += cut_time;
2937 return 0;
2938 }
2939 #endif
2940
2941 /*===========================================================================*/
2942 #ifdef USE_CGL_CUTS
2943 int check_and_add_cgl_cuts(lp_prob *p, int generator, cut_data ***cuts,
2944 int *num_cuts, int *bound_changes, OsiCuts *cutlist, int send_to_pool)
2945 {
2946 int i, k, num_row_cuts, *accepted_ind = NULL, num_elements,
2947 *indices, discard_cut, num_poor_quality = 0, num_unviolated = 0,
2948 num_duplicate = 0, *matind;
2949 int max_elements = p->par.max_cut_length,
2950 verbosity = p->par.verbosity;
2951 LPdata *lp_data = p->lp_data;
2952 int *tmp_matind = lp_data->tmp.i1;
2953 double *hashes = NULL, *elements, rhs, max_coeff, min_coeff, hash_value,
2954 violation, *matval, total_time, cut_time;
2955 double *random_hash = lp_data->random_hash;
2956 const double lpetol = lp_data->lpetol;
2957 const double etol10 = lpetol * 10;
2958 //const double etol50 = lpetol * 50;
2959 //const double etol500 = lpetol * 500;
2960 const double etol100 = lpetol * 100;
2961 const double etol1000 = lpetol * 1000;
2962 const double *x = lp_data->x;
2963 OsiRowCut row_cut;
2964 var_desc **vars = lp_data->vars;
2965 const int is_userind_in_order = p->par.is_userind_in_order;
2966 cut_data *sym_cut;
2967 int update_cut_length = FALSE;
2968
2969 /* two times is necessary */
2970 cut_time = used_time(&total_time);
2971 cut_time = used_time(&total_time);
2972
2973 num_row_cuts = cutlist->sizeRowCuts();
2974
2975 //if(num_row_cuts > 0){
2976 // hashes = (double *) malloc(num_row_cuts*DSIZE);
2977 //is_deleted = (int *) calloc(num_row_cuts, ISIZE);
2978 // accepted_ind = (int *) malloc(num_row_cuts* ISIZE);
2979 // cut_size = (int *) calloc(num_row_cuts, ISIZE);
2980 //}
2981
2982 if(lp_data->hashes_num < num_row_cuts + *num_cuts){
2983 lp_data->hashes_num = 5000 + (num_row_cuts + *num_cuts);
2984 lp_data->hashes = (double *)malloc(DSIZE*lp_data->hashes_num);
2985 }
2986
2987 if(lp_data->accepted_num < num_row_cuts){
2988 lp_data->accepted_num = 5000 + num_row_cuts;
2989 lp_data->accepted_ind = (int *)malloc(ISIZE*lp_data->accepted_num);
2990 }
2991
2992 hashes = lp_data->hashes;
2993 accepted_ind = lp_data->accepted_ind;
2994
2995 int accepted_cnt = 0;
2996 //j = 0;
2997 double fabs_value = 0.0;
2998
2999 //int v_level;
3000 double coeff_ratio;
3001 for (i=0; i<num_row_cuts; i++) {
3002 /* check for violation, duplicacy, quality of coefficients, length */
3003 row_cut = cutlist->rowCut(i);
3004 num_elements = row_cut.row().getNumElements();
3005 //cut_size[accepted_cnt] = num_elements;
3006 indices = const_cast<int *> (row_cut.row().getIndices());
3007 elements = const_cast<double *> (row_cut.row().getElements());
3008 rhs = row_cut.rhs();
3009 discard_cut = FALSE;
3010 max_coeff = 0;
3011 min_coeff = DBL_MAX;
3012
3013 if (verbosity>10) {
3014 row_cut.print();
3015 }
3016
3017 if (num_elements > max_elements){
3018 PRINT(verbosity,5,("Threw out cut because its length %d is too "
3019 "high.\n\n\n", num_elements));
3020 //printf("%i %i %i \n", num_elements, max_elements, generator);
3021 num_poor_quality++;
3022 //is_deleted[i] = TRUE;
3023 continue;
3024 }
3025
3026 /* hash value, min, max, violation */
3027 hash_value = 0;
3028 violation = 0;
3029 int is_int = TRUE;
3030 for (int el_num=0; el_num<num_elements; el_num++) {
3031
3032 if(!(lp_data->vars[indices[el_num]]->is_int)) is_int = FALSE;
3033
3034 // printf("%f\n", elements[el_num]);
3035 fabs_value = fabs(elements[el_num]);
3036 if (fabs_value>max_coeff) {
3037 max_coeff = fabs_value;
3038 }
3039 if (fabs_value < min_coeff) {
3040 min_coeff = fabs_value;
3041 }
3042 tmp_matind[el_num] = vars[indices[el_num]]->userind;
3043 hash_value += elements[el_num]*random_hash[tmp_matind[el_num]];
3044 violation += elements[el_num]*x[tmp_matind[el_num]];
3045 }
3046 //hashes[*num_cuts + accepted_cnt] = hash_value;
3047 /* see rhs as well */
3048 #if 1
3049 fabs_value = fabs(rhs);
3050 if (fabs_value > lpetol) {
3051 if (fabs_value < min_coeff) {
3052 min_coeff = fabs_value;
3053 }
3054 if (fabs_value > max_coeff) {
3055 max_coeff = fabs_value;
3056 }
3057 }
3058 #endif
3059 switch (row_cut.sense()) {
3060 case 'L':
3061 violation -= rhs;
3062 break;
3063 case 'G':
3064 violation = rhs - violation;
3065 break;
3066 case 'E':
3067 violation = fabs(rhs - violation);
3068 break;
3069 }
3070 //v_level = 1;
3071 coeff_ratio = min_coeff/max_coeff;
3072 /* check quality */
3073 if (num_elements>0) {
3074 if ( (max_coeff > 0 && coeff_ratio < etol1000)||
3075 (min_coeff > 0 && min_coeff < etol1000) ) {
3076 PRINT(verbosity,5,("Threw out cut because of bad coeffs.\n"));
3077 //printf("%f %f %f\n\n", min_coeff, max_coeff, etol1000);
3078 num_poor_quality++;
3079 //is_deleted[i] = TRUE;
3080 continue;
3081 }
3082 }
3083
3084 if (violation < etol10){//*v_level){
3085 PRINT(verbosity,5,("violation = %f. Threw out cut.\n",
3086 violation));
3087 num_unviolated++;
3088 //is_deleted[i] = TRUE;
3089 continue;
3090 }//else printf("violation - %f \n", violation);
3091
3092 /* check if sense is 'R' */
3093 if (row_cut.sense()=='R') {
3094 PRINT(verbosity,5,("cut #%d has a range. thrown out.\n", i));
3095 //is_deleted[i] = TRUE;
3096 continue;
3097 }
3098
3099 if(p->par.best_violation[generator] < lpetol){
3100 update_cut_length = TRUE;
3101 }
3102
3103 if(update_cut_length){
3104 if(violation > p->par.best_violation[generator]){
3105 //printf("%i - %f\n", generator, violation);
3106 p->par.best_violation[generator] = violation;
3107 p->par.best_violation_length[generator] = 4*num_elements;
3108 }
3109 }
3110
3111 /* cut is accepted. congratulations. */
3112 hashes[*num_cuts + accepted_cnt] = hash_value;
3113 accepted_ind[accepted_cnt] = i;
3114 accepted_cnt++;
3115
3116 if (generator == CGL_GOMORY_GENERATOR){
3117 p->lp_stat.gomory_nz += num_elements;
3118 }
3119
3120 //j++;
3121 #ifdef COMPILE_IN_LP
3122 if(p->bc_index < 1 && p->mip->mip_inf && ( generator == CGL_PROBING_GENERATOR ||
3123 generator == CGL_CLIQUE_GENERATOR ||
3124 generator == CGL_KNAPSACK_GENERATOR)){
3125 add_cut_to_mip_inf(p, num_elements, indices, elements, rhs, row_cut.sense());
3126 }
3127 #endif
3128 }
3129
3130 /* check for duplicates */
3131 hashes += *num_cuts;
3132 qsort_di(hashes, accepted_ind, accepted_cnt);
3133 int l_ind, r_ind, c_ind;
3134 int move_ratio = num_row_cuts + 100;
3135 for(l_ind = 0; l_ind < accepted_cnt;){
3136 c_ind = accepted_ind[l_ind];
3137 accepted_ind[l_ind] += move_ratio;
3138 for(r_ind = l_ind + 1; r_ind < accepted_cnt; r_ind++){
3139 if(fabs(hashes[l_ind] - hashes[r_ind]) < lpetol){
3140 PRINT(verbosity,5,("cut #%i is same as cut #%i\n", c_ind, accepted_ind[r_ind]));
3141 num_duplicate++;
3142 //is_deleted[i] = TRUE;
3143 r_ind++;
3144 }else{
3145 l_ind = r_ind;
3146 break;
3147 }
3148 }
3149 if(r_ind >= accepted_cnt) break;
3150 }
3151
3152 r_ind = accepted_cnt;
3153 accepted_cnt = 0;
3154 for(l_ind = 0; l_ind < r_ind; l_ind++){
3155 c_ind = accepted_ind[l_ind] - move_ratio;
3156 if(c_ind >= 0){
3157 hashes[accepted_cnt] = hashes[l_ind];
3158 accepted_ind[accepted_cnt++] = c_ind;
3159 }
3160 }
3161 hashes -= *num_cuts;
3162
3163 int * rc_ind = 0;
3164 int rc_cnt = 0;
3165 if (p->bc_index > 0 && p->mip->mip_inf && p->mip->mip_inf->c_num && generator == CGL_NUM_GENERATORS - 1){
3166 MIPinfo * mip_inf = p->mip->mip_inf;
3167 rc_ind = mip_inf->c_tmp;
3168 int c_num = mip_inf->c_num;
3169 int is_identical;
3170 /* check only for hash value and violation */
3171 for(int t_num = 0; t_num < c_num; t_num++){
3172 num_elements = mip_inf->c_beg[t_num + 1] - mip_inf->c_beg[t_num];
3173 elements = mip_inf->c_val + mip_inf->c_beg[t_num];
3174 indices = mip_inf->c_ind + mip_inf->c_beg[t_num];
3175 rhs = mip_inf->c_rhs[t_num];
3176 hash_value = 0.0;
3177 violation = 0.0;
3178 is_identical = FALSE;
3179
3180 for (int el_num=0; el_num<num_elements; el_num++) {
3181 tmp_matind[el_num] = vars[indices[el_num]]->userind;
3182 if(*num_cuts + accepted_cnt > 0) hash_value += elements[el_num]*random_hash[tmp_matind[el_num]];
3183 violation += elements[el_num]*x[tmp_matind[el_num]];
3184 }
3185
3186 switch (mip_inf->c_sense[t_num]) {
3187 case 'L':
3188 violation -= rhs;
3189 break;
3190 case 'G':
3191 violation = rhs - violation;
3192 break;
3193 case 'E':
3194 violation = fabs(rhs - violation);
3195 break;
3196 }
3197
3198 if (violation < etol100){
3199 continue;
3200 }
3201
3202 for(k = 0; k < accepted_cnt + *num_cuts; k++){
3203 if (fabs(hashes[k]-hash_value) < lpetol) {
3204 is_identical = TRUE;
3205 break;
3206 }
3207 }
3208
3209 if (is_identical){
3210 continue;
3211 }
3212
3213 rc_ind[rc_cnt] = t_num;
3214 rc_cnt++;
3215 }
3216 }
3217
3218 //if(rc_cnt > 0) printf("root cuts added %i %i\n", p->bc_index, rc_cnt);
3219
3220 int new_cut_num = accepted_cnt + rc_cnt;
3221
3222 /* copy the accepted cuts */
3223 if(new_cut_num > 0){
3224 if (*cuts){
3225 *cuts = (cut_data **)realloc(*cuts, (*num_cuts+new_cut_num)*sizeof(cut_data *));
3226 }else{
3227 *cuts = (cut_data **)malloc(new_cut_num*sizeof(cut_data *));
3228 }
3229 }
3230
3231 k = *num_cuts;
3232
3233 int p_cnt = 0;
3234 int ind = 0;
3235 char sense; double range;
3236
3237 //for (i=0; i<num_row_cuts + rc_cnt; i++) {
3238 for (i=0; i<new_cut_num; i++) {
3239 if (i < accepted_cnt){
3240 //if(is_deleted[i] == TRUE) {
3241 // continue;
3242 //}
3243 ind = accepted_ind[i];
3244 //if(ind - move_ratio < 0) continue;
3245 row_cut = cutlist->rowCut(ind);
3246 num_elements = row_cut.row().getNumElements();
3247 //PRINT(verbosity, -1,("length = %d \n", num_elements));
3248 indices = const_cast<int *> (row_cut.row().getIndices());
3249 elements = const_cast<double *> (row_cut.row().getElements());
3250 rhs = row_cut.rhs();
3251 sense = row_cut.sense();
3252 range = row_cut.range();
3253 }else{
3254 ind = rc_ind[i - accepted_cnt];
3255 num_elements = p->mip->mip_inf->c_beg[ind + 1] -
3256 p->mip->mip_inf->c_beg[ind];
3257 indices = p->mip->mip_inf->c_ind + p->mip->mip_inf->c_beg[ind];
3258 elements = p->mip->mip_inf->c_val + p->mip->mip_inf->c_beg[ind];
3259 rhs = p->mip->mip_inf->c_rhs[ind];
3260 sense = p->mip->mip_inf->c_sense[ind];
3261 range = 0;//sense = p->mip->mip_inf->c_sense[c_ind];
3262 }
3263 (*cuts)[k] = (cut_data *) calloc(1, sizeof(cut_data));
3264 sym_cut = (*cuts)[k];
3265 sym_cut->type = EXPLICIT_ROW;
3266 sym_cut->rhs = rhs;
3267 sym_cut->range = range;
3268 //sym_cut->size = (num_elements * (int)((ISIZE + DSIZE) + DSIZE));
3269 sym_cut->size = (int)(DSIZE + num_elements * (ISIZE + DSIZE));
3270 sym_cut->coef = (char *) malloc (sym_cut->size);
3271 sym_cut->sense = sense;
3272 ((double *) (sym_cut->coef))[0] = 0; // otherwise valgrind complains.
3273 ((int *) (sym_cut->coef))[0] = num_elements;
3274
3275 //Here, we have to pad the initial int to avoid misalignment, so we
3276 //add DSIZE bytes to get to a double boundary
3277 matval = (double *) (sym_cut->coef + DSIZE);
3278 matind = (int *) (sym_cut->coef + (num_elements + 1)*DSIZE);
3279 memcpy((char *)matval, (char *)elements, num_elements * DSIZE);
3280 if (is_userind_in_order == TRUE) {
3281 memcpy((char*)matind, (char *)indices, num_elements * ISIZE);
3282 } else {
3283 for (int i2=0; i2<num_elements; i2++) {
3284 tmp_matind[i2] = vars[indices[i2]]->userind;
3285 }
3286 memcpy((char*)matind, (char *)tmp_matind, num_elements * ISIZE);
3287 }
3288
3289 qsort_id(matind, matval, num_elements);
3290
3291 sym_cut->branch = DO_NOT_BRANCH_ON_THIS_ROW;
3292
3293 sym_cut->deletable = TRUE;
3294
3295 #ifdef COMPILE_IN_LP
3296 if(p->bc_level < 1 && p->mip->mip_inf && (generator == CGL_PROBING_GENERATOR ||
3297 generator == CGL_CLIQUE_GENERATOR ||
3298 generator == CGL_KNAPSACK_GENERATOR)){
3299
3300 double sos_ratio = 1.0*p->mip->mip_inf->binary_sos_row_num/(p->mip->m + 1);
3301
3302 if( ((sos_ratio >= 0.9 && p->iter_num < 2) ||
3303 (sos_ratio > 0.1 && sos_ratio < 0.9 && p->mip->mip_inf->prob_type == BINARY_TYPE) ||
3304 (sos_ratio > 0.5 && sos_ratio < 0.9 && p->mip->mip_inf->prob_type == BIN_CONT_TYPE)) &&
3305 p->node_iter_num < 5 && p_cnt < 50){// && cut_size[i] > 2){
3306 //sym_cut->deletable = FALSE;
3307 p_cnt++;
3308 }
3309 }
3310 #endif
3311 if (send_to_pool){
3312 sym_cut->name = CUT__SEND_TO_CP;
3313 }else{
3314 sym_cut->name = CUT__DO_NOT_SEND_TO_CP;
3315 }
3316 k++;
3317 }
3318 *num_cuts = k;
3319 // TODO: short circuit the copying to row data and si */
3320 for (i=0; i<num_row_cuts; i++) {
3321 cutlist->eraseRowCut(0);
3322 }
3323
3324 //FREE(hashes);
3325 //FREE(is_deleted);
3326 //FREE(accepted_ind);
3327 //FREE(cut_size);
3328
3329 /* update statistics */
3330 p->lp_stat.num_duplicate_cuts += num_duplicate;
3331 p->lp_stat.num_poor_cuts += num_poor_quality;
3332 p->lp_stat.num_unviolated_cuts += num_unviolated;
3333 p->lp_stat.cuts_generated += num_row_cuts;
3334 if (p->bc_level<1) {
3335 p->lp_stat.cuts_root += num_row_cuts;
3336 }
3337
3338 switch (generator) {
3339 case (CGL_PROBING_GENERATOR):
3340 p->lp_stat.probing_cuts += num_row_cuts;
3341 if (p->bc_level<1) {
3342 p->lp_stat.probing_cuts_root += num_row_cuts;
3343 }
3344 break;
3345 case (CGL_CLIQUE_GENERATOR):
3346 p->lp_stat.clique_cuts += num_row_cuts;
3347 if (p->bc_level<1) {
3348 p->lp_stat.clique_cuts_root += num_row_cuts;
3349 }
3350 break;
3351 case (CGL_KNAPSACK_GENERATOR):
3352 p->lp_stat.knapsack_cuts += num_row_cuts;
3353 if (p->bc_level<1) {
3354 p->lp_stat.knapsack_cuts_root += num_row_cuts;
3355 }
3356 break;
3357 case (CGL_GOMORY_GENERATOR):
3358 p->lp_stat.gomory_cuts += num_row_cuts;
3359 if (p->bc_level<1) {
3360 p->lp_stat.gomory_cuts_root += num_row_cuts;
3361 }
3362 break;
3363 case (CGL_TWOMIR_GENERATOR):
3364 p->lp_stat.twomir_cuts += num_row_cuts;
3365 if (p->bc_level<1) {
3366 p->lp_stat.twomir_cuts_root += num_row_cuts;
3367 }
3368 break;
3369 case (CGL_FLOWCOVER_GENERATOR):
3370 p->lp_stat.flowcover_cuts += num_row_cuts;
3371 if (p->bc_level<1) {
3372 p->lp_stat.flowcover_cuts_root += num_row_cuts;
3373 }
3374 break;
3375 case (CGL_ODDHOLE_GENERATOR):
3376 p->lp_stat.oddhole_cuts += num_row_cuts;
3377 if (p->bc_level<1) {
3378 p->lp_stat.oddhole_cuts_root += num_row_cuts;
3379 }
3380 break;
3381 }
3382
3383 cut_time = used_time(&total_time);
3384 p->comp_times.dupes_and_bad_coeffs_in_cuts += cut_time;
3385
3386 return 0;
3387 }
3388 #endif
3389 /*===========================================================================*/
3390 int add_cut_to_mip_inf(lp_prob *p, int cut_n, int *cut_ind, double *cut_val, double cut_rhs, char cut_sense){
3391
3392 MIPinfo *mip_inf = p->mip->mip_inf;
3393 int alloc_size = mip_inf->c_alloc_size;
3394 int alloc_num = mip_inf->c_alloc_num;
3395 //int t_nz = 0;//mip_inf->c_nz;
3396 if(alloc_size < 1){
3397 alloc_size = MAX(100*cut_n, (int)(100.0*p->lp_data->nz/p->lp_data->m));
3398 alloc_num = 1000;
3399
3400 mip_inf->c_ind = (int *)malloc(ISIZE*alloc_size);
3401 mip_inf->c_beg = (int *)malloc(ISIZE*(alloc_num + 1));
3402 mip_inf->c_val = (double *)malloc(DSIZE*alloc_size);
3403 mip_inf->c_sense = (char *)malloc(CSIZE*alloc_num);
3404 mip_inf->c_rhs = (double *)malloc(DSIZE*alloc_num);
3405 mip_inf->c_tmp = (int *)malloc(ISIZE*alloc_num);
3406
3407 mip_inf->c_alloc_size = alloc_size;
3408 mip_inf->c_alloc_num = alloc_num;
3409 mip_inf->c_beg[0] = 0;
3410 }else{
3411 if(alloc_size < mip_inf->c_beg[mip_inf->c_num] + cut_n){
3412 alloc_size += MAX(10*cut_n, (int)(10.0*p->lp_data->nz/p->lp_data->m));
3413 mip_inf->c_ind = (int *)realloc(mip_inf->c_ind, ISIZE*alloc_size);
3414 mip_inf->c_val = (double *)realloc(mip_inf->c_val, DSIZE*alloc_size);
3415 mip_inf->c_alloc_size = alloc_size;
3416 }
3417 if(mip_inf->c_num >= alloc_num){
3418 alloc_num += 1000;
3419 mip_inf->c_beg = (int *)realloc(mip_inf->c_beg, ISIZE*(alloc_num + 1));
3420 mip_inf->c_sense = (char *)realloc(mip_inf->c_sense, CSIZE*alloc_num);
3421 mip_inf->c_rhs = (double *)realloc(mip_inf->c_rhs, DSIZE*alloc_num);
3422 mip_inf->c_tmp = (int *)realloc(mip_inf->c_tmp, ISIZE*alloc_num);
3423
3424 mip_inf->c_alloc_num = alloc_num;
3425 }
3426 }
3427
3428 int *t_ind = mip_inf->c_ind;
3429 double *t_var = mip_inf->c_val;
3430 int *t_beg = mip_inf->c_beg;
3431 char *t_sense = mip_inf->c_sense;
3432 double *t_rhs = mip_inf->c_rhs;
3433 int t_num = mip_inf->c_num;
3434 //t_num++;
3435
3436 for (int el_num=0, t_loc = t_beg[t_num]; el_num<cut_n; el_num++, t_loc++) {
3437 t_ind[t_loc] = cut_ind[el_num];
3438 t_var[t_loc] = cut_val[el_num];
3439 }
3440
3441 t_beg[t_num + 1] = t_beg[t_num] + cut_n;
3442 t_sense[t_num] = cut_sense;
3443 t_rhs[t_num] = cut_rhs;
3444 //t_num++;
3445 (mip_inf->c_num)++;
3446
3447 return 0;
3448 }
3449
3450 /*===========================================================================*/
3451 #ifdef USE_CGL_CUTS
3452 int add_col_cuts(lp_prob *p, OsiCuts *cutlist, int *bound_changes)
3453 {
3454 int i, j;
3455 OsiColCut col_cut;
3456 const int verbosity = p->par.verbosity;
3457 int *indices;
3458 double *elements;
3459 double newb;
3460 int num_col_cuts;
3461 LPdata *lp_data = p->lp_data;
3462 var_desc **vars = lp_data->vars;
3463 const double big_bound = 1e25;
3464
3465 num_col_cuts = cutlist->sizeColCuts();
3466 for (i=0; i<num_col_cuts; i++) {
3467 col_cut = cutlist->colCut(i);
3468 if (verbosity>10) {
3469 col_cut.print();
3470 }
3471 indices = const_cast<int *>(col_cut.lbs().getIndices());
3472 elements = const_cast<double *>(col_cut.lbs().getElements());
3473 for (j=0;j<col_cut.lbs().getNumElements();j++) {
3474 newb = elements[j];
3475 if (newb > big_bound) {
3476 newb = big_bound;
3477 } else if (newb < -big_bound) {
3478 newb = -big_bound;
3479 }
3480 if (vars[indices[j]]->new_lb < newb) {
3481 vars[indices[j]]->new_lb = newb;
3482 change_lbub(lp_data, indices[j], newb, vars[indices[j]]->new_ub);
3483 (*bound_changes)++;
3484 }
3485 }
3486 indices = const_cast<int *>(col_cut.ubs().getIndices());
3487 elements = const_cast<double *>(col_cut.ubs().getElements());
3488 for (j=0;j<col_cut.ubs().getNumElements();j++) {
3489 newb = elements[j];
3490 if (newb > big_bound) {
3491 newb = big_bound;
3492 } else if (newb < -big_bound) {
3493 newb = -big_bound;
3494 }
3495 if (vars[indices[j]]->new_ub > newb) {
3496 vars[indices[j]]->new_ub = newb;
3497 change_lbub(lp_data, indices[j], vars[indices[j]]->new_lb, newb);
3498 (*bound_changes)++;
3499 }
3500 }
3501 }
3502
3503
3504
3505 for (i=0; i<num_col_cuts; i++) {
3506 cutlist->eraseColCut(0);
3507 }
3508
3509 return 0;
3510 }
3511 #endif
3512 /*===========================================================================*/
3513 int should_stop_adding_cgl_cuts(lp_prob *p, int i, int *should_stop)
3514 {
3515 *should_stop = FALSE;
3516 return 0;
3517 }
3518
3519 /*===========================================================================*/
3520 int update_pcost(lp_prob *p)
3521 {
3522 #ifdef COMPILE_IN_LP
3523 bc_node *parent = p->tm->active_nodes[p->proc_index]->parent;
3524 char sense = parent->bobj.sense[0];
3525 int branch_var = parent->bobj.position;
3526 double *pcost_down = p->pcost_down;
3527 double *pcost_up = p->pcost_up;
3528 int *br_rel_down = p->br_rel_down;
3529 int *br_rel_up = p->br_rel_up;
3530 double objval = p->lp_data->objval;
3531 double oldobjval = p->tm->active_nodes[p->proc_index]->lower_bound;
3532 double oldx = parent->bobj.value;
3533 double *x;
3534
3535 if(parent->bobj.type == SOS1_IMPLICIT){
3536 return 0;
3537 }
3538
3539 //get_x(p->lp_data);
3540 x = p->lp_data->x;
3541 if (parent->children[0]->bc_index != p->bc_index) {
3542 sense = (sense == 'L') ? 'G' : 'L';
3543 }
3544 if (sense == 'L') {
3545 if (oldx - x[branch_var] > 1e-5) {
3546 pcost_down[branch_var] = (pcost_down[branch_var]*
3547 br_rel_down[branch_var] + (objval - oldobjval)/
3548 (oldx-x[branch_var]))/(br_rel_down[branch_var] + 1);
3549 //printf("new pcost_down[%d] = %f\n", branch_var, pcost_down[branch_var]);
3550 br_rel_down[branch_var]++;
3551 } else {
3552 PRINT(p->par.verbosity, 0, ("warning: poor lpetol used while branching\n"));
3553 }
3554 } else {
3555 if (x[branch_var] - oldx > 1e-5) {
3556 pcost_up[branch_var] = (pcost_up[branch_var]*
3557 br_rel_up[branch_var] + (objval - oldobjval)/
3558 (x[branch_var]-oldx))/(br_rel_up[branch_var] + 1);
3559 //printf("new pcost_up[%d] = %f\n", branch_var, pcost_up[branch_var]);
3560 br_rel_up[branch_var]++;
3561 } else {
3562 PRINT(p->par.verbosity, 0, ("warning: poor lpetol used while branching\n"));
3563 }
3564 }
3565
3566 p->lp_stat.avg_br_obj_impr_in_path = ((p->bc_level-1)*
3567 p->lp_stat.avg_br_obj_impr_in_path + objval - oldobjval)/p->bc_level;
3568 #endif
3569 return 0;
3570 }
3571 /*===========================================================================*/
3572
3573 /* check if lb <= ub for each variable. otherwise fathom this branch. */
3574 int check_bounds(lp_prob *p, int *termcode)
3575 {
3576 int i;
3577 double *lb, *ub;
3578 const double lpetol = p->lp_data->lpetol;
3579 const int n = p->lp_data->n;
3580 LPdata *lp_data = p->lp_data;
3581
3582 get_bounds(lp_data);
3583 lb = lp_data->lb;
3584 ub = lp_data->ub;
3585
3586 for (i=0; i<n; i++) {
3587 if (lb[i] > ub[i]+lpetol) {
3588 break;
3589 }
3590 }
3591 if (i<n) {
3592 *termcode = LP_D_UNBOUNDED;
3593 }
3594 return 0;
3595 }
3596 /*===========================================================================*/
3597 /*===========================================================================*/
3598