Problems, Models and Complexity. Part I: Theory
Publikationstyp
Journal Article
Date Issued
2003
Sprache
English
TORE-URI
Volume
2
Issue
2
Start Page
121
End Page
151
Citation
Journal of Mathematical Modelling and Algorithms 2 (2): 121-151 (2003)
Publisher DOI
Publisher
Springer
The meaning of the term 'problem' in operations research (OR) deviates from the understanding in the theoretical computer sciences: While an OR problem is often conceived to be stated or represented by model formulations, a computer-science problem can be viewed as a mapping from encoded instances to solutions. Such a computer-science problem turns out to be rather similar to an OR model formulation. This ambiguity may cause difficulties if the computer-science theory of computational complexity is applied in the OR context. In OR, a specific model formulation is commonly used in the analysis of the underlying problem and the results obtained for this model are simply lifted to the problem level. But this may lead to erroneous results, if the model used is not appropriate for such an analysis of the problem. To resolve this issue, we first suggest a new precise formal definition of the term problem which is identified with an equivalence class of models describing it. Afterwards, a new definition is suggested for the size of a model which depends on the assumed encoding scheme. Only models which exhibit a minimal size with respect to a 'reasonable' encoding scheme finally turn out to be suitable for the model-based complexity analysis of an OR problem. Therefore, the appropriate choice (or if necessary the construction) of a suitable representative of an OR problem becomes an important theoretical aspect of the modelling process.
Subjects
philosophy of modelling
problem complexity
terminology
DDC Class
330: Wirtschaft
600: Technik