help-glpk
[Top][All Lists]

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

 From: HBuesching04 Subject: [Help-glpk] branch and bound for MILP - improvement possible? more details Date: Sun, 11 Jul 2004 18:47:08 +0200

```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.

```