The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jun. 14, 2016
Filed:
Oct. 16, 2013
International Business Machines Corporation, Armonk, NY (US);
Philippe Laborie, L'Hay-les-Roses, FR;
Paul Shaw, Grasse, FR;
INTERNATIONAL BUSINESS MACHINES CORPORATION, Armonk, NY (US);
Abstract
According to an aspect, a method for providing a minimal explanation to a set of unsatisfiable constraints involves retrieving a minimal subset of constraints that remain together unsatisfiable. The method includes iterating over a list of n constraints, and building a minimal explanation to a set of unsatisfiable constraints by determining which constraint to add to the set of unsatisfiable constraints. Building includes accelerating by removing an increasing number of constraints until removed further constraints makes the set of constraints satisfiable. A dichotomic search is performed on the removed further constraints. The average observed distance is identified between successive constraints in the set of unsatisfiable constraints. A plurality of 2further constraints located in the list of constraints is removed at the average observed distance from the most recently added constraint. Testing whether a current selected subset is unsatisfiable is performed for the first log(n) added constraints.