[Help-glpk] branch and bound for MILP - improvement possible? more details

[HBuesching04]

Has anyone an opinion about the suggestion? Feel free to do anything 
with it as you like.

New logic for pruning within branch and bound (while working on a node 
n of the branch-tree):

- solve new LP, which gives a lower value l(n) for the used assumptions 
- calculate delta by quick dual branching (new!)
- if l(n) + delta > upperlimit of MILP, prune this node (new is "delta")
- and so on as normal


Calculating the delta (routine in pseudo code):

Delta = 0
unfreeze all (in)equalities 
Loop over all non-integer variables x which are not part of a frozen 
inequality yet 
  set x := floor (x) (new equation!) and call 
quick_solve_dual_for_dual_branching and store resulting delta1
  set x := ceiling (x)(n. equ.) and call 
quick_solve_dual_for_dual_branching and store resulting delta2
  if minimum (delta1, delta2) > 0
     delta = delta + minimum(delta1, delta2)
     Freeze those inequalities (dual variable), which have a variable 
of a inequality, 
                                                which were changed in 
the two former calls  
                                                 <--- only working for 
sparse matrices for restrictions !!!! 
  end if
End Loop


Short survey of the subroutine quick_solve_dual_for_dual_branching:

- Build LP with non-freezed inequalities and new fixed variable x(e) 
- Make one or two steps in the solution of the dual LP
- Return change of lower limit and mark changed dual variables 
(inequalities)






A more easy implementation for calculating the delta would be the trial 
of some branches, then trying to combine these to a delta, but the 
running times will be much larger:

Delta = 0
unmark all (in)equalities 
Loop over all non-integer variables x, which are not part of a marked 
inequality yet 
  set x := floor (x) (new equation!) call solve_branching and store 
resulting delta1 and changed dual variables
  set x := ceiling (x) (n. equ.!) and call solve_branching and store 
resulting delta2 and changed dual variables
  if those dual variables which were changed in the two former calls 
have no variables in common 
     with the marked inequalities (<--- sparse matrices!)
     delta = delta + minimum(delta1, delta2)
     mark those inequalities (dual variables), which were changed in 
the two former solve calls
  end if
End Loop



I would begin with the slow algorithm! If noone takes the challenge my 
plans are to realize it in the next years. In my opinion this algorithm 
should be quite an improvement for very big sparse MILP.

Since now there is a lot of freedom in the given algorithm, it can be 
surely improved to higher deltas. 

Best regards
from Cologne
Harald.