Share Email Print

Proceedings Paper

Fast Algorithm To Generate Near Optimal Binary Decision Programs
Author(s): P. C. Baracos; L. C. Vroomen; L. J. Vroomen
Format Member Price Non-Member Price
PDF $14.40 $18.00

Paper Abstract

Binary decision (BD) programs have widespread applicability in diverse areas. In many situations, problems are defined in terms of Boolean expressions, which must be converted to decision programs for evaluation. Since the construction of optimal BD programs is NP-complete, absolute optimization appears computationally intractable. This paper presents a fast heuristic algorithm for constructing near-optimal decision programs and provides an optimality metric. The algorithm involves two steps: preprocessing and optimization. The preprocessor builds a sub-optimal (in some conditions near-optimal) decision program in linear time. If sub-optimal programs are generated, the optimizer is invoked, producing a near-optimal program, using decision tables, in 0(n2) time, where n is the size of the reduced decision table generated in the first step.

Paper Details

Date Published: 19 October 1987
PDF: 9 pages
Proc. SPIE 0853, IECON '87: Industrial Applications of Control and Simulation, (19 October 1987); doi: 10.1117/12.942936
Show Author Affiliations
P. C. Baracos, McGill University (Canada)
L. C. Vroomen, McGill University (Canada)
L. J. Vroomen, McGill University (Canada)

Published in SPIE Proceedings Vol. 0853:
IECON '87: Industrial Applications of Control and Simulation
Tom T. Hartley, Editor(s)

© SPIE. Terms of Use
Back to Top