Discrete Methods
Stochastic and Branch & Bound search can be used when the decision variables are discreteDecisions in which the alternatives are individually distinct. Examples are decisions which are the number of individual items (machines in a factory), an quantity that can be enumerated (machine type) and particularly yes/no decisions. and when the model and cost can be determined reasonably quickly.
A Stochastic search is suitable when the linkage between the effect of variables is relatively weak. It can be used when the calculation of the cost function requires that all decision variables have been set. The method is very simple, but not particularly powerful. Decision variables are selected randomly in turn (according to a preselected order) but respecting the constraints. If a full set of variables can be completed within the constraints the model and cost function are run. The set of variables with the lowest cost is recorded. If the decision set, model and cost function can be readily determined modern computers run so quickly that so many decisions are tried that a reasonable solution can be found in acceptable time. Of course the solution is not likely to be the true minimum, but in most cases data and details in the model and cost function are not exact so that there is little to be gained from finding the true optimal value. If the number of constraints makes it difficult to find valid sets of decisions then a full search of the decision space can be made. The decision of stochastic or full search can be made according to the number of valid decision combinations permitted by the constraints.
Branch and bound can be used if the model and cost function can be calculated with incomplete decision sets and increases as decisions are added to the set. The method uses a tree search of the decision space. Firstly a depth first search finds a valid solution, the model is run and the cost function is calculated. Then a systematic search of the decision tree is made, and as each decision is made the partial model and cost are calculated and if the cost is greater than the lowest cost found so far the branch can be abandoned. The performance of branch & bound depends on how quickly a good solution is found.
Optimal Solutions 4U has considerable experience in developing search algorithms for discrete decision problems. These algorithms can be delivered as individual applications or modules for incorporating into existing applications. We would be pleased to offer consultancy on this, or any other aspect of Optimisation. You can get in touch by sending a message from our Contact Us page, or by calling us on the number below.