An efficient SAT formulation for learning multiple criteria
  non-compensatory sorting rules from examples
  The literature on Multiple Criteria Decision Analysis (MCDA) proposes several
methods in order to sort alternatives evaluated on several attributes into
ordered classes. Non Compensatory Sorting models (NCS) assign alternatives to
classes based on the way they compare to multicriteria profiles separating the
consecutive classes. Previous works have proposed approaches to learn the
parameters of a NCS model based on a learning set. Exact approaches based on
mixed integer linear programming ensures that the learning set is best
restored, but can only handle datasets of limited size. Heuristic approaches
can handle large learning sets, but do not provide any guarantee about the
inferred model. In this paper, we propose an alternative formulation to learn a
NCS model. This formulation, based on a SAT problem, guarantees to find a model
fully consistent with the learning set (whenever it exists), and is
computationally much more efficient than existing exact MIP approaches.
