Sequential drug decision problems in long-term medical conditions: a case Study of Primary Hypertension Eunju Kim ba, ma, msc

2) Heuristics: Constructive methods

Given the search space is structured as a tree, constructive methods try to overcome the computational complexity by eliminating parts of the branches where it is unlikely to find an optimum solution. Various strategies for partitioning allow selective exploration of the active nodes of the trees to obtain an optimal or near optimal solutions for the problem.

The greedy algorithm, which is the simplest constructive heuristic method, moves one by one to make the best available decision at each stage^[153]. As this is a simple but short-sighted method to solve a large and complex decision problem, the algorithm has been often used as an extended version^[154-156] or as a part of meta-heuristics to improve the problem solving procedure^[157-159].

The branch-and-bound algorithm uses a lower bound (or upper bound for a maximisation problem) to avoid searching worse branches than the currently best branch identified from the previous search. Several derivatives of the branch-and-bound algorithm have been proposed. Best-first search explores the most promising node first based on a heuristic rule^{[160, 161]}. Breadth-first search explores all the nodes on one level first before moving to the next level^{[162, 163]}. Depth-first search proceeds down in the tree as deep as possible in an arbitrary pattern before making any decision and then backtracks out through the tree^{[164, 165]}. Branch-and-price^{[166, 167]}, branch-and-cut^[168] and A-algorithm^{[169, 170]} were also introduced.

Constructive methods are typically the fastest approximate methods, but limited when the decision space becomes very large. Therefore, various heuristics have been incorporated into the branch-and-bound algorithms. Garaix et al applied the greedy insertion procedure to construct a possible sequence, a descent method to identify the best solution on the first hierarchical level of the objective function, and a scheduling method to re-optimise the initial solution based on the second hierarchical level of the objective function^[167]. Dell'Amico et al introduced greedy heuristics incorporated with a local search and a scatter search^[165]. Local search methods, GA^[171] and SA^[172], also has been combined with the branch-and-bound algorithm. These studies showed that heuristics applied to the branch-and-bound algorithm improved the quality of solution with reasonable computational requirements.