1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 1995 - 2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): Andrew Eremin, IC-Parc 20% 21% END LICENSE BLOCK 22% ---------------------------------------------------------------------- 23% 24% Description: ECLiPSe best-first search library 25% 26% System: ECLiPSe Constraint Logic Programming System 27% Author/s: Andrew Eremin, IC-Parc 28% Version: $Id: bfs.ecl,v 1.1 2012/07/31 02:17:06 jschimpf Exp $ 29% 30% ---------------------------------------------------------------------- 31 32 33% ---------------------------------------------------------------------- 34:- module(bfs). 35 36:- lib(constraint_pools). 37:- lib(hash). 38:- lib(eplex). 39:- lib(n_trees). 40 41% ---------------------------------------------------------------------- 42% 43% Meta-attribute 44% 45% ---------------------------------------------------------------------- 46 47:- meta_attribute(bfs, [unify:unify_bfs/2]). 48 49:- local struct( 50 bfs( 51 optimal_val, 52 type, 53 node_info, 54 pseudocost:pseudocost, 55 solver, 56 next 57 ) 58 ). 59 60% ---------------------------------------------------------------------- 61% 62% Bfs var node info structure 63% 64% ---------------------------------------------------------------------- 65 66:- local struct( 67 bfs_node_info( 68 id, % int: node number 69 lo, % float: node lower bound 70 hi, % float: node upper bound 71 val, % float: node optimal solution value 72 rc % float: node reduced cost 73 ) 74 ). 75 76% ---------------------------------------------------------------------- 77% 78% Pools 79% 80% ---------------------------------------------------------------------- 81 82:- export bfs_instance/1. % bfs_instance(+PoolName) 83 84:- local struct(bfs_constraint_type(branch, global_cut)). 85 86% ---------------------------------------------------------------------- 87% 88% Best-first search tree structure 89% 90% ---------------------------------------------------------------------- 91 92:- local struct( 93 bfs_tree( 94 pool, % the pool with which the 95 % solver is associated 96 module, % caller module 97 98 data, % arbitrary prob data that 99 % branches may want to access: 100 % probably variables in some 101 % structured form since 102 % branches are stored over 103 % failure and cannot contain 104 % explicit vars 105 feas_check, % the arbitrary global 106 % feasibility check 107 % (intention is other than 108 % variable integrality) 109 110 shelf, % ECLiPSe shelf for storing 111 % various results over failures 112 cost, % var: variable for the 113 % optimal cost 114 integral_obj, % atom: yes or no, is the cost 115 % of all feasible 116 % solutions integral? 117 int_tolerance, % float: integrality tolerance 118 sense, % min or max: optimisation sense 119 node_susp, % suspension list containing 120 % the suspension for the node 121 % solver 122 vars, % []: list of all vars currently 123 % belonging to this tree 124 root_node, % n_tree: the root of the 125 % search tree 126 % represented as a 127 % n_tree 128 next_node_no, % int: the id for the next 129 % node created 130 best_bound, % float: current best global 131 % feasible solution 132 % objective value 133 gubs, % [GUB1,...,GUBm]: list of 134 % bfs_gub structures for 135 % the GUBs of this problem 136 stats:stats, % structure holding 137 % statistics info 138 info_messages, % on, off: info message status 139 % Search Control: node selection 140 node_select, % atom: best_first, depth_first, 141 % best_estimate 142 % node selection criteria 143 % Search Control: problem division 144 alpha_min, % float: constants used in 145 alpha_max, % float: utilising variable 146 % up/down estimations 147 % for branching: 148 % variable estimation = 149 % alpha_min * 150 % min(up/down est) + 151 % alpha_max * 152 % max(up/down est) 153 beta_const, % float: constants used in 154 beta_pc, % float: calculating variable 155 beta_lb, % float: up/down estimations: 156 % up/down estimation = 157 % beta_const + 158 % beta_pc * pseudocost + 159 % beta_lb * lowerbound 160 pcd_average, % float: average observed 161 % down-branch pseudocost 162 pcd_count, % int: number of observed 163 % down-branches 164 pcu_average, % float: average observed 165 % up-branch pseudocost 166 pcu_count, % int: number of observed 167 % up-branches 168 pc_init, % atom: average,calculated,cost: 169 % pseudocost initialization 170 % method: 171 % set to current average, 172 % calulated, 173 % set to objective cost 174 % coefficient 175 pc_ratio, % float: ratio in (0.0..1.0) 176 % of max work in calculating 177 % pseudocosts to root node 178 % solution work 179 pc_update, % atom: average,first,last: 180 % pseudocost update method 181 % set to average/first/last 182 % of observed degradations 183 lb_time % int: time limit in seconds 184 % for lower bound calculation 185 ) 186 ). 187 188% ---------------------------------------------------------------------- 189% 190% bfs_tree shelf structure 191% 192% ---------------------------------------------------------------------- 193 194:- local struct(bfs_shelf(branches, global_cuts, info)). 195 196% ---------------------------------------------------------------------- 197% 198% Branch-and-Price search tree node structure 199% 200% ---------------------------------------------------------------------- 201 202:- local struct( 203 bfs_node( 204 id, % int: node number 205 state, % arbitrary local state for the 206 % node solver 207 rank, % node ranking for node selection 208 objval, % float: relaxed optimal 209 % solution value 210 parent_obj, % float: relaxed optimal 211 % solution value of 212 % parent node 213 % these two are needed when 214 % using pseudocost-based 215 % methods 216 pc_update, % pseudocost to update after 217 % solving node: [GUBNo, BPNo, Dir] 218 frac_vars, % []: integer vars with fractional 219 % node optimal solution 220 branches % []: current branching decisions 221 ) 222 ). 223 224% ---------------------------------------------------------------------- 225% 226% Generalised Upper/Lower bound structure 227% 228% ---------------------------------------------------------------------- 229 230:- local struct( 231 bfs_gub( 232 vars, 233 refs, 234 pseudocosts 235 ) 236 ). 237 238% ---------------------------------------------------------------------- 239% 240% Pseudocost structure 241% 242% ---------------------------------------------------------------------- 243 244:- local struct( 245 pseudocost( 246 pcd, 247 pcd_count, 248 pcu, 249 pcu_count 250 ) 251 ). 252 253% ---------------------------------------------------------------------- 254% 255% Statistics structure 256% 257% ---------------------------------------------------------------------- 258 259:- local struct( 260 stats( 261 start_time, 262 total_time, 263 first_sol_time, 264 opt_sol_time, 265 no_sols, 266 solve_time, 267 separate_time, 268 nodes_separated, 269 nodes_solved 270 ) 271 ). 272 273% ---------------------------------------------------------------------- 274% 275% exports 276% 277% ---------------------------------------------------------------------- 278 279:- export bfs_integers/2. 280:- export bfs_node_info/3. 281:- export bfs_node_info/6. 282:- export bfs_statistics/1. 283:- export bfs_node_cost/2. 284:- export bfs_var_get/4. 285:- export bfs_get/3. 286:- export bfs_set/3. 287:- export bfs_impose_node_state/2. 288:- export bfs_solver_setup/3. 289:- export bfs_solver_setup/4. 290:- export bfs_solve/2. 291:- export bfs_branch/2. 292:- export bfs_branch/3. 293:- export bfs_global_cut/2. 294:- export bfs_minimize_eplex_node/2. 295:- export bfs_update_pseudocosts/1. 296:- export bfs_deg_est/2. 297:- export bfs_strong/2. 298:- export bfs_enhanced/2. 299:- export bfs_fracvar/1. 300 301% ---------------------------------------------------------------------- 302% 303% bfs attribute handlers 304% 305% ---------------------------------------------------------------------- 306 307unify_bfs(_, Attr) :- 308 var(Attr). % Ignore if not a bfs var 309unify_bfs(Term, Attr) :- 310 compound(Attr), 311 unify_term_bfs(Term, Attr). 312 313:- mode unify_term_bfs(?, +). 314unify_term_bfs(X, Attr) :- 315 nonvar(X), % bfs var and NONVAR - instantiated 316 instantiation_deviates_for_handle(Attr, X). 317unify_term_bfs(Y{bfs:AttrY}, AttrX) :- 318 -?-> 319 unify_bfs_bfs(Y, AttrY, AttrX). 320 321unify_bfs_bfs(_, AttrY, AttrX) :- 322 var(AttrY), % No attribute for this extension 323 AttrX = AttrY. % Transfer the attribute 324unify_bfs_bfs(_, AttrY, AttrX) :- 325 nonvar(AttrY), % bfs var and bfs var 326 unify_bfs_handles(AttrX, AttrY). 327 328instantiation_deviates_for_handle(ThisAttr, X) :- 329 ( compound(ThisAttr) -> 330 ThisAttr = bfs with [ 331 solver:Handle, 332 optimal_val:Val, 333 next:NextAttr 334 ], 335 ( X = Val -> % instantiated to its optimal_val 336 true 337 ; bfs_next_node(Handle, _SubTree) -> 338 % Still processing: the optimal val is only 339 % current optimal in the tree, and quite 340 % likely the instantiation has been caused 341 % by the tree search at another node, so 342 % do not rewake the solver now because it 343 % could fail incorrectly. 344 true 345 ; 346 % finished solving so this was a true optimal, 347 % wake solver 348 schedule_suspensions(node_susp of bfs_tree, Handle), 349 wake 350 ), 351 instantiation_deviates_for_handle(NextAttr, X) 352 ; 353 % chain terminated by atom 'end' 354 true 355 ). 356 357unify_bfs_handles(ThisAttrX, AttrY) :- 358 ThisAttrX = bfs with [ 359 solver:Handle, 360 next:NextAttrX 361 ], 362 remove_bfs_attr_for_handle(Handle, AttrY, ThisAttrY, NextAttrY), 363 ( compound(ThisAttrY) -> 364 % two variables in the same solver are unified, 365 % send an equality constraint to the solver and wake it 366 % Note to AE: how do I get back the vars? 367 schedule_suspensions(node_susp of bfs_tree, Handle), 368 wake 369 ; 370 % Y has no attribute for Pool 371 ThisAttrY = end 372 ), 373 % continue with the rest of X and Ys chains 374 unify_bfs_handles(NextAttrX, ThisAttrX, NextAttrY). 375 376unify_bfs_handles(ThisAttrX, Attr0, AttrY) :- 377 ( compound(ThisAttrX) -> 378 ( compound(AttrY) -> 379 ThisAttrX = bfs with [ 380 solver:Handle, 381 next:NextAttrX 382 ], 383 remove_bfs_attr_for_handle(Handle, AttrY, ThisAttrY, NextAttrY), 384 ( compound(ThisAttrY) -> 385 % two variables in the same solver are unified, 386 % send an equality constraint for the two columns 387 % to the external solver and wake it 388 % Note to AE: how do I get back the vars? 389 schedule_suspensions(node_susp of bfs_tree, Handle), 390 wake 391 ; 392 % Y has no attribute for Pool 393 ThisAttrY = end 394 ), 395 % continue with the rest of X and Ys chains 396 unify_bfs_handles(NextAttrX, ThisAttrX, NextAttrY) 397 ; 398 % Ys chain terminated by atom'end' 399 true 400 ) 401 ; 402 % Xs chain terminated by atom 'end' 403 % put the rest of Ys chain here 404 setarg(next of bfs, Attr0, AttrY) 405 ). 406 407% From a bfs_attr, removes the attribute corresponding to that for the 408% first argument form the chain and returns it. Fails if none found. 409remove_bfs_attr_for_handle(Handle, ThisAttr, Attr, RestAttr) :- 410 % no need to test for var(ThisAttr) in chain 411 ThisAttr = bfs with [solver:ThisHandle, next:NextAttr], 412 (ThisHandle == Handle -> 413 RestAttr = NextAttr, 414 setarg(next of bfs, ThisAttr, end), 415 Attr = ThisAttr 416 ; 417 RestAttr = ThisAttr, 418 dechain_bfs_attr_for_handle1(Handle, NextAttr, ThisAttr, Attr) 419 ). 420 421dechain_bfs_attr_for_handle1(Handle, ThisAttr, Attr0, Attr) :- 422 % no need to test for var(ThisAttr) in chain 423 ( ThisAttr = bfs with [solver:ThisHandle, next:NextAttr] -> 424 (ThisHandle == Handle -> 425 setarg(next of bfs, Attr0, NextAttr), 426 setarg(next of bfs, ThisAttr, end), 427 Attr = ThisAttr 428 ; 429 dechain_bfs_attr_for_handle1(Handle, NextAttr, ThisAttr, Attr) 430 ) 431 ; % chain terminated by atom 'end' 432 ThisAttr = Attr 433 ). 434 435% ---------------------------------------------------------------------- 436 437get_bfs_attr(X{bfs:Attr0}, Handle, Attr) ?- 438 ( var(Attr0) -> 439 new_bfs_attr(X, Handle, Attr) 440 ; 441 Attr0 = bfs with [solver:Handle0,next:Next], 442 % should not fail unless Attr0 incorrect 443 ( Handle0 == Handle -> 444 Attr = Attr0 445 ; 446 get_bfs_attr1(Next, Attr0, Handle, Attr) 447 ) 448 ). 449get_bfs_attr(X, Handle, Attr) :- % make a new bfs variable 450 free(X), 451 new_bfs_attr(X, Handle, Attr). 452 453get_bfs_attr1(ThisAttr, Attr0, Handle, Attr) :- 454 atom(ThisAttr), !, % chain terminated by atom 'end' 455 new_bfs_attrstruct(Handle, Attr), 456 setarg(next of bfs, Attr0, Attr). 457get_bfs_attr1(ThisAttr, _Attr0, Handle, Attr) :- 458 ThisAttr = bfs with [solver:Handle0,next:Next], 459 ( Handle0 == Handle -> 460 Attr = ThisAttr 461 ; 462 get_bfs_attr1(Next, ThisAttr, Handle, Attr) 463 ). 464 465new_bfs_attr(X, Handle, Attr) :- % make a new bfs variable: 466 new_bfs_attrstruct(Handle, Attr), 467 add_attribute(X, Attr, bfs), % add a bfs attribute 468 Handle = bfs_tree{vars:Vars}, 469 ( var(Vars) -> Vars0 = [X] ; Vars0 = [X|Vars] ), 470 setarg(vars of bfs_tree, Handle, Vars0), % add it to the bfs tree 471 true. 472 473:- mode new_bfs_attrstruct(+,-). 474new_bfs_attrstruct(Handle, Attr) :- 475 hash_create(NodeInfoHashTable), 476 Attr = bfs with [ 477 type: real, 478 node_info:NodeInfoHashTable, 479 pcu: 0, 480 pcu_count: none, 481 pcd: 0, 482 pcd_count: none, 483 solver:Handle, 484 next:end 485 ]. 486 487% From a bfs_attr, searches for the attribute corresponding to that for the 488% first argument. Fails if none found. 489get_bfs_attr_for_handle(Handle, Attr0, Attr) :- 490 compound(Attr0), 491 get_bfs_attr_for_handle1(Handle, Attr0, Attr). 492 493get_bfs_attr_for_handle1(Handle, Attr0, Attr) :- 494 % no need to test for var(Attr0) in chain 495 Attr0 = bfs with [solver:Handle0,next:NextAttr], 496 (Handle0 == Handle -> 497 Attr0 = Attr 498 ; 499 get_bfs_attr_for_handle1(Handle, NextAttr, Attr) 500 ). 501 502bfs_get_node_info(Var, NodeId, Val, _Handle) :- 503 nonvar(Var), !, 504 Val = bfs_node_info with [ 505 id:NodeId, 506 lo:Var, 507 hi:Var, 508 val:Var, 509 rc:0 510 ]. 511bfs_get_node_info(Var{bfs:Attr0}, NodeId, Val, Handle) ?- 512 get_bfs_attr_for_handle(Handle, Attr0, Attr), 513 Attr = bfs with [ 514 type:Type, 515 node_info:Vals 516 ], 517 nonvar(NodeId), 518 ( hash_get(Vals, NodeId, Val) -> 519 % found a bfs_node_info struct for this node 520 true 521 ; 522 % no bfs_node_info struct for this node, 523 % implicitly has original bounds, 0 val and rc 524 Val = bfs_node_info with [ 525 id:NodeId, 526 lo:NLo, 527 hi:NHi, 528 val:0, 529 rc:0 530 ], 531 get_var_bounds(Var, Lo, Hi), 532 ( Type == integer -> 533 NLo is ceiling(Lo), 534 NHi is floor(Hi) 535 ; 536 NLo = Lo, 537 NHi = Hi 538 ) 539 ). 540 541update_node_info(Val, V) :- 542 Val = bfs_node_info with [ 543 lo:Lo, 544 hi:Hi, 545 val:T, 546 rc:RC 547 ], 548 V = bfs_node_info with [ 549 lo:L, 550 hi:H 551 ], 552 ( var(Lo) -> true 553 ; var(L) -> setarg(lo of bfs_node_info, V, Lo) 554 ; NL is max(Lo, L), setarg(lo of bfs_node_info, V, NL) ), 555 ( var(Hi) -> true 556 ; var(H) -> setarg(hi of bfs_node_info, V, Hi) 557 ; NH is min(Hi, H), setarg(hi of bfs_node_info, V, NH) ), 558 ( var(T) -> true ; setarg(val of bfs_node_info, V, T) ), 559 ( var(RC) -> true ; setarg(rc of bfs_node_info, V, RC) ). 560 561bfs_new_node_info(Var, Node, NodeInfo, Handle) :- 562 get_bfs_attr(Var, Handle, Attr), 563 Attr = bfs{type:T, node_info:NodeInfoHash}, 564 Node = bfs_node{id:Id, frac_vars:Vars}, 565 NodeInfo = bfs_node_info{id:Id, val:Val}, 566 ( ( nonvar(Val), T == integer, 567 Handle = bfs_tree with int_tolerance:IntTol, 568 abs(Val-round(Val)) > IntTol ) -> 569 setarg(frac_vars of bfs_node, Node, [Var:Val|Vars]) 570 ; 571 true 572 ), 573 ( hash_get(NodeInfoHash, Id, NodeInfo0) -> 574 update_node_info(NodeInfo, NodeInfo0) 575 ; 576 hash_add(NodeInfoHash, Id, NodeInfo) 577 ). 578 579% bfs_node_info/6 : for low-level handles 580bfs_node_info(Handle, Var, Lo, Hi, Val, RC) :- 581 ( var(Handle) -> 582 error(4, bfs_node_info(Handle, Var, Lo, Hi, Val, RC)) 583 ; Handle = bfs_tree with [] -> 584 Info = bfs_node_info with [lo:Lo, hi:Hi, val:Val, rc:RC], 585 bfs_node_info_body(Handle, Var, Info) 586 ; 587 % not a proper bfs handle 588 error(5, bfs_node_info(Handle, Var, Lo, Hi, Val, RC)) 589 ). 590 591% node_info/5 : for pools 592bfs_node_info1(Var, Lo, Hi, Val, RC, Pool) :- 593 get_pool_item(Pool, Handle), 594 ( Handle == 0 -> 595 printf(error, "Bfs instance has no tree set up in %w%n", 596 [Pool:node_info(Var, Lo, Hi, Val, RC)]), 597 abort 598 ; 599 Info = bfs_node_info with [lo:Lo, hi:Hi, val:Val, rc:RC], 600 bfs_node_info_body(Handle, Var, Info) 601 ). 602 603% bfs_node_info/3 : for low-level handles 604bfs_node_info(Handle, Var, Info) :- 605 ( var(Handle) -> 606 error(4, bfs_node_info(Handle, Var, Info)) 607 ; Handle = bfs_tree with [] -> 608 bfs_node_info_body(Handle, Var, Info) 609 ; 610 % not a proper bfs handle 611 error(5, bfs_node_info(Handle, Var, Info)) 612 ). 613 614% node_info/2 : for pools 615bfs_node_info1(Var, Info, Pool) :- 616 get_pool_item(Pool, Handle), 617 ( Handle == 0 -> 618 printf(error, "Bfs instance has no tree set up in %w%n", 619 [Pool:node_info(Var, Info)]), 620 abort 621 ; 622 bfs_node_info_body(Handle, Var, Info) 623 ). 624 625bfs_node_info_body(Handle, Var, Val) :- 626 ( bfs_next_node(Handle, SubTree), 627 n_trees:n_tree_get(data, SubTree, Node) -> 628 ( var(Val) -> 629 Node = bfs_node with id:Id, 630 bfs_get_node_info(Var, Id, Val, Handle) 631 ; 632 bfs_new_node_info(Var, Node, Val, Handle) 633 ) 634 ; 635 printf(error, "Bfs tree has no current node in %w%n", 636 [bfs_node_info_body(Handle, Var, Val)]), 637 abort 638 ). 639 640% bfs_var_get/4: for low-level handles 641bfs_var_get(Handle, Var, What, Val) :- 642 ( var(Handle) -> 643 error(4, bfs_var_get(Handle, Var, What, Val)) 644 ; var(What) -> 645 error(4, bfs_var_get(Handle, Var, What, Val)) 646 ; Handle = bfs_tree{} -> 647 bfs_var_get_body(Handle, Var, What, Val) 648 ; 649 error(5, bfs_var_get(Handle, Var, What, Val)) 650 ). 651 652% var_get/3: for pools 653bfs_var_get1(Var, What, Val, Pool) :- 654 ( var(What) -> 655 error(4, Pool:var_get(Var, What, Val)) 656 ; 657 get_pool_item(Pool, Handle), 658 ( Handle == 0 -> 659 printf(error, "Bfs instance has no tree set up in %w%n", 660 [Pool:var_get(Var, What, Val)]), 661 abort 662 ; 663 bfs_var_get_body(Handle, Var, What, Val) 664 ) 665 ). 666 667bfs_var_get_body(Handle, Var, node_val, Val) ?- !, 668 ( bfs_next_node(Handle, SubTree), 669 n_trees:n_tree_get(data, SubTree, bfs_node{id:Id}) -> 670 ( number(Var) -> 671 Val = Var 672 ; 673 bfs_get_node_info(Var, Id, bfs_node_info{val:Val}, 674 Handle) 675 ) 676 ; 677 printf(error, "Bfs tree has no current node in %w%n", 678 [bfs_var_get_body(Handle, Var, node_val, Val)]), 679 abort 680 ). 681bfs_var_get_body(Handle, Var, node_bounds, Val) ?- !, 682 ( bfs_next_node(Handle, SubTree), 683 n_trees:n_tree_get(data, SubTree, bfs_node{id:Id}) -> 684 ( number(Var) -> 685 Val = Var..Var 686 ; 687 bfs_get_node_info(Var, Id, bfs_node_info{lo:Lo,hi:Hi}, 688 Handle), 689 Val = Lo..Hi 690 ) 691 ; 692 printf(error, "Bfs tree has no current node in %w%n", 693 [bfs_var_get_body(Handle, Var, node_bounds, Val)]), 694 abort 695 ). 696bfs_var_get_body(Handle, Var, node_rc, Val) ?- !, 697 ( bfs_next_node(Handle, SubTree), 698 n_trees:n_tree_get(data, SubTree, bfs_node{id:Id}) -> 699 ( number(Var) -> Val = 0 700 ; bfs_get_node_info(Var, Id, bfs_node_info{rc:Val}, Handle) ) 701 ; 702 printf(error, "Bfs tree has no current node in %w%n", 703 [bfs_var_get_body(Handle, Var, node_rc, Val)]), 704 abort 705 ). 706bfs_var_get_body(Handle, Var, optimal_val, Val) ?- !, 707 ( number(Var) -> 708 Val = Var 709 ; 710 get_bfs_attr(Var, Handle, bfs{optimal_val:Val}) 711 ). 712bfs_var_get_body(Handle, Var, type, Val) ?- !, 713 ( integer(Var) -> 714 Val = integer 715 ; number(Var) -> 716 Val = real 717 ; 718 get_bfs_attr(Var, Handle, bfs{type:Val}) 719 ). 720bfs_var_get_body(Handle, Var, What, Val) :- 721 error(6, bfs_var_get_body(Handle, Var, What, Val)). 722 723bfs_var_set(_{bfs:Attr0}, optimal_val, Val, Handle) ?- !, 724 get_bfs_attr_for_handle(Handle, Attr0, Attr), 725 ( Attr = bfs with type: integer -> 726 Opt is fix(round(float(Val))) 727 ; 728 Opt = Val 729 ), 730 setarg(optimal_val of bfs, Attr, Opt). 731bfs_var_set(Var, What, Val, Handle) :- 732 error(6, bfs_var_set(Var, What, Val, Handle)). 733 734bfs_integers1(Ints, Pool) :- 735 get_pool_handle(Handle, Pool), 736 bfs_integers(Handle, Ints). 737 738bfs_integers(Handle, Ints) :- 739 ( var(Ints) -> 740 get_bfs_attr(Ints, Handle, Attr), 741 setarg(type of bfs, Attr, integer) 742 ; 743 ( 744 foreach(Var, Ints), 745 param(Handle) 746 do 747 get_bfs_attr(Var, Handle, Attr), 748 setarg(type of bfs, Attr, integer) 749 ) 750 ). 751 752% bfs_branch/2: for low-level handles 753bfs_branch(Handle, Branch) :- 754 ( var(Handle) -> 755 error(4, bfs_branch(Handle, Branch)) 756 ; Handle = bfs_tree{} -> 757 bfs_branch_body(Handle, [0, Branch]) 758 ; 759 error(5, bfs_branch(Handle, Branch)) 760 ). 761 762% bfs_branch/1: for pools 763bfs_branch1(Branch, Pool) :- 764 get_pool_item(Pool, Handle), 765 ( Handle == 0 -> 766 printf(error, "Bfs instance has no tree set up in %w%n", 767 [Pool:bfs_branch(Branch)]), 768 abort 769 ; 770 bfs_branch_body(Handle, [0, Branch]) 771 ). 772 773% bfs_branch/3: for low-level handles 774bfs_branch(Handle, Score, Branch) :- 775 ( var(Handle) -> 776 error(4, bfs_branch(Handle, Score, Branch)) 777 ; Handle = bfs_tree{} -> 778 bfs_branch_body(Handle, [Score, Branch]) 779 ; 780 error(5, bfs_branch(Handle, Score, Branch)) 781 ). 782 783% branch/2: for pools 784bfs_branch1(Score, Branch, Pool) :- 785 get_pool_item(Pool, Handle), 786 ( Handle == 0 -> 787 printf(error, "Bfs instance has no tree set up in %w%n", 788 [Pool:branch(Score, Branch)]), 789 abort 790 ; 791 bfs_branch_body(Handle, [Score, Branch]) 792 ). 793 794bfs_branch_body(bfs_tree{shelf:Shelf}, Branch) :- 795 shelf_get(Shelf, branches of bfs_shelf, Branches), 796 shelf_set(Shelf, branches of bfs_shelf, [Branch|Branches]). 797 798% bfs_global_cut/2: for low-level handles 799bfs_global_cut(Handle, GlobalCut) :- 800 ( var(Handle) -> 801 error(4, bfs_global_cut(Handle, GlobalCut)) 802 ; Handle = bfs_tree{} -> 803 bfs_global_cut_body(Handle, GlobalCut) 804 ; 805 error(5, bfs_global_cut(Handle, GlobalCut)) 806 ). 807 808% global_cut/1: for pools 809bfs_global_cut1(GlobalCut, Pool) :- 810 get_pool_item(Pool, Handle), 811 ( Handle == 0 -> 812 printf(error, "Bfs instance has no tree set up in %w%n", 813 [Pool:global_cut(GlobalCut)]), 814 abort 815 ; 816 bfs_global_cut_body(Handle, GlobalCut) 817 ). 818 819bfs_global_cut_body(bfs_tree{shelf:Shelf}, GlobalCut) :- 820 shelf_get(Shelf, global_cuts of bfs_shelf, GlobalCuts), 821 shelf_set(Shelf, global_cuts of bfs_shelf, [GlobalCut|GlobalCuts]). 822 823bfs_info_message(bfs_tree with info_messages:OnOff, String, Vars) :- 824 ( OnOff == on -> printf(String, Vars) ; true ). 825 826% bfs_statistics/1: for low-level handles 827bfs_statistics(Handle) :- 828 ( var(Handle) -> 829 error(4, bfs_statistics(Handle)) 830 ; Handle = bfs_tree{} -> 831 bfs_statistics_body(Handle) 832 ; 833 error(5, bfs_statistics(Handle)) 834 ). 835 836% /0: for pools 837bfs_statistics1(Pool) :- 838 get_pool_item(Pool, Handle), 839 ( Handle == 0 -> 840 printf(error, "Bfs instance has no tree set up in %w%n", 841 [Pool:statistics]), 842 abort 843 ; 844 bfs_statistics_body(Handle) 845 ). 846 847bfs_statistics_body(bfs_tree{next_node_no:NTotal, stats:Stats}) :- 848 Stats = stats{total_time:TTotal, 849 nodes_solved:NSolve, 850 solve_time:TSolve, 851 nodes_separated:NSep, 852 separate_time:TSep, 853 no_sols:NSol, 854 first_sol_time:TFirst, 855 opt_sol_time:TOpt 856 }, 857 printf("%n%nbfs statistics:%n%tTotal nodes:" 858 " %d%n%tTotal time: %w" 859 "%n%tNodes solved: %d%n%tNode solution time: %w" 860 "%n%tNodes separated: %d%n%tNode separation time: %w" 861 "%n%tSolutions found: %d%n%tFirst solution time: %w" 862 "%n%tOptimal solution time: %w%n%n", 863 [NTotal, TTotal, NSolve, TSolve, 864 NSep, TSep, NSol, TFirst, TOpt]). 865 866% bfs_node_cost/2: for low-level handles 867bfs_node_cost(Handle, Val) :- 868 ( var(Handle) -> 869 error(4, bfs_node_cost(Handle, Val)) 870 ; var(Val) -> 871 error(4, bfs_node_cost(Handle, Val)) 872 ; Handle = bfs_tree{} -> 873 bfs_node_cost_body(Handle, Val) 874 ; 875 error(5, bfs_node_cost(Handle, Val)) 876 ). 877 878% node_cost/1: for pools 879bfs_node_cost1(Val, Pool) :- 880 ( var(Val) -> 881 error(4, Pool:node_cost(Val)) 882 ; 883 get_pool_item(Pool, Handle), 884 ( Handle == 0 -> 885 printf(error, "Bfs instance has no tree set up in %w%n", 886 [Pool:node_cost(Val)]), 887 abort 888 ; 889 bfs_node_cost_body(Handle, Val) 890 ) 891 ). 892 893bfs_node_cost_body(Handle, NodeCost) :- 894 bfs_next_node(Handle, SubTree), 895 n_trees:n_tree_get(data, SubTree, Node), 896 setarg(objval of bfs_node, Node, NodeCost). 897 898% bfs_get/3: for low-level handles 899bfs_get(Handle, What, Val) :- 900 ( var(Handle) -> 901 error(4, bfs_get(Handle, What, Val)) 902 ; var(What) -> 903 error(4, bfs_get(Handle, What, Val)) 904 ; Handle = bfs_tree{} -> 905 bfs_get_body(Handle, What, Val) 906 ; 907 error(5, bfs_get(Handle, What, Val)) 908 ). 909 910% get/2: for pools 911bfs_get1(What, Val, Pool) :- 912 ( var(What) -> 913 error(4, Pool:get(What, Val)) 914 ; 915 get_pool_item(Pool, Handle), 916 ( Handle == 0 -> 917 printf(error, "Bfs instance has no tree set up in %w%n", 918 [Pool:get(What, Val)]), 919 abort 920 ; 921 bfs_get_body(Handle, What, Val) 922 ) 923 ). 924 925bfs_next_node(Handle, Node) :- 926 Handle = bfs_tree{ 927 root_node:Root, 928 best_bound:Bound, 929 node_select:Method, 930 integral_obj:IntObj 931 }, 932 ( Method == depth_first -> 933 n_trees:next(dfs, Root, Node0) 934 ; Method == two_phase -> 935 n_trees:next(dfs, Root, Node0) 936 ; Method == best_first -> 937 n_trees:next(bfs, Root, Node0) 938 ; Method == best_estimate -> 939 n_trees:next(bfs, Root, Node0) 940 ), 941 ( %n_trees:n_tree_get(data, Node0, bfs_node{parent_obj:ParentObj}), 942 %fathom_by_bounds(IntObj, ParentObj, Bound) -> 943 % n_trees:n_tree_fathom(Node0), 944 % bfs_next_node(Handle, Node) 945 %; 946 Node = Node0 947 ). 948 949bfs_get_body(Handle, frac_vars, Val) ?- !, 950 bfs_next_node(Handle, SubTree), 951 n_trees:n_tree_get(data, SubTree, bfs_node{frac_vars:Vars}), 952 ( foreach(Var:_, Vars), foreach(Var, Val) do true ). 953bfs_get_body(Handle, branches, Val) ?- !, 954 bfs_next_node(Handle, SubTree), 955 n_trees:n_tree_get(data, SubTree, bfs_node{branches:Val}). 956bfs_get_body(Handle, data, Val) ?- !, 957 Handle = bfs_tree{data:Val}. 958bfs_get_body(Handle, node_count, Val) ?- !, 959 Handle = bfs_tree{next_node_no:Val}. 960bfs_get_body(Handle, What, Val) :- 961 error(6, bfs_get_body(Handle, What, Val)). 962 963% bfs_set/3: for low-level handles 964bfs_set(Handle, What, Val) :- 965 ( var(Handle) -> 966 error(4, bfs_set(Handle, What, Val)) 967 ; var(What) -> 968 error(4, bfs_set(Handle, What, Val)) 969 ; var(Val) -> 970 error(4, bfs_set(Handle, What, Val)) 971 ; Handle = bfs_tree{} -> 972 bfs_set_body(Handle, What, Val) 973 ; 974 error(5, bfs_set(Handle, What, Val)) 975 ). 976 977% set/2: for pools 978bfs_set1(What, Val, Pool) :- 979 ( var(What) -> 980 error(4, Pool:set(What, Val)) 981 ; var(Val) -> 982 error(4, Pool:set(What, Val)) 983 ; 984 get_pool_item(Pool, Handle), 985 ( Handle == 0 -> 986 printf(error, "Bfs instance has no tree set up in %w%n", 987 [Pool:set(What, Val)]), 988 abort 989 ; 990 bfs_set_body(Handle, What, Val) 991 ) 992 ). 993 994bfs_set_body(Handle, feas_check, Val) ?- !, 995 functor(Val, Functor, Arity), 996 Handle = bfs_tree with module:Module, 997 current_predicate(Functor/Arity)@Module, 998 setarg(feas_check of bfs_tree, Handle, Val). 999bfs_set_body(Handle, data, Val) ?- !, 1000 setarg(data of bfs_tree, Handle, Val). 1001bfs_set_body(Handle, node_select, Val) ?- !, 1002 setarg(node_select of bfs_tree, Handle, Val). 1003bfs_set_body(Handle, alpha_min, Val) ?- !, 1004 setarg(alpha_min of bfs_tree, Handle, Val). 1005bfs_set_body(Handle, alpha_max, Val) ?- !, 1006 setarg(alpha_max of bfs_tree, Handle, Val). 1007bfs_set_body(Handle, beta_const, Val) ?- !, 1008 setarg(beta_const of bfs_tree, Handle, Val). 1009bfs_set_body(Handle, beta_pc, Val) ?- !, 1010 setarg(beta_pc of bfs_tree, Handle, Val). 1011bfs_set_body(Handle, beta_lb, Val) ?- !, 1012 setarg(beta_lb of bfs_tree, Handle, Val). 1013bfs_set_body(Handle, pc_init, Val) ?- !, 1014 setarg(pc_init of bfs_tree, Handle, Val). 1015bfs_set_body(Handle, pc_update, Val) ?- !, 1016 setarg(pc_update of bfs_tree, Handle, Val). 1017bfs_set_body(Handle, pc_ratio, Val) ?- !, 1018 setarg(pc_ratio of bfs_tree, Handle, Val). 1019bfs_set_body(Handle, lb_time, Val) ?- !, 1020 setarg(lb_time of bfs_tree, Handle, Val). 1021bfs_set_body(Handle, int_tolerance, Val) ?- !, 1022 setarg(int_tolerance of bfs_tree, Handle, Val). 1023bfs_set_body(Handle, info_messages, Val) ?- !, 1024 setarg(info_messages of bfs_tree, Handle, Val). 1025bfs_set_body(Handle, What, Val) :- 1026 error(6, bfs_set_body(Handle, What, Val)). 1027 1028 1029% bfs_solver_setup/3,4: for low-level handles 1030:- tool(bfs_solver_setup/3, bfs_solver_setup2/4). 1031 1032bfs_solver_setup2(Handle, Sense, Solver, Module) :- 1033 bfs_solver_setup(Handle, Sense, Solver, [], Module). 1034 1035:- tool(bfs_solver_setup/4, bfs_solver_setup/5). 1036 1037bfs_solver_setup(Handle, Sense, Solver, OptionList, Module) :- 1038 bfs_solver_setup_body(Handle, Sense, Solver, OptionList, _, Module). 1039 1040% solver_setup/2,3: for pools 1041:- tool(bfs_solver_setup1/3, bfs_solver_setup0/4). 1042 1043bfs_solver_setup0(Sense, Solver, Pool, Module) :- 1044 bfs_solver_setup0(Sense, Solver, [], Pool, Module). 1045 1046:- tool(bfs_solver_setup1/4, bfs_solver_setup0/5). 1047 1048bfs_solver_setup0(Sense, Solver, OptionList, Pool, Module) :- 1049 get_pool_handle(Handle, Pool), 1050 bfs_solver_setup_body(Handle, Sense, Solver, OptionList, Pool, Module). 1051 1052bfs_solver_setup_body(Handle, Sense, Solver, OptionList, Pool, Module) :- 1053 ( var(Solver) -> 1054 error(4, bfs_solver_setup(Sense, Solver, OptionList, Pool)) 1055 ; 1056 true 1057 ), 1058 ( var(Sense) -> 1059 error(4, bfs_solver_setup(Sense, Solver, OptionList, Pool)) 1060 ; Sense == min -> 1061 true 1062 ; Sense == max -> 1063 true 1064 ; error(6, bfs_solver_setup(Sense, Solver, OptionList, Pool)) 1065 ), 1066 % setup tree 1067 Handle = bfs_tree with [ 1068 module:Module, 1069 shelf:Shelf, 1070 sense:Sense, 1071 cost:CostVar, 1072 best_bound:1.0Inf, 1073 root_node:Root, 1074 next_node_no:1, 1075 pool:Pool 1076 ], 1077 set_var_bounds(CostVar, -1.0Inf, 1.0Inf), 1078 % create a shelf for storing info over failures 1079 shelf_create(bfs_shelf{branches:[],global_cuts:[],info:[]}, Shelf), 1080 % create a root node bfs_node struct 1081 RootNode = bfs_node with [ 1082 id:0, 1083 rank: Rank, 1084 parent_obj: -1.0Inf, 1085 branches:[] 1086 ], 1087 % create a n_tree for the search tree and place the bfs_node 1088 % struct in its data 1089 n_trees:n_tree((<), Root), 1090 n_trees:n_tree_set(data, Root, RootNode), 1091 ( atom(Solver), is_constraint_pool(Solver) -> 1092 get_pool_item(Solver, Item), 1093 % if the solver supplied is a constraint pool name we 1094 % have built-in node optimization and separation 1095 % predicates for eplex problems, otherwise 1096 % they must be user-supplied 1097 %( Item = prob with [vars:VarArr, objcoeffs:Expr] -> 1098 ( functor(Item, prob, _) -> 1099 Solver:eplex_get(vars, VarArr), 1100 Solver:eplex_get(objective, Objective), 1101 Objective =.. [Sense, Expr], 1102 Solve = bfs_minimize_eplex_node(Handle, Item), 1103 lp_set(Item, reduced_cost, yes), 1104 lp_set(Item, keep_basis, yes), 1105 RootNode = bfs_node with state:([],[]), 1106 DefaultSeparation = bfs_deg_est(Handle, eplex(Item)), 1107 %( bfs_integral_objective(Expr, VarArr, Handle) -> 1108 ( bfs_integral_objective(Handle, Expr) -> 1109 setarg(integral_obj of bfs_tree, Handle, yes) 1110 ; 1111 true 1112 ), 1113 % process option list and fill in default values 1114 process_options(OptionList, Handle, Item, Separation), 1115 fill_in_defaults(Handle, DefaultSeparation, Separation), 1116 % try to identify GUB constraints to improve branching 1117 gub_constraints(Item, Handle) 1118 ; 1119 concat_string([Pool, 1120 ": no built-in node optimization or" 1121 " separation predicates for pool ", 1122 Solver], Message), 1123 writeln(warning_output, Message), 1124 abort 1125 ) 1126 %; Solver = prob with [vars:VarArr, objcoeffs:Expr] -> 1127 ; functor(Solver, prob, _) -> 1128 lp_get(Solver, vars, VarArr), 1129 lp_get(Solver, objective, Objective), 1130 Objective =.. [Sense, Expr], 1131 Solve = bfs_minimize_eplex_node(Handle, Solver), 1132 lp_set(Solver, reduced_cost, yes), 1133 lp_set(Solver, keep_basis, yes), 1134 RootNode = bfs_node with state:([],[]), 1135 DefaultSeparation = bfs_deg_est(Handle, eplex(Solver)), 1136 %( bfs_integral_objective(Expr, VarArr, Handle) -> 1137 ( bfs_integral_objective(Handle, Expr) -> 1138 setarg(integral_obj of bfs_tree, Handle, yes) 1139 ; 1140 true 1141 ), 1142 % process option list and fill in default values 1143 process_options(OptionList, Handle, Solver, Separation), 1144 fill_in_defaults(Handle, DefaultSeparation, Separation), 1145 % try to identify GUB constraints to improve branching 1146 gub_constraints(Solver, Handle) 1147 ; 1148 Solve = Solver, 1149 % process option list and fill in default values 1150 process_options(OptionList, Handle, Separation), 1151 fill_in_defaults(Handle, DefaultSeparation, Separation) 1152 ), 1153 Handle = bfs_tree with node_select:NodeSelect, 1154 ( ( functor(Solve, bfs_minimize_eplex_node, _), 1155 lp_get(presolve, 1), 1156 lp_get(optimizer, xpress), 1157 (Separation = bfs_deg_est(_, _); Separation = bfs_strong(_, _)) ) -> 1158 % We disallow the use of XPRESS with estimate-based 1159 % methods on pre-solved problems because IF there is an 1160 % abort (probably hitting iteration limit before finding 1161 % a feasible basis) AND the external solver is XPRESS-MP 1162 % AND the problem was pre-solved, THEN the variable 1163 % column numbers get returned in the wrong order causing 1164 % incorrect solutions at future nodes 1165 Separation1 = bfs_fracvar(Handle), 1166 ( NodeSelect == best_estimate -> 1167 % have to change the node selection method also 1168 % since best_estimate requires some sort of 1169 % estimate-based spearation method 1170 setarg(node_select of bfs_tree, Handle, best_first), 1171 NewNS = best_first 1172 ; 1173 NewNS = NodeSelect 1174 ), 1175 bfs_info_message(Handle, "cannot use lower-bounding based" 1176 " estimate methods for variable/branch" 1177 " selection with pre-solved XPRESS problems," 1178 " parameters changed to%n%tseparation: fracvar" 1179 " %n%tnode_select: %w%n", [NewNS]) 1180 ; 1181 Separation1 = Separation 1182 ), 1183 Handle = bfs_tree with node_select:NodeSelect0, 1184 ( NodeSelect0 == best_first -> 1185 Rank = -1.0Inf 1186 ; NodeSelect0 == depth_first -> 1187 Rank = "" 1188 ; NodeSelect0 == best_estimate -> 1189 Rank = -1.0Inf 1190 ; NodeSelect0 == two_phase -> 1191 Rank = "" 1192 ; 1193 error(4, bfs_solver_setup(Solver, OptionList, Pool)) 1194 ), 1195 % make a suspension for the node processing 1196 % and insert it in the node_susp suspension list of Handle 1197 make_suspension(bfs_body(Handle, Solve, Separation1, Pool), 1198 0, Susp), 1199 enter_suspension_list(node_susp of bfs_tree, Handle, Susp). 1200 1201bfs_solver_cleanup(Pool) :- 1202 get_pool_handle(Handle, Pool), 1203 Handle = bfs_tree with node_susp:SuspList, 1204 ( foreach(Susp, SuspList) do kill_suspension(Susp) ). 1205 1206% bfs_solve/2: for low-level handles 1207bfs_solve(Handle, Obj) :- 1208 ( var(Handle) -> 1209 error(4, bfs_solve(Handle, Obj)) 1210 ; Handle = bfs_tree{} -> 1211 bfs_solve_body(Handle, Obj) 1212 ; 1213 error(5, bfs_solve(Handle, Obj)) 1214 ). 1215 1216% solve/1: for pools 1217bfs_solve1(Obj, Pool) :- 1218 get_pool_handle(Handle, Pool), 1219 bfs_solve_body(Handle, Obj). 1220 1221bfs_solve_body(Handle, Obj) :- 1222 cputime(StartTime), 1223 setarg(start_time of bfs_tree, Handle, StartTime), 1224 setarg(no_sols of bfs_tree, Handle, 0), 1225 Handle = bfs_tree with sense:Sense, 1226 ( Sense == min -> 1227 setarg(best_bound of bfs_tree, Handle, 1.0Inf) 1228 ; Sense == max -> 1229 setarg(best_bound of bfs_tree, Handle, -1.0Inf) 1230 ), 1231 schedule_suspensions(node_susp of bfs_tree, Handle), 1232 wake, 1233 cputime(EndTime), 1234 TotalTime is EndTime - StartTime, 1235 setarg(total_time of bfs_tree, Handle, TotalTime), 1236 % return the optimal solution value 1237 Handle = bfs_tree{node_select:NodeSelect, 1238 best_bound:Obj}, 1239 ( Sense == min -> 1240 Obj < 1.0Inf 1241 ; Sense == max -> 1242 Obj > -1.0Inf 1243 ), 1244 % replace the root node for later resolution 1245 ( NodeSelect == best_first -> 1246 Rank = -1.0Inf 1247 ; NodeSelect == depth_first -> 1248 Rank = "" 1249 ; NodeSelect == best_estimate -> 1250 Rank = -1.0Inf 1251 ; NodeSelect == two_phase -> 1252 Rank = "" 1253 ), 1254 RootNode = bfs_node with [ 1255 id:0, 1256 rank: Rank, 1257 parent_obj: -1.0Inf, 1258 branches:[] 1259 ], 1260 % create a n_tree for the search tree and place the bfs_node 1261 % struct in its data 1262 n_trees:n_tree((<), Root), 1263 n_trees:n_tree_set(data, Root, RootNode), 1264 setarg(root_node of bfs_tree, Handle, Root). 1265 1266gub_constraints(EplexHandle, Handle) :- 1267 % we need to find gub constraints in the problem and 1268 % identify suitable reference rows for them 1269 Handle = bfs_tree{int_tolerance:IntTol}, 1270 lp_get(EplexHandle, constraints_norm, NormCstrs), 1271 ( 1272 foreach(Type:[Const*One|VarTerms], NormCstrs), 1273 fromto(OtherCstrs, Out, In, []), 1274 fromto(GUBSets, GOut, GIn, []), 1275 param(IntTol, Handle) 1276 do 1277 ( Type == (>=) -> 1278 % not a GUB 1279 Out = [Type:[Const*One|VarTerms]|In], 1280 GOut = GIn 1281 ; gub_structure(VarTerms, GUBSet, Const, IntTol, Handle) -> 1282 % found a GUB constraint 1283 Out = In, 1284 GOut = [GUBSet|GIn] 1285 ; 1286 % not a GUB 1287 Out = [Type:[Const*One|VarTerms]|In], 1288 GOut = GIn 1289 ) 1290 ), 1291 ( 1292 foreach(GUBSet, GUBSets), 1293 fromto(GUBs, Out, In, []), 1294 param(OtherCstrs) 1295 do 1296 ( reference_row(OtherCstrs, GUBSet, Vars, RefTerms, PCStructs) -> 1297 % found a suitable reference row for this GUB 1298 % create a bfs_gub structure 1299 GUB = bfs_gub with [ 1300 vars:Vars, 1301 refs:RefTerms, 1302 pseudocosts:PCStructs 1303 ], 1304 Out = [GUB|In] 1305 ; 1306 % cannot find a suitable reference row for 1307 % this GUB 1308 Out = In 1309 ) 1310 ), 1311 ( GUBs == [] -> 1312 true 1313 ; 1314 GUBStruct =.. [[]|GUBs], 1315 setarg(gubs of bfs_tree, Handle, GUBStruct), 1316 Handle = bfs_tree{root_node:Root}, 1317 n_trees:n_tree_get(data, Root, RootNode), 1318 setarg(branches of bfs_node, RootNode, 1319 [lp_add(EplexHandle, [], [])]) 1320 ). 1321 1322process_options([], _, _, _) ?- !, true. 1323process_options([O|Os], Handle, EplexHandle, Separation) ?- !, 1324 process_option(O, Handle, EplexHandle, Separation), 1325 process_options(Os, Handle, EplexHandle, Separation). 1326process_options(_NonList, Handle, _, _) :- 1327 Handle = bfs_tree with pool:Pool, 1328 bfs_info_message(Handle, "%w : options not proper list." 1329 " Ignored.%n,", [Pool]). 1330 1331process_option(separation(S), Handle, Eplex, Separation) ?- !, 1332 process_separation(S, Handle, Eplex, Separation). 1333process_option(O, Handle, _, Separation) ?- !, 1334 process_option(O, Handle, Separation). 1335 1336process_separation(Val, Handle, Eplex, Separation) :- !, 1337 ( Val = deg_est -> Separation = bfs_deg_est(Handle, eplex(Eplex)) 1338 ; Val = fracvar -> Separation = bfs_fracvar(Handle) 1339 ; Val = strong -> Separation = bfs_strong(Handle, eplex(Eplex)) 1340 ; Val = enhanced -> Separation = bfs_enhanced(Handle, eplex(Eplex)) 1341 % this doesn't exist! 1342 %; Val = gub -> Separation = bfs_gub(Handle) 1343 ; Separation = Val ). 1344 1345process_options([], _, _) ?- !, true. 1346process_options([O|Os], Handle, Separation) ?- !, 1347 process_option(O, Handle, Separation), 1348 process_options(Os, Handle, Separation). 1349process_options(_NonList, Handle, _) :- 1350 Handle = bfs_tree with pool:Pool, 1351 bfs_info_message(Handle, "%w : options not proper list." 1352 " Ignored.%n,", [Pool]). 1353 1354process_option(separation(Separation), _Handle, Separation) :- !. 1355process_option(global_feasibility_check(Val), Handle, _) ?- !, 1356 bfs_set_body(Handle, feas_check, Val). 1357process_option(data(Val), Handle, _) ?- !, 1358 bfs_set_body(Handle, data, Val). 1359process_option(node_select(Val), Handle, _) ?- !, 1360 bfs_set_body(Handle, node_select, Val). 1361process_option(alpha(AlphaMin, AlphaMax), Handle, _) ?- !, 1362 bfs_set_body(Handle, alpha_min, AlphaMin), 1363 bfs_set_body(Handle, alpha_max, AlphaMax). 1364process_option(beta(BetaConst, BetaPC, BetaLB), Handle, _) ?- !, 1365 bfs_set_body(Handle, beta_const, BetaConst), 1366 bfs_set_body(Handle, beta_pc, BetaPC), 1367 bfs_set_body(Handle, beta_lb, BetaLB). 1368process_option(pseudo_cost(PCInit, PCUpdate, PCRatio), Handle, _) ?- !, 1369 bfs_set_body(Handle, pc_init, PCInit), 1370 bfs_set_body(Handle, pc_update, PCUpdate), 1371 ( var(PCRatio) -> true 1372 ; 0 < PCRatio, PCRatio < 1 -> bfs_set_body(Handle, pc_ratio, PCRatio) 1373 ; bfs_info_message(Handle, "Invalid pc_ratio (ignored): %w%n", [PCRatio]) ). 1374process_option(lower_bound(Val), Handle, _) ?- !, 1375 bfs_set_body(Handle, lb_time, Val). 1376process_option(int_tolerance(Val), Handle, _) ?- !, 1377 ( 0 =< Val, Val =< 0.5 -> bfs_set_body(Handle, int_tolerance, Val) 1378 ; bfs_info_message(Handle, "Invalid int_tolerance (ignored): %w%n", [Val]) ). 1379process_option(info_messages(Val), Handle, _) ?- !, 1380 bfs_set_body(Handle, info_messages, Val). 1381process_option(NoOpt, Handle, _) :- 1382 bfs_info_message(Handle, "Invalid option (ignored): %w%n", [NoOpt]). 1383 1384fill_in_defaults(Handle, DefaultSeparation, Separation) :- 1385 Handle = bfs_tree with [ 1386 data:Data, 1387 feas_check:FeasCheck, 1388 integral_obj:IntObj, 1389 int_tolerance:IntTol, 1390 vars:Vars, 1391 node_select:NodeSelect, 1392 pcd_count:0-0, 1393 pcu_count:0-0, 1394 alpha_min:AlphaMin, 1395 alpha_max:AlphaMax, 1396 beta_const:BetaConst, 1397 beta_pc:BetaPC, 1398 beta_lb:BetaLB, 1399 pc_init:PCInit, 1400 pc_update:PCUpdate, 1401 pc_ratio:PCRatio, 1402 lb_time:LB, 1403 total_time:0, 1404 no_sols:0, 1405 solve_time:0, 1406 separate_time:0, 1407 nodes_separated:0, 1408 nodes_solved:0, 1409 gubs:GUBs, 1410 info_messages:OnOff, 1411 pool:Pool 1412 ], 1413 ( var(Data) -> Data = 0 ; true ), 1414 ( var(FeasCheck) -> FeasCheck = true ; true ), 1415 ( var(IntObj) -> IntObj = no ; true ), 1416 ( var(IntTol) -> IntTol = 1e-05 ; true ), 1417 ( var(Vars) -> Vars = [] ; true ), 1418 ( var(Separation) -> 1419 ( var(DefaultSeparation) -> 1420 concat_string([Pool, 1421 ": no node separation method" 1422 " specified."], Message), 1423 writeln(warning_output, Message), 1424 abort 1425 ; 1426 Separation = DefaultSeparation 1427 ) 1428 ; 1429 true 1430 ), 1431 ( var(NodeSelect) -> NodeSelect = best_first ; true ), 1432 ( var(AlphaMin) -> AlphaMin = 2 ; true ), 1433 ( var(AlphaMax) -> AlphaMax = 1 ; true ), 1434 ( var(BetaConst) -> BetaConst = 0 ; true ), 1435 ( var(BetaPC) -> BetaPC = 1 ; true ), 1436 ( var(BetaLB) -> BetaLB = 1 ; true ), 1437 ( var(PCInit) -> PCInit = calculated ; true ), 1438 ( var(PCUpdate) -> PCUpdate = average ; true ), 1439 ( var(PCRatio) -> PCRatio = 0.05 ; true ), 1440 ( var(LB) -> LB = 1 ; true ), 1441 ( var(OnOff) -> OnOff = off ; true ), 1442 ( var(GUBs) -> GUBs = [] ; true ). 1443 1444bfs_integral_objective(Handle, Expr1+Expr2) :- 1445 bfs_integral_objective(Handle, Expr1), 1446 bfs_integral_objective(Handle, Expr2). 1447bfs_integral_objective(Handle, C*Var) :- 1448 integer(C), 1449 bfs_var_get_body(Handle, Var, type, integer). 1450bfs_integral_objective(Handle, Var) :- 1451 bfs_var_get_body(Handle, Var, type, integer). 1452 1453bfs_integral_objective([], _, _). 1454bfs_integral_objective([J:C|Rest], VarArr, Handle) :- 1455 integer(C), 1456 J1 is J + 1, 1457 arg(J1, VarArr, Var), 1458 bfs_var_get_body(Handle, Var, type, integer), 1459 bfs_integral_objective(Rest, VarArr, Handle). 1460 1461:- demon bfs_body/4. 1462:- set_flag(bfs_body/4, priority, 8). 1463:- set_flag(bfs_body/4, run_priority, 8). 1464bfs_body(Handle, Solve, Separation, Pool) :- 1465 Handle = bfs_tree{module:Module, 1466 solve_time:TSolve, 1467 nodes_solved:NSolve, 1468 shelf:Shelf 1469 }, 1470 ( bfs_next_node(Handle, SubTree), 1471 n_trees:n_tree_get(data, SubTree, Node) -> 1472 Node = bfs_node{id:NodeId}, 1473 bfs_info_message(Handle, "%w:Processing node %w%n%tsolving relaxation ... ", 1474 [Pool, NodeId]), 1475 cputime(T1), 1476 % call node minimization goal 1477 setarg(frac_vars of bfs_node, Node, []), 1478 ( call(Solve)@Module -> 1479 Node = bfs_node{objval:ObjVal}, 1480 bfs_info_message(Handle, " done, z = %w%n", [ObjVal]) 1481 ; 1482 setarg(objval of bfs_node, Node, 1.0Inf), 1483 bfs_info_message(Handle, " infeasible%n", []) 1484 ), 1485 % do some statistics collection 1486 cputime(T2), 1487 TSolve1 is TSolve + T2 - T1, 1488 setarg(solve_time of bfs_tree, Handle, TSolve1), 1489 NSolve1 is NSolve + 1, 1490 setarg(nodes_solved of bfs_tree, Handle, NSolve1), 1491 bfs_info_message(Handle, "%tAdding global cuts ... ", []), 1492 % note to AE: should really check all nodes in the tree 1493 % to ensure they are feasible with these new global cuts 1494 shelf_get(Shelf, global_cuts of bfs_shelf, GlobalCuts), 1495 ( 1496 foreach(GlobalCut, GlobalCuts), 1497 param(Module) 1498 do 1499 call(GlobalCut)@Module 1500 ), 1501 shelf_set(Shelf, global_cuts of bfs_shelf, []), 1502 bfs_info_message(Handle, " done%n", []), 1503 bfs_info_message(Handle, "%tseparating ... ", []), 1504 cputime(T3), 1505 Handle = bfs_tree{feas_check:FeasCheck, 1506 shelf:Shelf, 1507 sense:Sense, 1508 vars:Vars, 1509 integral_obj:IntObj, 1510 cost:Cost, 1511 best_bound:BestBound, 1512 node_select:NodeSelect, 1513 next_node_no:Id1, 1514 separate_time:TSep, 1515 nodes_separated:NSep, 1516 start_time:TStart, 1517 no_sols:NSols 1518 }, 1519 Node = bfs_node{id:NodeId, 1520 objval:NodeCost, 1521 rank:Rank, 1522 frac_vars:FracVars, 1523 state:State, 1524 branches:Branches 1525 }, 1526 ( NodeCost == 1.0Inf -> 1527 % fathomed by infeasibility 1528 bfs_info_message(Handle, "%tfathomed by infeasibility%n", []), 1529 n_trees:n_tree_fathom(SubTree) 1530 ; fathom_by_bounds(IntObj, NodeCost, BestBound) -> 1531 % fathomed by bounds 1532 bfs_info_message(Handle, "%tfathomed by bounds%n", []), 1533 n_trees:n_tree_fathom(SubTree) 1534 ; global_feasible(Node, FeasCheck, Module) -> 1535 % globally feasible solution, 1536 % optimal within tolerance bound 1537 bfs_info_message(Handle, "%tglobally feasible%n", []), 1538 % do some statistics collection 1539 cputime(T), 1540 TSolution is T - TStart, 1541 setarg(opt_sol_time of bfs_tree, Handle, TSolution), 1542 % update incumbent and prune nodes 1543 set_var_bounds(Cost, -1.0Inf, NodeCost), 1544 ( IntObj == yes -> 1545 NewBound is fix(NodeCost), 1546 PruneBound is NodeCost - 1 1547 ; 1548 NewBound = NodeCost, 1549 PruneBound = NodeCost 1550 ), 1551 setarg(best_bound of bfs_tree, Handle, NewBound), 1552 n_trees:n_tree_fathom(SubTree), 1553 Handle = bfs_tree with vars:Vars, 1554 ( 1555 foreach(Var, Vars), 1556 param(NodeId, Handle) 1557 do 1558 ( var(Var) -> 1559 bfs_get_node_info(Var, NodeId, 1560 bfs_node_info with val:Val, Handle), 1561 bfs_var_set(Var, optimal_val, Val, Handle) 1562 ; 1563 true 1564 ) 1565 ), 1566 ( NSols = 0 -> 1567 % first feasible solution 1568 % if we are using a two-phase strategy 1569 % we should switch 1570 ( NodeSelect == two_phase -> 1571 setarg(node_select of bfs_tree, Handle, best_first) 1572 ; 1573 true 1574 ), 1575 setarg(first_sol_time of bfs_tree, Handle, TSolution), 1576 setarg(no_sols of bfs_tree, Handle, 1) 1577 ; 1578 % new optimal solution 1579 NSols1 is NSols + 1, 1580 setarg(no_sols of bfs_tree, Handle, NSols1) 1581 ) 1582 ; 1583 ( 1584 foreach(Var, Vars), 1585 foreach(Lo..Hi, LoHis), 1586 param(NodeId, Handle) 1587 do 1588 bfs_get_node_info(Var, NodeId, 1589 bfs_node_info with [lo:Lo, hi:Hi], 1590 Handle) 1591 ), 1592 shelf_set(Shelf, branches of bfs_shelf, []), 1593 call(Separation)@Module, 1594 shelf_get(Shelf, branches of bfs_shelf, ScoredBranches), 1595 ( 1596 foreach([Score, Branch], ScoredBranches), 1597 foreach(Diff-NewNode, ChildRanks), 1598 count(Id, Id1, Id2), 1599 param(NodeSelect, Sense, NodeCost, Rank, State, Branches, 1600 FracVars, Vars, LoHis, Handle, SubTree) 1601 do 1602 NewNode = bfs_node with [ 1603 id:Id, 1604 rank:ChildRank, 1605 parent_obj:NodeCost, 1606 state:State, 1607 branches:ChildBranches 1608 ], 1609 ( 1610 foreach(Var, Vars), 1611 foreach(Lo..Hi, LoHis), 1612 param(NewNode, Handle) 1613 do 1614 bfs_new_node_info(Var, NewNode, 1615 bfs_node_info with [lo:Lo, hi:Hi], 1616 Handle) 1617 ), 1618 ( number(Score) -> 1619 Diff = Score 1620 ; 1621 Score = [_PCIdxs, PCStruct, Diff, UpDown], 1622 setarg(pc_update of bfs_node, NewNode, 1623 [PCStruct, Diff, UpDown]) 1624 ), 1625 ( Branch = NewNode -> 1626 true 1627 ; Branch = bounds(Idx, Lo..Hi) -> 1628 % it was a variable bound update 1629 FracVarArr =.. [[]|FracVars], 1630 arg(Idx, FracVarArr, Var:_Sol), 1631 PCVars = [Var], 1632 bfs_new_node_info(Var, NewNode, 1633 bfs_node_info with [lo:Lo, hi:Hi], 1634 Handle), 1635 ChildBranches = Branches 1636 ; Branch = gub_bound(GN, NVars, Rel, Rhs), 1637 Branches = [lp_add(EplexHandle, Cstrs, [])] -> 1638 % it was a gub and we have an eplex 1639 % handle to add to 1640 Handle = bfs_tree{gubs:GUBs}, 1641 arg(GN, GUBs, GUB), 1642 GUB = bfs_gub{vars:GUBVars}, 1643 ( 1644 for(_, 1, NVars), 1645 foreach(Term, Terms), 1646 fromto(GUBVars, [Term|Rest], Rest, _) 1647 do 1648 true 1649 ), 1650 term_variables(Terms, PCVars), 1651 Expr =.. [Rel, sum(PCVars), Rhs], 1652 normalise_cstrs([Expr], [Cstr], []), 1653 ChildBranches = [lp_add(EplexHandle, [Cstr|Cstrs], [])] 1654 ; 1655 % it was some user defined branch 1656 ChildBranches = [Branch|Branches] 1657 ), 1658 ( NodeSelect == best_first -> 1659 % using a static node selection method 1660 % so order among children by fractional change 1661 % the rank given to a node here is the bound 1662 % on the node objective obtained from the parent 1663 % and the frac change Diff from parent to node, 1664 % standard ordering ensures we choose among them 1665 % in Bound then Frac order 1666 ( Rank = PCost-_ -> true ; Rank = PCost ), 1667 ( Sense = min -> 1668 NodeCost0 is max(PCost, NodeCost), 1669 ChildRank = NodeCost0-Diff 1670 ; % Sense = max 1671 NodeCost0 is min(PCost, NodeCost), 1672 Diff1 is 1 - Diff, 1673 ChildRank = NodeCost0-Diff1 1674 ), 1675 n_trees:n_tree_expand(SubTree, 1676 ChildRank, 1677 ChildNode), 1678 n_trees:n_tree_set(data, ChildNode, NewNode) 1679 ; NodeSelect == depth_first -> 1680 true 1681 ; NodeSelect == two_phase -> 1682 true 1683 ; NodeSelect == best_estimate -> 1684 % using an estimate based selection method, so the order 1685 % of the nodes is taken care of automatically 1686 % Note to AE: this may not give the correct 1687 % estimates with gub branching? 1688 ( Sense = min -> 1689 Order = (@<), 1690 Functor = (+) 1691 ; % Sense = max 1692 Order = (@>), 1693 Functor = (-) 1694 ), 1695 PCStruct = pseudocost with [pcd:PCD, pcu:PCU], 1696 ( 1697 foreach(Var:Val, FracVars), 1698 fromto(NodeCost, In, Out, CommonRank), 1699 param(Handle, PCVars, Functor) 1700 do 1701 ( var_member(Var, PCVars) -> 1702 Out = In 1703 ; 1704 get_bfs_attr(Var, Handle, 1705 bfs with [pcd:D, pcu: U]), 1706 Delta is min(D*(Val-floor(Val)), 1707 U*(ceiling(Val)-Val)), 1708 Goal =.. [Functor, In, Delta, Out], 1709 call(Goal) 1710 ) 1711 ), 1712 ( UpDown == d -> Delta is PCD * Diff 1713 ; Delta is PCU * Diff ), % UpDown == u 1714 Goal =.. [Functor, CommonRank, Delta, ChildRank], 1715 call(Goal), 1716 n_trees:n_tree_expand(SubTree, 1717 ChildRank, 1718 ChildNode), 1719 n_trees:n_tree_set(data, ChildNode, NewNode) 1720 ; 1721 printf(error, "unknown node_select type: %w%n", 1722 [NodeSelect]), 1723 abort 1724 ) 1725 ), 1726 ( ( NodeSelect == depth_first ; NodeSelect == two_phase ) -> 1727 sort(1, =<, ChildRanks, Sorted), 1728 ( 1729 foreach(_-NewNode, Sorted), 1730 count(N, 0, _), 1731 param(SubTree, Pool, Rank) 1732 do 1733 ( N =< 255 -> 1734 char_code(C, N), 1735 concat_string([Rank, C], ChildRank), 1736 NewNode = bfs_node with rank:ChildRank, 1737 n_trees:n_tree_expand(SubTree, 1738 ChildRank, 1739 ChildNode), 1740 n_trees:n_tree_set(data, ChildNode, NewNode) 1741 ; 1742 printf(error, "%w: maximum number" 1743 " of children at a node" 1744 " exceeded (256)%n", 1745 [Pool]), 1746 abort 1747 ) 1748 ) 1749 ; true ), 1750 NextId is Id2 + 1, 1751 cputime(T4), 1752 TSep1 is TSep + T4 - T3, 1753 setarg(separate_time of bfs_tree, Handle, TSep1), 1754 NSep1 is NSep + 1, 1755 setarg(nodes_separated of bfs_tree, Handle, NSep1), 1756 setarg(next_node_no of bfs_tree, Handle, NextId), 1757 bfs_info_message(Handle, "done, nodes %d..%d created%n", 1758 [Id1, Id2]) 1759 ), 1760 schedule_suspensions(node_susp of bfs_tree, Handle), 1761 wake 1762 ; 1763 true 1764 ). 1765 1766var_member(Var, [H|T]) :- 1767 ( Var == H -> true ; var_member(Var, T) ). 1768 1769% bfs_minimize_eplex_node/2: for low-level handles 1770bfs_minimize_eplex_node(Handle, EplexHandle) :- 1771 ( var(Handle) -> 1772 error(4, bfs_minimize_eplex_node(Handle, EplexHandle)) 1773 ; Handle = bfs_tree{} -> 1774 bfs_minimize_eplex_node_body(Handle, EplexHandle) 1775 ; 1776 error(5, bfs_minimize_eplex_node(Handle, EplexHandle)) 1777 ). 1778 1779% minimize_eplex_node/1: for pools 1780bfs_minimize_eplex_node1(EplexHandle, Pool) :- 1781 get_pool_handle(Handle, Pool), 1782 bfs_minimize_eplex_node_body(Handle, EplexHandle). 1783 1784bfs_minimize_eplex_node_body(Handle, EplexHandle) :- 1785 Handle = bfs_tree with [ 1786 cost:Cost, 1787 shelf:Shelf, 1788 pc_ratio:PCRatio, 1789 no_sols:NSols 1790 ], 1791 bfs_next_node(Handle, SubTree), 1792 n_trees:n_tree_get(data, SubTree, Node), 1793 Node = bfs_node with [ 1794 id:NodeId, 1795 state:(CBasis, RBasis), 1796 branches:Branches 1797 ], 1798 ( NodeId = 0 -> 1799 % root node, no need to block/fail 1800 lp_solve(EplexHandle, Obj), 1801 lp_get(EplexHandle, vars, VarArr), 1802 VarArr =.. [_|Vars], 1803 ( 1804 foreach(Var, Vars), 1805 param(EplexHandle, Handle) 1806 do 1807 lp_var_get(EplexHandle, Var, solution, Val), 1808 lp_var_get(EplexHandle, Var, reduced_cost, RC), 1809 get_var_bounds(Var, Lo, Hi), 1810 Info = bfs_node_info with [ 1811 lo:Lo, 1812 hi:Hi, 1813 val:Val, 1814 rc:RC 1815 ], 1816 bfs_node_info_body(Handle, Var, Info) 1817 ), 1818 lp_get(EplexHandle, simplex_iterations, Its), 1819 Node = bfs_node with frac_vars:FracVars, 1820 length(FracVars, NFrac), 1821 PCIt is fix(ceiling((PCRatio*Its)/(2*NFrac))), 1822 setarg(pc_ratio of bfs_tree, Handle, PCIt), 1823 lp_get(EplexHandle, cbasis, NewCBasis), 1824 lp_get(EplexHandle, rbasis, NewRBasis), 1825 setarg(state of bfs_node, Node, (NewCBasis, NewRBasis)) 1826 ; 1827 shelf_get(Shelf, info of bfs_shelf, OldInfo), 1828 \+ \+ ( lp_set(EplexHandle, cbasis, CBasis), 1829 lp_set(EplexHandle, rbasis, RBasis), 1830 lp_get(EplexHandle, vars, VarArr), 1831 VarArr =.. [_|Vars], 1832 call_priority(( 1833 foreach(Var, Vars), 1834 param(Handle, EplexHandle) 1835 do 1836 bfs_node_info_body(Handle, Var, Info), 1837 Info = bfs_node_info with [lo:Lo, hi:Hi], 1838 set_var_bounds(Var, Lo, Hi), 1839 lp_var_set_bounds(EplexHandle, Var, Lo, Hi) 1840 ), 2), 1841 ( foreach(Branch, Branches) do call(Branch) ), 1842 lp_solve(EplexHandle, Obj), 1843 ( NSols > 0 -> 1844 reduced_cost_pruning(EplexHandle, Cost) 1845 ; 1846 true 1847 ), 1848 ( 1849 foreach(Var, Vars), 1850 foreach(Info, Vals), 1851 param(EplexHandle) 1852 do 1853 lp_var_get(EplexHandle, Var, solution, Val), 1854 lp_var_get(EplexHandle, Var, reduced_cost, RC), 1855 get_var_bounds(Var, Lo, Hi), 1856 Info = bfs_node_info with [ 1857 lo:Lo, 1858 hi:Hi, 1859 val:Val, 1860 rc:RC 1861 ] 1862 ), 1863 lp_get(EplexHandle, cbasis, NewCBasis), 1864 lp_get(EplexHandle, rbasis, NewRBasis), 1865 shelf_set(Shelf, info of bfs_shelf, [Obj, Vals, (NewCBasis, NewRBasis)]) 1866 ), 1867 lp_get(EplexHandle, vars, VarArr), 1868 VarArr =.. [_|Vars], 1869 shelf_get(Shelf, info of bfs_shelf, [Obj, Vals, NewState]), 1870 shelf_set(Shelf, info of bfs_shelf, OldInfo), 1871 ( 1872 foreach(Var, Vars), 1873 foreach(Info, Vals), 1874 param(Handle) 1875 do 1876 bfs_node_info_body(Handle, Var, Info) 1877 ), 1878 setarg(state of bfs_node, Node, NewState) 1879 ), 1880 setarg(objval of bfs_node, Node, Obj). 1881 1882% bfs_update_pseudocosts/1: for low-level handles 1883bfs_update_pseudocosts(Handle) :- 1884 ( var(Handle) -> 1885 error(4, bfs_update_pseudocosts(Handle)) 1886 ; Handle = bfs_tree{} -> 1887 bfs_update_pseudocosts_body(Handle) 1888 ; 1889 error(5, bfs_update_pseudocosts(Handle)) 1890 ). 1891 1892% update_pseudocosts/0: for pools 1893bfs_update_pseudocosts1(Pool) :- 1894 get_pool_item(Pool, Handle), 1895 ( Handle == 0 -> 1896 printf(error, "Bfs instance has no tree set up in %w%n", 1897 [Pool:update_pseudocosts]), 1898 abort 1899 ; 1900 bfs_update_pseudocosts_body(Handle) 1901 ). 1902 1903bfs_update_pseudocosts_body(Handle) :- 1904 Handle = bfs_tree{ 1905 pc_update:PCUpdate, 1906 pcd_count:PCDCount-PCDTotal, 1907 pcu_count:PCUCount-PCUTotal 1908 }, 1909 bfs_next_node(Handle, SubTree), 1910 n_trees:n_tree_get(data, SubTree, Node), 1911 Node = bfs_node{ 1912 id:Id, 1913 objval:Obj, 1914 parent_obj:ObjP, 1915 pc_update:[PCStruct, Frac, Direction] 1916 }, 1917 ( Id == 0 -> 1918 true 1919 ; 1920 PseudoCost is (Obj - ObjP)/Frac, 1921 % update pseudocosts 1922 PCStruct = pseudocost{ 1923 pcd:Pcd, 1924 pcd_count:PcdTerm, 1925 pcu:Pcu, 1926 pcu_count:PcuTerm 1927 }, 1928 ( Direction == u -> 1929 % update the global pcu counters 1930 % for pcu initialisation 1931 NewPCUCount is PCUCount + 1, 1932 NewPCUTotal is PCUTotal + PseudoCost, 1933 NewPCUAverage is NewPCUTotal/NewPCUCount, 1934 setarg(pcu_average of bfs_tree, Handle, 1935 NewPCUAverage), 1936 setarg(pcu_count of bfs_tree, Handle, 1937 NewPCUCount-NewPCUTotal), 1938 % update the pcu counters involved in the branch 1939 ( PcuTerm = 0-Pcu -> 1940 NewPcuCount = 1, 1941 NewPcuTotal = PseudoCost, 1942 NewPcu = PseudoCost 1943 ; 1944 PcuTerm = PcuCount-PcuTotal, 1945 NewPcuCount is PcuCount + 1, 1946 NewPcuTotal is PcuTotal + PseudoCost, 1947 ( PCUpdate = first -> 1948 NewPcu = Pcu 1949 ; PCUpdate = last -> 1950 NewPcu = PseudoCost 1951 ; % PCUpdate = average 1952 NewPcu is NewPcuTotal/NewPcuCount 1953 ) 1954 ), 1955 setarg(pcu_count of pseudocost, PCStruct, 1956 NewPcuCount-NewPcuTotal), 1957 setarg(pcu of pseudocost, PCStruct, NewPcu) 1958 ; Direction == d -> 1959 % update the global pcd counters 1960 % for pcd initialisation 1961 NewPCDCount is PCDCount + 1, 1962 NewPCDTotal is PCDTotal + PseudoCost, 1963 NewPCDAverage is NewPCDTotal/NewPCDCount, 1964 setarg(pcd_average of bfs_tree, Handle, 1965 NewPCDAverage), 1966 setarg(pcd_count of bfs_tree, Handle, 1967 NewPCDCount-NewPCDTotal), 1968 % update the pcd counters involved in the branch 1969 ( PcdTerm = 0-Pcd -> 1970 NewPcdCount = 1, 1971 NewPcdTotal = PseudoCost, 1972 NewPcd = PseudoCost 1973 ; 1974 PcdTerm = PcdCount-PcdTotal, 1975 NewPcdCount is PcdCount + 1, 1976 NewPcdTotal is PcdTotal + PseudoCost, 1977 ( PCUpdate = first -> 1978 NewPcd = Pcd 1979 ; PCUpdate = last -> 1980 NewPcd = PseudoCost 1981 ; % PCUpdate = average 1982 NewPcd is NewPcdTotal/NewPcdCount 1983 ) 1984 ), 1985 setarg(pcd_count of pseudocost, PCStruct, 1986 NewPcdCount-NewPcdTotal), 1987 setarg(pcd of pseudocost, PCStruct, NewPcd) 1988 ) 1989 ). 1990 1991fathom_by_bounds(IntObj, Obj, Bound) :- 1992 ( IntObj == yes -> 1993 ceiling(Obj) > Bound 1994 ; 1995 Obj > Bound 1996 ). 1997 1998global_feasible(bfs_node with frac_vars:[], FeasCheck, Module) :- 1999 call(FeasCheck)@Module. 2000 2001depth_first(Ranks, Base) :- 2002 sort(1, >=, Ranks, Sorted), 2003 ( 2004 foreach(_-Rank, Sorted), 2005 count(N, 1, _), 2006 param(Base) 2007 do 2008 concat_string([Base, N], Rank) 2009 ). 2010 2011gub_structure([], [], _Handle). 2012gub_structure([Val*Var|Rest], [Var|Terms], Handle) :- 2013 Val =:= 1, 2014 bfs_var_get_body(Handle, Var, type, integer), 2015 gub_structure(Rest, Terms, Handle). 2016 2017gub_structure([], [], Val, IntTol, _Handle) :- 2018 abs(Val + 1) =< IntTol. 2019gub_structure([Val*Var|Rest], Terms, Sum, IntTol, Handle) :- 2020 ( (Val =:= 1, bfs_var_get_body(Handle, Var, type, integer)) -> 2021 Terms = [Var|Terms0], 2022 Sum0 = Sum 2023 ; 2024 Terms = Terms0, 2025 get_var_bounds(Var, Lo, Hi), 2026 Sum0 is Sum + min(Val*Lo, Val*Hi) 2027 ), 2028 gub_structure(Rest, Terms0, Sum0, IntTol, Handle). 2029 2030reference_row([_Type:[_Const*_One|Terms]|Cstrs], GUBSet, 2031 Vars, RefTerms, PCStructs) :- 2032 ( reference_row1(GUBSet, Terms, RefTerms0) -> 2033 % Note to AE: should we commit to just the first 2034 % possible reference 2035 % row we find or collect them all as generators for 2036 % branching constraints? Probably that would then be too 2037 % expensive to check them all each time, but it might 2038 % create better branches 2039 sort(RefTerms0, RefTerms), 2040 ( 2041 foreach(_Coeff*Var, RefTerms), 2042 foreach(1*Var, Vars), 2043 foreach(pseudocost with [pcd_count:none, 2044 pcu_count:none], PCList) 2045 do 2046 true 2047 ), 2048 PCStructs =.. [[]|PCList] 2049 ; 2050 reference_row(Cstrs, GUBSet, Vars, RefTerms, PCStructs) 2051 ). 2052 2053reference_row1([], _Terms, []). 2054reference_row1([Var|GUBSet], Terms, [RefTerm|RefTerms]) :- 2055 reference_row(Var, Terms, RefTerm, Terms0), 2056 reference_row1(GUBSet, Terms0, RefTerms). 2057 2058reference_row(Var, [Val0*Var0|Terms], RefTerm, Terms0) :- 2059 ( Var == Var0 -> 2060 RefTerm= Val0*Var0, 2061 Terms0 = Terms 2062 ; 2063 Terms0 = [Val0*Var0|Terms1], 2064 reference_row(Var, Terms, RefTerm, Terms1) 2065 ). 2066 2067branchpoint([Coeff:VarCount:VarSum|BranchPoints], RefTotal, NVars, Diff) :- 2068 ( Coeff > RefTotal -> 2069 % this branch set includes vars with coeff above the 2070 % suggested ref val 2071 branchpoint(BranchPoints, RefTotal, NVars, Diff) 2072 ; 2073 % maximal branch set with no coeffs above the suggested 2074 % ref val 2075 NVars = VarCount, 2076 Diff = VarSum 2077 ). 2078 2079% bfs_deg_est/2: for low-level handles 2080bfs_deg_est(Handle, Node) :- 2081 ( var(Handle) -> 2082 error(4, bfs_deg_est(Handle, Node)) 2083 ; Handle = bfs_tree{} -> 2084 bfs_deg_est_body(Handle, Node) 2085 ; 2086 error(5, bfs_deg_est(Handle, Node)) 2087 ). 2088 2089% deg_est/1: for pools 2090bfs_deg_est1(Node, Pool) :- 2091 get_pool_item(Pool, Handle), 2092 ( Handle == 0 -> 2093 printf(error, "Bfs instance has no tree set up in %w%n", 2094 [Pool:deg_est(Node)]), 2095 abort 2096 ; 2097 bfs_deg_est_body(Handle, Node) 2098 ). 2099 2100% Note to AE: try to get rid of the eplex handle form this call 2101bfs_deg_est_body(Handle, eplex(EplexHandle)) :- 2102 Handle = bfs_tree{shelf:Shelf, 2103 gubs:GUBs 2104 }, 2105 bfs_next_node(Handle, SubTree), 2106 n_trees:n_tree_get(data, SubTree, Node), 2107 % check the shelf is empty just in case 2108 shelf_get(Shelf, branches of bfs_shelf, []), 2109 Node = bfs_node with id:NodeId, 2110 % update pseudocosts for this node 2111 ( NodeId > 0 -> 2112 bfs_update_pseudocosts_body(Handle) 2113 ; 2114 true 2115 ), 2116 % find the var to branch on 2117 shelf_get(Shelf, info of bfs_shelf, OldInfo), 2118 bfs_deg_est(Handle, eplex(EplexHandle), Result, PseudoCosts), 2119 shelf_set(Shelf, info of bfs_shelf, OldInfo), 2120 ( Result = g(GN, NVars, Down) -> 2121 % initialize any GUB pseudocosts 2122 ( 2123 foreacharg(bfs_gub{pseudocosts:PCStructs}, GUBs), 2124 foreach(PseudoCost, PseudoCosts) 2125 do 2126 ( PseudoCost == not_stored -> 2127 true 2128 ; 2129 PseudoCost = BP-[PCD, PCU], 2130 arg(BP, PCStructs, PCStruct), 2131 setarg(pcd_count of pseudocost, PCStruct, 0-PCD), 2132 setarg(pcd of pseudocost, PCStruct, PCD), 2133 setarg(pcu_count of pseudocost, PCStruct, 0-PCU), 2134 setarg(pcu of pseudocost, PCStruct, PCU) 2135 ) 2136 ), 2137 arg(GN, GUBs, GUB), 2138 GUB = bfs_gub{pseudocosts:PCStructs}, 2139 arg(NVars, PCStructs, PCStruct), 2140 Up is 1 - Down, 2141 % store the branches 2142 shelf_set(Shelf, branches of bfs_shelf, 2143 [ 2144 [[g(GN, NVars), PCStruct, Down, d], % score 2145 gub_bound(GN, NVars, =<, 0)], % branch 2146 [[g(GN, NVars), PCStruct, Up, u], % score 2147 gub_bound(GN, NVars, >=, 1)] % branch 2148 ]) 2149 ; 2150 Result = v(Idx), 2151 Node = bfs_node with frac_vars:Vars, 2152 % initialize any variable pseudocosts 2153 ( 2154 foreach(Var:_, Vars), 2155 foreach(PseudoCost, PseudoCosts), 2156 param(Handle) 2157 do 2158 ( PseudoCost == not_stored -> 2159 true 2160 ; 2161 PseudoCost = [PCD, PCU], 2162 get_bfs_attr(Var, Handle, Attr), 2163 setarg(pcd_count of bfs, Attr, 0-PCD), 2164 setarg(pcd of bfs, Attr, PCD), 2165 setarg(pcu_count of bfs, Attr, 0-PCU), 2166 setarg(pcu of bfs, Attr, PCU) 2167 ) 2168 ), 2169 VarArr =.. [[]|Vars], 2170 arg(Idx, VarArr, Var:Val), 2171 Lo is ceiling(Val), 2172 Up is Lo - Val, 2173 Hi is floor(Val), 2174 Down is Val - Hi, 2175 get_bfs_attr(Var, Handle, bfs with pseudocost:PCStruct), 2176 % store the branches 2177 shelf_set(Shelf, branches of bfs_shelf, 2178 [ 2179 [[v(Idx), PCStruct, Down, d], 2180 bounds(Idx, -1.0Inf..Hi)], 2181 [[v(Idx), PCStruct, Up, u], 2182 bounds(Idx, Lo..1.0Inf)] 2183 ]) 2184 ). 2185 2186bfs_deg_est(Handle, NodeType, _, _) :- 2187 % branching on best estimate 2188 bfs_impose_node_state_body(NodeType, Handle), 2189 Handle = bfs_tree{int_tolerance:IntTol, 2190 gubs:GUBs, 2191 shelf:Shelf, 2192 alpha_min:AlphaMin, 2193 alpha_max:AlphaMax, 2194 beta_const:BetaConst, 2195 beta_pc:BetaPC, 2196 beta_lb:BetaLB, 2197 pc_init:PCInit, 2198 pc_ratio:PCIt, 2199 lb_time:LBIt 2200 }, 2201 bfs_next_node(Handle, SubTree), 2202 n_trees:n_tree_get(data, SubTree, Node), 2203 Node = bfs_node{id:NodeId, 2204 objval:NodeCost, 2205 frac_vars:Vars 2206 }, 2207 ( ( PCInit == calculated, PCIt >= LBIt ) -> 2208 PCOverLB = true 2209 ; 2210 PCOverLB = fail 2211 ), 2212 ( 2213 foreacharg(GUB, GUBs), 2214 foreach(PseudoCost, GPseudoCosts), 2215 count(GN, 1, _), 2216 fromto(_, In, Out, Result), 2217 fromto(_, ScoreIn, ScoreOut, _), 2218 param(Handle, NodeType, IntTol, NodeId, NodeCost, 2219 AlphaMin, AlphaMax, 2220 BetaConst, BetaPC, BetaLB, PCOverLB) 2221 do 2222 GUB = bfs_gub{vars:Vars, 2223 refs:Refs, 2224 pseudocosts:PCStructs 2225 }, 2226 ( 2227 foreach(Coeff*Var, Refs), 2228 count(NVars, 1, _), 2229 fromto([], BPIn, [Coeff:NVars:VTOut|BPIn], BranchPoints), 2230 fromto(0, VTIn, VTOut, _), 2231 fromto(0, RTIn, RTOut, RefTotal), 2232 fromto(0, FIn, FOut, Frac), 2233 param(Handle, IntTol, NodeId) 2234 do 2235 bfs_get_node_info(Var, NodeId, 2236 bfs_node_info with val:Val, Handle), 2237 VTOut is VTIn + Val, 2238 RTOut is RTIn + Coeff*Val, 2239 ( abs(min(Val-floor(Val),ceiling(Val)-Val)) =< IntTol -> 2240 FOut = FIn 2241 ; 2242 FOut is FIn + 1 2243 ) 2244 ), 2245 % if there are less than Limit fractional vars in the GUB it 2246 % is likely better to choose a good single var to branch 2247 % on, so we ignore this GUB 2248 % Note to AE: should not be hardwired Limit 2249 Limit = 2, 2250 ( Frac =< Limit -> 2251 PseudoCost = not_stored, 2252 Out = In, 2253 ScoreOut = ScoreIn 2254 ; 2255 % find the branchpoint for the GUB, and calculate score 2256 branchpoint(BranchPoints, RefTotal, NVars, Sum), 2257 ( BetaPC =:= 0 -> 2258 % only lower bounds in estimate 2259 PCD = 0, 2260 PCU = 0, 2261 PseudoCost = not_stored 2262 ; 2263 % otherwise get pseudocosts 2264 get_gub_pseudocosts(Handle, NodeType, 2265 NodeCost, GUB, NVars, Sum, 2266 PCD, PCU, Initializing), 2267 ( call(Initializing) -> 2268 PseudoCost = NVars-[PCD, PCU] 2269 ; 2270 PseudoCost = not_stored 2271 ) 2272 ), 2273 ( BetaLB =:= 0 -> 2274 % only pseudocosts in estimate 2275 LD = 0, 2276 LU = 0 2277 ; 2278 ( call(PCOverLB), 2279 arg(NVars, PCStructs, 2280 pseudocost with [pcd_count:0-LD, 2281 pcu_count:0-LU]) ) -> 2282 % if pseudocosts have just been calculated and are 2283 % stronger, use them as lower bounds 2284 true 2285 ; 2286 % otherwise get lower bounds 2287 ( 2288 for(_, 1, NVars), 2289 foreach(Term, Terms), 2290 fromto(Vars, [Term|Rest], Rest, _) 2291 do 2292 true 2293 ), 2294 get_gub_lowerbounds(Handle, NodeType, 2295 NodeCost, Terms, 2296 LD, LU) 2297 ), 2298 DownScore is BetaConst + (BetaPC * PCD * Sum) + 2299 (BetaLB * LD), 2300 UpScore is BetaConst + (BetaPC * PCU * (1-Sum)) + 2301 (BetaLB * LU), 2302 Score is AlphaMin * min(DownScore, UpScore) + 2303 AlphaMax * max(DownScore, UpScore), 2304 ( (nonvar(ScoreIn), Score =< ScoreIn) -> 2305 ScoreOut = ScoreIn, 2306 Out = In 2307 ; 2308 ScoreOut = Score, 2309 Out = g(GN, NVars, Sum) 2310 ) 2311 ) 2312 2313 ), 2314 ( nonvar(Result) -> 2315 PseudoCosts = GPseudoCosts 2316 ; 2317 % there were no GUBs with enough frac vars to be worth 2318 % branching on, choose a single var using deg_est 2319 ( 2320 foreach(Var:Val, Vars), 2321 count(I, 1, _), 2322 fromto(_, ScoreIn, ScoreOut, _), 2323 fromto(_, In, Out, Result), 2324 foreach(PseudoCost, PseudoCosts), 2325 param(Handle, NodeType, NodeCost, 2326 AlphaMin, AlphaMax, 2327 BetaConst, BetaPC, BetaLB, PCOverLB) 2328 do 2329 Up is ceiling(Val) - Val, 2330 Down is Val - floor(Val), 2331 ( BetaPC =:= 0 -> 2332 % only lower bounds in estimate 2333 PCD = 0, 2334 PCU = 0, 2335 PseudoCost = not_stored 2336 ; 2337 % otherwise get pseudocosts 2338 get_pseudocosts(Handle, NodeType, 2339 NodeCost, Var, Val, 2340 PCD, PCU, Initializing), 2341 ( call(Initializing) -> 2342 PseudoCost = [PCD, PCU] 2343 ; 2344 PseudoCost = not_stored 2345 ) 2346 ), 2347 ( BetaLB =:= 0 -> 2348 % only pseudocosts in estimate 2349 LD = 0, 2350 LU = 0 2351 ; 2352 ( call(PCOverLB), 2353 get_bfs_attr(Var, Handle, 2354 bfs with [pcd_count:0-LD, 2355 pcu_count:0-LU]) ) -> 2356 % if pseudocosts have just been calculated and are 2357 % stronger, use them as lower bounds 2358 true 2359 ; 2360 % otherwise get lower bounds 2361 get_lowerbounds(Handle, NodeType, 2362 NodeCost, Var, Val, 2363 LD, LU) 2364 ), 2365 DownScore is BetaConst + (BetaPC * PCD * Down) + 2366 (BetaLB * LD), 2367 UpScore is BetaConst + (BetaPC * PCU * Up) + 2368 (BetaLB * LU), 2369 Score is AlphaMin * min(DownScore, UpScore) + 2370 AlphaMax * max(DownScore, UpScore), 2371 ( (nonvar(ScoreIn), Score =< ScoreIn) -> 2372 ScoreOut = ScoreIn, 2373 Out = In 2374 ; 2375 ScoreOut = Score, 2376 Out = v(I) 2377 ) 2378 ) 2379 ), 2380 shelf_set(Shelf, info of bfs_shelf, Result:PseudoCosts), 2381 fail. 2382bfs_deg_est(bfs_tree{shelf:Shelf}, _, Result, PseudoCosts) :- 2383 shelf_get(Shelf, info of bfs_shelf, Result:PseudoCosts). 2384 2385% bfs_fracvar/1: for low-level handles 2386bfs_fracvar(Handle) :- 2387 ( var(Handle) -> 2388 error(4, bfs_fracvar(Handle)) 2389 ; Handle = bfs_tree{} -> 2390 bfs_fracvar_body(Handle) 2391 ; 2392 error(5, bfs_fracvar(Handle)) 2393 ). 2394 2395% fracvar/0: for pools 2396bfs_fracvar1(Pool) :- 2397 get_pool_item(Pool, Handle), 2398 ( Handle == 0 -> 2399 printf(error, "Bfs instance has no tree set up in %w%n", 2400 [Pool:fracvar]), 2401 abort 2402 ; 2403 bfs_fracvar_body(Handle) 2404 ). 2405 2406bfs_fracvar_body(Handle) :- 2407 % branching on gub if available or most fractional var 2408 Handle = bfs_tree{int_tolerance:IntTol, 2409 shelf:Shelf, 2410 gubs:GUBs 2411 }, 2412 bfs_next_node(Handle, SubTree), 2413 n_trees:n_tree_get(data, SubTree, Node), 2414 Node = bfs_node{id:NodeId, 2415 frac_vars:Vars 2416 }, 2417 % check the shelf is empty just in case 2418 shelf_get(Shelf, branches of bfs_shelf, []), 2419 ( 2420 foreacharg(GUB, GUBs), 2421 count(GN, 1, _), 2422 fromto(_, In, Out, Result), 2423 fromto(IntTol, ScoreIn, ScoreOut, _), 2424 param(Handle, IntTol, NodeId) 2425 do 2426 GUB = bfs_gub{refs:Refs}, 2427 ( 2428 foreach(Coeff*Var, Refs), 2429 count(NVars, 1, _), 2430 fromto([], BPIn, [Coeff:NVars:VTOut|BPIn], BranchPoints), 2431 fromto(0, VTIn, VTOut, _), 2432 fromto(0, RTIn, RTOut, RefTotal), 2433 fromto(0, FIn, FOut, Frac), 2434 param(Handle, IntTol, NodeId) 2435 do 2436 bfs_get_node_info(Var, NodeId, 2437 bfs_node_info{val:Val}, Handle), 2438 VTOut is VTIn + Val, 2439 RTOut is RTIn + Coeff*Val, 2440 ( abs(min(Val-floor(Val),ceiling(Val)-Val)) =< IntTol -> 2441 FOut = FIn 2442 ; 2443 FOut is FIn + 1 2444 ) 2445 ), 2446 % if there are less than Limit fractional vars in the GUB it 2447 % is likely better to choose a good single var to branch 2448 % on, so we ignore this GUB 2449 % Note to AE: should not be hardwired Limit 2450 Limit = 2, 2451 ( Frac =< Limit -> 2452 Out = In, 2453 ScoreOut = ScoreIn 2454 ; 2455 % find the branchpoint for the GUB, if the sum is 2456 % more fractional than the current choice, use it 2457 branchpoint(BranchPoints, RefTotal, NVars, Sum), 2458 Score is min(Sum, (1 - Sum)), 2459 ( Score =< ScoreIn -> 2460 ScoreOut = ScoreIn, 2461 Out = In 2462 ; 2463 ScoreOut = Score, 2464 Out = GN:NVars:Sum 2465 ) 2466 ) 2467 ), 2468 ( nonvar(Result) -> 2469 Result = GN:NVars:Down, 2470 Up is 1 - Down, 2471 % store the branches 2472 shelf_set(Shelf, branches of bfs_shelf, 2473 [ 2474 [Down, % score 2475 gub_bound(GN, NVars, =<, 0)], % branch 2476 [Up, % score 2477 gub_bound(GN, NVars, >=, 1)] % branch 2478 ]) 2479 ; 2480 % there were no GUBs with enough frac vars to be worth 2481 % branching on, choose a single var 2482 ( 2483 foreach(_Var:Val, Vars), 2484 count(I, 1, _), 2485 fromto(IntTol, DiffIn, DiffOut, _), 2486 fromto(_, In, Out, Idx:V) 2487 do 2488 Diff is abs(round(Val) - Val), 2489 ( Diff > DiffIn -> 2490 DiffOut = Diff, 2491 Out = I:Val 2492 ; 2493 DiffOut = DiffIn, 2494 Out = In 2495 ) 2496 ), 2497 Lo is ceiling(V), 2498 Up is Lo - V, 2499 Hi is floor(V), 2500 Down is V - Hi, 2501 % store the branches 2502 shelf_set(Shelf, branches of bfs_shelf, 2503 [ 2504 [Down, 2505 bounds(Idx, -1.0Inf..Hi)], 2506 [Up, 2507 bounds(Idx, Lo..1.0Inf)] 2508 ]) 2509 ). 2510 2511% bfs_enhanced/2: for low-level handles 2512bfs_enhanced(Handle, Node) :- 2513 ( var(Handle) -> 2514 error(4, bfs_enhanced(Handle, Node)) 2515 ; Handle = bfs_tree{} -> 2516 bfs_enhanced_body(Handle, Node) 2517 ; 2518 error(5, bfs_enhanced(Handle, Node)) 2519 ). 2520 2521% enhanced/1: for pools 2522bfs_enhanced1(Node, Pool) :- 2523 get_pool_item(Pool, Handle), 2524 ( Handle == 0 -> 2525 printf(error, "Bfs instance has no tree set up in %w%n", 2526 [Pool:enhanced(Node)]), 2527 abort 2528 ; 2529 bfs_enhanced_body(Handle, Node) 2530 ). 2531 2532bfs_enhanced_body(Handle, eplex(EplexHandle)) :- 2533 Handle = bfs_tree{int_tolerance:IntTol, 2534 shelf:Shelf, 2535 gubs:GUBs 2536 }, 2537 bfs_next_node(Handle, SubTree), 2538 n_trees:n_tree_get(data, SubTree, Node), 2539 Node = bfs_node{id:NodeId, 2540 frac_vars:Vars 2541 }, 2542 % check the shelf is empty just in case 2543 shelf_get(Shelf, branches of bfs_shelf, []), 2544 ( 2545 foreacharg(GUB, GUBs), 2546 count(GN, 1, _), 2547 fromto(_, In, Out, Result), 2548 fromto(IntTol, ScoreIn, ScoreOut, _), 2549 param(Handle, IntTol, NodeId) 2550 do 2551 GUB = bfs_gub{refs:Refs}, 2552 ( 2553 foreach(Coeff*Var, Refs), 2554 count(NVars, 1, _), 2555 fromto([], BPIn, [Coeff:NVars:VTOut|BPIn], BranchPoints), 2556 fromto(0, VTIn, VTOut, _), 2557 fromto(0, RTIn, RTOut, RefTotal), 2558 fromto(0, FIn, FOut, Frac), 2559 param(Handle, IntTol, NodeId) 2560 do 2561 bfs_get_node_info(Var, NodeId, 2562 bfs_node_info{val:Val}, Handle), 2563 VTOut is VTIn + Val, 2564 RTOut is RTIn + Coeff*Val, 2565 ( abs(min(Val-floor(Val),ceiling(Val)-Val)) =< IntTol -> 2566 FOut = FIn 2567 ; 2568 FOut is FIn + 1 2569 ) 2570 ), 2571 % if there are less than Limit fractional vars in the GUB it 2572 % is likely better to choose a good single var to branch 2573 % on, so we ignore this GUB 2574 Limit = 2, 2575 ( Frac =< Limit -> 2576 Out = In, 2577 ScoreOut = ScoreIn 2578 ; 2579 % find the branchpoint for the GUB, if the sum is 2580 % more fractional than the current choice, use it 2581 branchpoint(BranchPoints, RefTotal, NVars, Sum), 2582 Score is min(Sum, (1 - Sum)), 2583 ( Score =< ScoreIn -> 2584 ScoreOut = ScoreIn, 2585 Out = In 2586 ; 2587 ScoreOut = Score, 2588 Out = GN:NVars:Sum 2589 ) 2590 ) 2591 ), 2592 ( nonvar(Result) -> 2593 Result = GN:NVars:Down, 2594 Up is 1 - Down, 2595 % store the branches 2596 shelf_set(Shelf, branches of bfs_shelf, 2597 [ 2598 [Down, % score 2599 gub_bound(GN, NVars, =<, 0)], % branch 2600 [Up, % score 2601 gub_bound(GN, NVars, >=, 1)] % branch 2602 ]) 2603 ; 2604 % there were no GUBs with enough frac vars to be worth 2605 % branching on, choose a single var 2606 ( 2607 foreach(Var:Val, Vars), 2608 foreach(Frac-Val-Var, FracVars), 2609 fromto(0.0, LIn, LOut, L), 2610 fromto(1.0, UIn, UOut, U) 2611 do 2612 Frac is Val - floor(Val), 2613 ( Frac < 0.5 -> 2614 LOut is max(Frac, LIn), 2615 UOut = UIn 2616 ; Frac > 0.5 -> 2617 LOut = LIn, 2618 UOut is min(Frac, UIn) 2619 ; 2620 LOut = 0.5, 2621 UOut = 0.5 2622 ) 2623 ), 2624 LBound is 0.8 * L, 2625 UBound is 0.2 + 0.8 * U, 2626 ( 2627 foreach(FracPart-Val-Var, FracVars), 2628 count(I, 1, _), 2629 fromto(-1.0Inf, ScoreIn, ScoreOut, _), 2630 fromto(_, In, Out, Idx:V), 2631 param(EplexHandle, LBound, UBound) 2632 do 2633 ( (FracPart >= LBound, FracPart =< UBound) -> 2634 lp_get(EplexHandle, objective, Objective), 2635 Objective =.. [_MinMax, Expr], 2636 ( bfs_objective_coeff(Expr, Var, Score) -> 2637 %EplexHandle = prob with objcoeffs:ObjCoeffs, 2638 %lp_var_occurrence(Var, EplexHandle, J), 2639 %( member(J:Score, ObjCoeffs) -> 2640 true 2641 ; 2642 Score = 0 2643 ), 2644 ( Score =< ScoreIn -> 2645 ScoreOut = ScoreIn, 2646 Out = In 2647 ; 2648 ScoreOut = Score, 2649 Out = I:Val 2650 ) 2651 ; 2652 ScoreOut = ScoreIn, 2653 Out = In 2654 ) 2655 ), 2656 Lo is ceiling(V), 2657 Up is Lo - V, 2658 Hi is floor(V), 2659 Down is V - Hi, 2660 % store the branches 2661 shelf_set(Shelf, branches of bfs_shelf, 2662 [ 2663 [Down, 2664 bounds(Idx, -1.0Inf..Hi)], 2665 [Up, 2666 bounds(Idx, Lo..1.0Inf)] 2667 ]) 2668 ). 2669 2670% bfs_strong/2: for low-level handles 2671bfs_strong(Handle, Node) :- 2672 ( var(Handle) -> 2673 error(4, bfs_strong(Handle, Node)) 2674 ; Handle = bfs_tree{} -> 2675 bfs_strong_body(Handle, Node) 2676 ; 2677 error(5, bfs_strong(Handle, Node)) 2678 ). 2679 2680% strong/1: for pools 2681bfs_strong1(Node, Pool) :- 2682 get_pool_item(Pool, Handle), 2683 ( Handle == 0 -> 2684 printf(error, "Bfs instance has no tree set up in %w%n", 2685 [Pool:strong(Node)]), 2686 abort 2687 ; 2688 bfs_strong_body(Handle, Node) 2689 ). 2690 2691% Note to AE: try to get rid of the eplex handle form this call 2692bfs_strong_body(Handle, eplex(EplexHandle)) :- 2693 Handle = bfs_tree{shelf:Shelf}, 2694 shelf_get(Shelf, info of bfs_shelf, OldInfo), 2695 bfs_strong(Handle, eplex(EplexHandle), Result), 2696 shelf_set(Shelf, info of bfs_shelf, OldInfo), 2697 % check the shelf is empty just in case 2698 shelf_get(Shelf, branches of bfs_shelf, []), 2699 ( Result = g(GN, NVars, Down) -> 2700 Up is 1 - Down, 2701 % store the branches 2702 shelf_set(Shelf, branches of bfs_shelf, 2703 [ 2704 [Down, % score 2705 gub_bound(GN, NVars, =<, 0)], % branch 2706 [Up, % score 2707 gub_bound(GN, NVars, >=, 1)] % branch 2708 ]) 2709 ; 2710 Result = v(Idx), 2711 bfs_next_node(Handle, SubTree), 2712 n_trees:n_tree_get(data, SubTree, bfs_node{frac_vars:Vars}), 2713 VarArr =.. [[]|Vars], 2714 arg(Idx, VarArr, _Var:Val), 2715 Lo is ceiling(Val), 2716 Up is Lo - Val, 2717 Hi is floor(Val), 2718 Down is Val - Hi, 2719 % store the branches 2720 shelf_set(Shelf, branches of bfs_shelf, 2721 [ 2722 [Down, 2723 bounds(Idx, -1.0Inf..Hi)], 2724 [Up, 2725 bounds(Idx, Lo..1.0Inf)] 2726 ]) 2727 ). 2728 2729bfs_strong(Handle, NodeType, _) :- 2730 bfs_impose_node_state_body(NodeType, Handle), 2731 Handle = bfs_tree{int_tolerance:IntTol, 2732 gubs:GUBs, 2733 shelf:Shelf, 2734 alpha_min:AlphaMin, 2735 alpha_max:AlphaMax 2736 }, 2737 bfs_next_node(Handle, SubTree), 2738 n_trees:n_tree_get(data, SubTree, Node), 2739 Node = bfs_node{id:NodeId, 2740 objval:NodeCost, 2741 frac_vars:Vars 2742 }, 2743 ( 2744 foreacharg(GUB, GUBs), 2745 count(GN, 1, _), 2746 fromto(_, In, Out, Result), 2747 fromto(_, ScoreIn, ScoreOut, _), 2748 param(Handle, NodeType, IntTol, NodeId, NodeCost, 2749 AlphaMin, AlphaMax) 2750 do 2751 GUB = bfs_gub{vars:Vars, 2752 refs:Refs 2753 }, 2754 ( 2755 foreach(Coeff*Var, Refs), 2756 count(NVars, 1, _), 2757 fromto([], BPIn, [Coeff:NVars:VTOut|BPIn], BranchPoints), 2758 fromto(0, VTIn, VTOut, _), 2759 fromto(0, RTIn, RTOut, RefTotal), 2760 fromto(0, FIn, FOut, Frac), 2761 param(Handle, IntTol, NodeId) 2762 do 2763 bfs_get_node_info(Var, NodeId, 2764 bfs_node_info{val:Val}, Handle), 2765 VTOut is VTIn + Val, 2766 RTOut is RTIn + Coeff*Val, 2767 ( abs(min(Val-floor(Val),ceiling(Val)-Val)) =< IntTol -> 2768 FOut = FIn 2769 ; 2770 FOut is FIn + 1 2771 ) 2772 ), 2773 % if there are less than Limit fractional vars in the GUB it 2774 % is likely better to choose a good single var to branch 2775 % on, so we ignore this GUB 2776 % Note to AE: should not be hardwired Limit 2777 Limit = 2, 2778 ( Frac =< Limit -> 2779 Out = In, 2780 ScoreOut = ScoreIn 2781 ; 2782 % find the branchpoint for the GUB, if the sum is 2783 % more fractional than the current choice, use it 2784 branchpoint(BranchPoints, RefTotal, NVars, Sum), 2785 ( 2786 for(_, 1, NVars), 2787 foreach(Term, Terms), 2788 fromto(Vars, [Term|Rest], Rest, _) 2789 do 2790 true 2791 ), 2792 get_gub_lowerbounds(Handle, NodeType, 2793 NodeCost, Terms, 2794 DownScore, UpScore), 2795 Score is AlphaMin * min(DownScore, UpScore) + 2796 AlphaMax * max(DownScore, UpScore), 2797 ( (nonvar(ScoreIn), Score =< ScoreIn) -> 2798 ScoreOut = ScoreIn, 2799 Out = In 2800 ; 2801 ScoreOut = Score, 2802 Out = g(GN, NVars, Sum) 2803 ) 2804 ) 2805 2806 ), 2807 ( nonvar(Result) -> 2808 true 2809 ; 2810 % there were no GUBs with enough frac vars to be worth 2811 % branching on, choose a single var 2812 ( 2813 foreach(Var:Val, Vars), 2814 count(I, 1, _), 2815 foreach(Frac-I-Val-Var, FracVars), 2816 fromto(0.0, LIn, LOut, L), 2817 fromto(1.0, UIn, UOut, U) 2818 do 2819 Frac is Val - floor(Val), 2820 ( Frac < 0.5 -> 2821 LOut is max(Frac, LIn), 2822 UOut = UIn 2823 ; Frac > 0.5 -> 2824 LOut = LIn, 2825 UOut is min(Frac, UIn) 2826 ; 2827 LOut = 0.5, 2828 UOut = 0.5 2829 ) 2830 ), 2831 LBound is 0.8 * L, 2832 UBound is 0.2 + 0.8 * U, 2833 ( 2834 foreach(FracPart-Idx-Val-Var, FracVars), 2835 fromto(_, ScoreIn, ScoreOut, _), 2836 fromto(_, In, Out, Result), 2837 param(Handle, NodeType, NodeCost, 2838 AlphaMin, AlphaMax, LBound, UBound) 2839 do 2840 ( (FracPart >= LBound, FracPart =< UBound) -> 2841 get_lowerbounds(Handle, NodeType, 2842 NodeCost, Var, Val, 2843 DownScore, UpScore), 2844 Score is AlphaMin * min(DownScore, UpScore) + 2845 AlphaMax * max(DownScore, UpScore), 2846 ( (nonvar(ScoreIn), Score =< ScoreIn) -> 2847 ScoreOut = ScoreIn, 2848 Out = In 2849 ; 2850 ScoreOut = Score, 2851 Out = v(Idx) 2852 ) 2853 ; 2854 ScoreOut = ScoreIn, 2855 Out = In 2856 ) 2857 ) 2858 ), 2859 shelf_set(Shelf, info of bfs_shelf, Result), 2860 fail. 2861bfs_strong(bfs_tree with shelf:Shelf, _, Result) :- 2862 shelf_get(Shelf, info of bfs_shelf, Result). 2863 2864% bfs_impose_node_state/2 : for low-level handles 2865bfs_impose_node_state(NodeType, Handle) :- 2866 ( var(Handle) -> 2867 error(4, bfs_impose_node_state(NodeType, Handle)) 2868 ; Handle = bfs_tree with [] -> 2869 bfs_impose_node_state_body(NodeType, Handle) 2870 ; 2871 % not a proper bfs handle 2872 error(5, bfs_impose_node_state(NodeType, Handle)) 2873 ). 2874 2875% impose_node_state/1 : for pools 2876bfs_impose_node_state1(NodeType, Pool) :- 2877 get_pool_item(Pool, Handle), 2878 ( Handle == 0 -> 2879 printf(error, "Bfs instance has no tree set up in %w%n", 2880 [Pool:impose_node_state(NodeType)]), 2881 abort 2882 ; 2883 bfs_impose_node_state_body(NodeType, Handle) 2884 ). 2885 2886bfs_impose_node_state_body(NodeType, Handle) :- 2887 Handle = bfs_tree{vars:Vars}, 2888 bfs_next_node(Handle, SubTree), 2889 n_trees:n_tree_get(data, SubTree, Node), 2890 Node = bfs_node with [ 2891 id:NodeId, 2892 state:(CBasis, RBasis), 2893 branches:Branches 2894 ], 2895 % apply branching decisions & propagate 2896 % call them all as atomic op to limit wakings 2897 % since we will be doing this often 2898 call_priority(( 2899 foreach(Var, Vars), 2900 param(NodeId, Handle) 2901 do 2902 bfs_get_node_info(Var, NodeId, 2903 bfs_node_info with [lo:Lo, hi:Hi], 2904 Handle), 2905 set_var_bounds(Var, Lo, Hi) 2906 ), 2), 2907 call_priority(( 2908 foreach(Branch, Branches) 2909 do 2910 call(Branch) 2911 ), 2), 2912 ( NodeType = eplex(EplexHandle) -> 2913 lp_set(EplexHandle, cbasis, CBasis), 2914 lp_set(EplexHandle, rbasis, RBasis) 2915 ; 2916 true 2917 ). 2918 2919get_gub_pseudocosts(Handle, NodeType, NodeCost, GUB, BranchPoint, Sum, 2920 PseudoCostDown, PseudoCostUp, Initializing) :- 2921 Handle = bfs_tree{pcd_average:PcDown, 2922 pcu_average:PcUp, 2923 pc_init:PcInit, 2924 pc_ratio:Limit, 2925 shelf:Shelf 2926 }, 2927 NodeType = eplex(EplexHandle), 2928 GUB = bfs_gub{vars:Vars, 2929 pseudocosts:PCStructs 2930 }, 2931 arg(BranchPoint, PCStructs, PseudoCosts), 2932 PseudoCosts = pseudocost{pcd:PCD, 2933 pcd_count:PCD_Count, 2934 pcu:PCU 2935 }, 2936 ( PCD_Count = none -> 2937 ( PcInit == calculated -> 2938 % explicitly calculating initial pseudocosts: 2939 shelf_get(Shelf, info of bfs_shelf, OldInfo), 2940 estimate_degradation(Handle, NodeType, 2941 lp_add(EplexHandle, 2942 [(=:=):[0*1|Vars]], []), 2943 Limit, ObjValDown), 2944 PseudoCostDown is abs((ObjValDown - NodeCost)/Sum), 2945 estimate_degradation(Handle, NodeType, 2946 lp_add(EplexHandle, 2947 [(=:=):[-1*1|Vars]], []), 2948 Limit, ObjValUp), 2949 PseudoCostUp is abs((ObjValUp - NodeCost)/(1 - Sum)), 2950 shelf_set(Shelf, info of bfs_shelf, OldInfo) 2951 ; 2952 PcInit == average -> 2953 % initializing to current average: 2954 PseudoCostDown = PcDown, 2955 PseudoCostUp = PcUp 2956 ; 2957 printf(error, "unknown GUB pseudocost" 2958 " initialization method %w%n", 2959 [PcInit]), 2960 flush(ouput), 2961 abort 2962 ), 2963 Initializing = true, 2964 setarg(pcd_count of pseudocost, PseudoCosts, 0-PseudoCostDown), 2965 setarg(pcd of pseudocost, PseudoCosts, PseudoCostDown), 2966 setarg(pcu_count of pseudocost, PseudoCosts, 0-PseudoCostUp), 2967 setarg(pcu of pseudocost, PseudoCosts, PseudoCostUp) 2968 ; 2969 Initializing = fail, 2970 PseudoCostDown = PCD, 2971 PseudoCostUp = PCU 2972 ). 2973 2974get_pseudocosts(Handle, NodeType, NodeCost, Var, Val, 2975 PseudoCostDown, PseudoCostUp, Initializing) :- 2976 Handle = bfs_tree{pcd_average:PcDown, 2977 pcu_average:PcUp, 2978 pc_init:PcInit, 2979 pc_ratio:Limit, 2980 shelf:Shelf 2981 }, 2982 get_bfs_attr(Var, Handle, Attr), 2983 Attr = bfs{pcd:PCD, 2984 pcd_count:PCD_Count, 2985 pcu:PCU 2986 }, 2987 ( PCD_Count = none -> 2988 ( PcInit == calculated -> 2989 % explicitly calculating initial pseudocosts: 2990 shelf_get(Shelf, info of bfs_shelf, OldInfo), 2991 Hi is floor(Val), 2992 estimate_degradation(Handle, NodeType, 2993 set_var_bounds(Var, -1.0Inf, Hi), 2994 Limit, ObjValDown), 2995 PseudoCostDown is abs((ObjValDown - NodeCost)/(Val - Hi)), 2996 Lo is ceiling(Val), 2997 estimate_degradation(Handle, NodeType, 2998 set_var_bounds(Var, Lo, 1.0Inf), 2999 Limit, ObjValUp), 3000 PseudoCostUp is abs((ObjValUp - NodeCost)/(Lo - Val)), 3001 shelf_set(Shelf, info of bfs_shelf, OldInfo) 3002 ; 3003 PcInit == cost -> 3004 % initializing to cost coefficient: 3005 ( NodeType = eplex(EplexHandle) -> 3006 lp_get(EplexHandle, objective, Objective), 3007 Objective =.. [_MinMax, Expr], 3008 ( bfs_objective_coeff(Expr, Var, Cost) -> 3009 %EplexHandle = prob with objcoeffs:ObjCoeffs, 3010 %lp_var_occurrence(Var, EplexHandle, J), 3011 %( member(J:Cost, ObjCoeffs) -> 3012 true 3013 ; 3014 Cost = 0 3015 ) 3016 ; 3017 printf(error, "Don't know how to get the cost" 3018 " coefficient for %d in get_pseudocosts/8%n", 3019 [Var]), 3020 abort 3021 ), 3022 % Note to AE: 3023 % so we have to be able to GET the cost 3024 % coefficient from somewhere 3025 PseudoCostDown = Cost, 3026 PseudoCostUp = Cost 3027 ; 3028 PcInit == average -> 3029 % initializing to current average: 3030 PseudoCostDown = PcDown, 3031 PseudoCostUp = PcUp 3032 ; 3033 printf(error, "unknown pseudocost" 3034 " initialization method %w%n", 3035 [PcInit]), 3036 flush(ouput), 3037 abort 3038 ), 3039 3040 Initializing = true, 3041 3042 setarg(pcd_count of bfs, Attr, 0-PseudoCostDown), 3043 setarg(pcd of bfs, Attr, PseudoCostDown), 3044 setarg(pcu_count of bfs, Attr, 0-PseudoCostUp), 3045 setarg(pcu of bfs, Attr, PseudoCostUp) 3046 ; 3047 3048 Initializing = fail, 3049 3050 PseudoCostDown = PCD, 3051 PseudoCostUp = PCU 3052 ). 3053 3054bfs_objective_coeff(Expr1+Expr2, X, C) :- 3055 ( bfs_objective_coeff(Expr1, X, C) -> true 3056 ; bfs_objective_coeff(Expr2, X, C) -> true 3057 ; fail ). 3058%bfs_objective_coeff(Expr1+_Expr2, X, C) :- 3059% bfs_objective_coeff(Expr1, X, C). 3060%bfs_objective_coeff(_Expr1+Expr2, X, C) :- 3061% bfs_objective_coeff(Expr2, X, C). 3062bfs_objective_coeff(C*Var, X, C) :- 3063 Var == X, !. 3064bfs_objective_coeff(Var, X, 1) :- 3065 Var == X, !. 3066 3067get_gub_lowerbounds(Handle, eplex(EplexHandle), NodeCost, Terms, LD, LU) :- 3068 Handle = bfs_tree{lb_time:Limit, shelf:Shelf}, 3069 shelf_get(Shelf, info of bfs_shelf, OldInfo), 3070 length(Terms, NVars), 3071 GLimit is NVars * Limit, 3072 normalise_cstrs([sum(Terms) =:= 0, sum(Terms) =:= 1], 3073 [Cstr1, Cstr2], []), 3074 estimate_degradation(Handle, NodeType, 3075 lp_add(EplexHandle, Cstr1, []), 3076 GLimit, ObjValDown), 3077 LD is abs(ObjValDown - NodeCost), 3078 estimate_degradation(Handle, NodeType, 3079 lp_add(EplexHandle, Cstr2, []), 3080 GLimit, ObjValUp), 3081 LU is abs(ObjValUp - NodeCost), 3082 shelf_set(Shelf, info of bfs_shelf, OldInfo). 3083 3084get_lowerbounds(Handle, NodeType, NodeCost, Var, Val, LD, LU) :- 3085 Handle = bfs_tree{lb_time:Limit, shelf:Shelf}, 3086 shelf_get(Shelf, info of bfs_shelf, OldInfo), 3087 Hi is floor(Val), 3088 estimate_degradation(Handle, NodeType, 3089 set_var_bounds(Var, -1.0Inf, Hi), 3090 Limit, ObjValDown), 3091 LD is abs(ObjValDown - NodeCost), 3092 Lo is ceiling(Val), 3093 estimate_degradation(Handle, NodeType, 3094 set_var_bounds(Var, Lo, 1.0Inf), 3095 Limit, ObjValUp), 3096 LU is abs(ObjValUp - NodeCost), 3097 shelf_set(Shelf, info of bfs_shelf, OldInfo). 3098 3099estimate_degradation(bfs_tree{shelf:Shelf}, eplex(EplexHandle), 3100 Bound, Limit, _DegVal) :- 3101 shelf_set(Shelf, info of bfs_shelf, 1.0Inf), 3102 call(Bound), 3103 lp_get(optimizer, Optimizer), 3104 ( Optimizer == cplex -> 3105 lp_get(optimizer_param(iteration_limit), ItLim), 3106 lp_set(optimizer_param(iteration_limit), Limit) 3107 ; 3108 lp_get(EplexHandle, optimizer_param(iteration_limit), ItLim), 3109 lp_set(EplexHandle, optimizer_param(iteration_limit), Limit) 3110 ), 3111 lp_get(EplexHandle, method, Method), 3112 lp_set(EplexHandle, method, dual), 3113 set_event_handler(eplex_suboptimal, true/0), 3114 set_event_handler(eplex_abort, exit_abort/0), 3115 block( ( lp_solve(EplexHandle, Obj) -> true ; Obj = 1.0Inf ), 3116 abort, 3117 % IF there was an abort (probably hit iteration limit 3118 % before finding a feasible basis) AND presolve was 3119 % turned on AND the external solver is XPRESS-MP, THEN 3120 % the problem is not postsolved, and row/column numbers 3121 % can be completely wrong resulting in solution 3122 % information being returned in the incorrect order and 3123 % possibly variable bounds getting out of sync from now 3124 % on. Currently we avoid this by just disallowing the 3125 % use of a presolved XPRESS problem with estimate 3126 % degradation but we could alternatively check here and 3127 % reload the problem and bounds if necessary 3128 Obj = 1.0Inf 3129 ), 3130 set_event_handler(eplex_suboptimal, eplex_result_handler/2), 3131 set_event_handler(eplex_abort, eplex_result_handler/2), 3132 shelf_set(Shelf, info of bfs_shelf, Obj), 3133 ( Optimizer == cplex -> 3134 lp_set(optimizer_param(iteration_limit), ItLim) 3135 ; 3136 lp_set(EplexHandle, optimizer_param(iteration_limit), ItLim) 3137 ), 3138 lp_set(EplexHandle, method, Method), 3139 fail. 3140estimate_degradation(bfs_tree with shelf:Shelf, _, _, _, DegVal) :- 3141 shelf_get(Shelf, info of bfs_shelf, DegVal). 3142 3143exit_abort :- exit_block(abort). 3144 3145%----------------------------------------------------------------------- 3146% Pools 3147%----------------------------------------------------------------------- 3148 3149:- local record(bfs_pools). % list of bfs pool names 3150 3151create_bfs_pool(Pool) :- 3152 create_constraint_pool(Pool, property(arity) of bfs_constraint_type, 3153 [ 3154 deg_est/1 -> bfs_deg_est1/2, 3155 strong/1 -> bfs_strong1/2, 3156 enhanced/1 -> bfs_enhanced1/2, 3157 fracvar/0 -> bfs_fracvar1/1, 3158 node_cost/1 -> bfs_node_cost1/2, 3159 impose_node_state/1 -> bfs_impose_node_state1/2, 3160 update_pseudocosts/0 -> bfs_update_pseudocosts1/1, 3161 minimize_eplex_node/1 -> bfs_minimize_eplex_node1/2, 3162 var_get/3 -> bfs_var_get1/4, 3163 integers/1 -> bfs_integers1/2, 3164 get/2 -> bfs_get1/3, 3165 set/2 -> bfs_set1/3, 3166 node_info/2 -> bfs_node_info1/3, 3167 node_info/5 -> bfs_node_info1/6, 3168 statistics/0 -> bfs_statistics1/1, 3169 solve/1 -> bfs_solve1/2, 3170 solver_setup/2 -> bfs_solver_setup1/3, 3171 solver_setup/3 -> bfs_solver_setup1/4, 3172 solver_cleanup/0 -> bfs_solver_cleanup/1, 3173 bfs_branch/1 -> bfs_branch1/2, 3174 branch/2 -> bfs_branch1/3, 3175 global_cut/1 -> bfs_global_cut1/2 3176 ]). 3177 3178 3179bfs_instance(PoolName) :- 3180 ( lp_get(optimizer, xpress), lp_get(optimizer_version, 13) -> 3181 % warn the user that there are bugs when using 3182 % XPRESS-MP 13.26 as external solver 3183 % I am unsure whether this is related to the bugs 3184 % already reported to Dash, or something new 3185 printf(warning_output, "Warning: XPRESS-MP 13.26 is known to give" 3186 " incorrect (suboptimal) solutions on some test" 3187 " instances%n", []) 3188 ; true ), 3189 ( is_constraint_pool(PoolName), 3190 recorded(bfs_pools, PoolName) % is a bfs pool 3191 -> 3192 % if pool exists, check if it is currently empty 3193 ( pool_is_empty(PoolName), 3194 get_pool_item(PoolName, 0) % has no associated solver 3195 -> 3196 true 3197 ; 3198 printf(error, "Bfs instance still in use in %w%n", [bfs_instance(PoolName)]), 3199 abort 3200 ) 3201 ; 3202% ( current_module(PoolName) -> 3203% error(6, bfs_instance(PoolName)) 3204% ; 3205 record(bfs_pools, PoolName), 3206 create_bfs_pool(PoolName) 3207% ) 3208 ). 3209 3210get_pool_handle(Handle, Pool) :- 3211 get_pool_item(Pool, Handle0), 3212 ( Handle0 == 0 -> 3213 Handle = bfs_tree with [pool:Pool], 3214 init_suspension_list(node_susp of bfs_tree, Handle), 3215 set_pool_item(Pool, Handle) 3216 ; 3217 Handle0 = bfs_tree with [], 3218 Handle = Handle0 3219 ). 3220 3221% ---------------------------------------------------------------------- 3222 3223:- comment(categories, ["Algorithms","Constraints"]). 3224:- comment(summary, "Best-first search library"). 3225:- comment(author, "Andrew Eremin"). 3226:- comment(copyright, "Cisco Systems, Inc."). 3227:- comment(date, "$Date: 2012/07/31 02:17:06 $"). 3228:- comment(status, prototype). 3229 3230:- comment(include, bfs_comments). 3231