US 10,832,141 B2Granted

Extract timeout core of a constraint satisfaction problem

AssigneeInternational Business Machines Corporation

InventorOdellia Boni

Life of this patent

Estimating the term…

Loading patent…

Abstract

A computerized method comprising using hardware processors for receiving a constraint satisfaction problem (CSP) from a constraint solver system that previously reached a timeout error. The CSP comprises two or more constraints. The hardware processor(s) are used for determining one or more timeout cores of constraints by iteratively removing some test constraints from the CSP thereby forming a sub-problem, and solving the sub-problem using the constraint solver system. When the constraint solver system determines that the sub-problem is solvable the test constraints are added to the timeout cores and the test constraint returning to the CSP, otherwise the sub-problem is assigned as the CSP for the subsequent iteration. The timeout cores are sent to a user terminal for presentation to a user, and receiving a user input to resolve the timeout error of the CSP.

Claims20

Dependent claims

A computerized method comprising using at least one hardware processor for:

receiving a constraint satisfaction problem (CSP) that previously reached a timeout error during a computation of a solution to the CSP, wherein it is not known whether the CSP would have been satisfiable absent a timeout threshold that caused the timeout error, and wherein the CSP comprises a plurality of constraints;
determining at least one timeout core of constraints by iteratively:
(a) removing some test constraints from the CSP thereby forming a sub-problem,
(b) solving the sub-problem using a constraint solver system,
(c) when the constraint solver system determines that the sub-problem is satisfiable, the test constraints are added to the at least one timeout core and are returned to the CSP for the subsequent iteration, and
(d) when the constraint solver system determines that the sub-problem reaches a sub-problem timeout error, the sub-problem is assigned as the CSP for the subsequent iteration;
and
sending the at least one timeout core to a user terminal, for:
(i) presentation to the user, and
(ii) receiving input from the user to resolve the timeout error of the CSP.

7 more elements

A computer program product, the computer program product comprising a non-transitory computer-readable storage medium having program code embodied therewith, the program code executable by at least one hardware processor for:

receiving a constraint satisfaction problem (CSP) that previously reached a timeout error during a computation of a solution to the CSP, wherein it is not known whether the CSP would have been satisfiable absent a timeout threshold that caused the timeout error, and wherein the CSP comprises a plurality of constraints;
determining at least one timeout core of constraints by iteratively:
(a) removing some test constraints from the CSP thereby forming a sub-problem,
(b) solving the sub-problem using a constraint solver system,
(c) when the constraint solver system determines that the sub-problem is solvable the test constraints are added to the at least one timeout core and are returned to the CSP for the subsequent iteration, and
(d) when the constraint solver system determines that the sub-problem reaches a sub-problem timeout error, the sub-problem is assigned as the CSP for the subsequent iteration;
and
sending the at least one timeout core to a user terminal, for:
(i) presentation to the user, and
(ii) receiving input from the user to resolve the timeout error of the CSP.

7 more elements

A computerized system comprising:

at least one hardware processor;
a non-transitory computer-readable storage medium having program code embodied therewith, the program code executable by the at least one hardware processor for:
receiving a constraint satisfaction problem (CSP), that previously reached a timeout error during a computation of a solution to the CSP, wherein it is not known whether the CSP would have been satisfiable absent a timeout threshold that caused the timeout error, and wherein the CSP comprises a plurality of constraints;
determining at least one timeout core of constraints by iteratively:
(a) removing some test constraints from the CSP thereby forming a sub-problem,
(b) solving the sub-problem using a constraint solver system,
(c) when the constraint solver system determines that the sub-problem is solvable the test constraints are added to the at least one timeout core and the test constraint returning to the CSP, and
(d) when the constraint solver system determines that the sub-problem reaches a sub-problem timeout error, sub-problem is assigned as the CSP for the subsequent iteration;
and
sending the at least one timeout core to a user terminal for:
(i) presentation to the user, and
(ii) receiving input from the user to resolve the timeout error of the CSP.

9 more elements

Dependencies are inferred from the claim text.