Bi-criteria optimization problems for decision rules

Fawaz Alsolami (), Talha Amin (), Igor Chikalov () and Mikhail Moshkov ()
Additional contact information
Fawaz Alsolami: King Abdulaziz University
Talha Amin: King Abdullah University of Science and Technology
Igor Chikalov: King Abdullah University of Science and Technology
Mikhail Moshkov: King Abdullah University of Science and Technology

Annals of Operations Research, 2018, vol. 271, issue 2, No 1, 279-295

Abstract: Abstract We consider bi-criteria optimization problems for decision rules and rule systems relative to length and coverage. We study decision tables with many-valued decisions in which each row is associated with a set of decisions as well as single-valued decisions where each row has a single decision. Short rules are more understandable; rules covering more rows are more general. Both of these problems—minimization of length and maximization of coverage of rules are NP-hard. We create dynamic programming algorithms which can find the minimum length and the maximum coverage of rules, and can construct the set of Pareto optimal points for the corresponding bi-criteria optimization problem. This approach is applicable for medium-sized decision tables. However, the considered approach allows us to evaluate the quality of various heuristics for decision rule construction which are applicable for relatively big datasets. We can evaluate these heuristics from the point of view of (i) single-criterion—we can compare the length or coverage of rules constructed by heuristics; and (ii) bi-criteria—we can measure the distance of a point (length, coverage) corresponding to a heuristic from the set of Pareto optimal points. The presented results show that the best heuristics from the point of view of bi-criteria optimization are not always the best ones from the point of view of single-criterion optimization.

Keywords: Decision tables with many-valued decisions; Systems of decision rules; Dynamic programming; Pareto optimal points; Greedy heuristics (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2905-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:271:y:2018:i:2:d:10.1007_s10479-018-2905-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2905-0

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().