Skip Navigation

The Computer Journal 1973 16(2):135-140; doi:10.1093/comjnl/16.2.135
© 1973 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (9)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Wyman, F. P.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Binary programming: A decision rule for selecting optimal vs heuristic techniques

F. P. Wyman *

Department of Management Science and Organizational Behavior, College of Business, Administration, The Pennyslvania State University, 120 Boucke Building, University Park, Pennsylvania, USA

Management scientists have studied heuristics programming for some time, but usually with some degree of apology due to an inability to prove the optimality of their heuristic results. This paper illustrates how heuristic integer programming may be seriously studied inductively, with the purpose of developing a systematic body of propositions concerning computational properties of integer programming techniques. A decision rule is formulated for choosing between optimal and heuristic techniques on the basis of a more nearly global criterion for mathematical programming: cost of computation plus the value of the objective function.

An optimising 0-1 code is compared to a recently-developed heuristics 0-1 technique with respect to objective function value and computer time. The comparison is performed by varying three factors of problem structure: number of constraints, number of variables and constraint severity on a total of 180 problems. Regression models are postulated and fitted to the data with promising results. Breakeven charts are developed so that a user with a given problem size, cost of computation, and objective function may rapidly determine the preferability of heuristic-verus-optimal technique. The results indicated that the heuristic solutions are practically identical to the optimal solutions while requiring about one-tenth of the computational effort. The results also support the notion that a heuristic will eventually dominate any optimising technique for a sufficiently difficult problem.

Received July 1971.

* Department of Management Science and Organizational Behavior, College of Business Administration, The Pennsylvania State University, 120 Boucke Building, University Park, Pennsylvania 16802, USA


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.