General Branch & Bound Algorithm

What you have to do:

Make sure that both a problem type and all parameters are defined. Choose Exact Algorithms|Branch & Bound from the menu Algorithms and after editing the options press OK.

Options:

Number of Solutions:

LisaBB is able to compute all optimal solutions of a given problem. To safe time and memory, give an upper bound for the number of schedules in the output, normally 1.

Lower bound:

If you know a lower bound for the objective function value, then enter it here. Each schedule which does not exceed this value is treated as optimal.

Upper bound:

If a schedule is already known, enter its objective value here to make the algorithm reject all schedules with bigger objective value.

Insertion order:

Chose the order in which LisaBB considers the operations. Possible are:

LPT

ordered by nonincreasing processing times

RANDOM

in random order

Bounding:

Chose a procedure to compute lower bounds within the algorithm:

NORMAL

objective function value of partial schedule

EXTENDED

not implemented

If LisaBB is too slow:

• Because LisaBB handles different kinds of problems, it cannot take advantage problem specific things. Use an algorithm especially implemented for your problem if possible.
• Abort the algorithm after some time. It will output the best solution(s) found so far.
• Try another insertion order or bounding procedure.
• Find the optimal objective value with option "Number of solutions=1". To find further optimal solutions in a second run, give the optimal objective value as upper and lower bound.
• If you cannot find the optimal solution, try finding a schedule with objective function in the interval [x,y] by giving x and y as lower and upper boud, respectively. However, it is possible that LisaBB does not find a schedule with this properties.