# US 8,751,425 B2 · Constraint satisfaction problem solver with interactive conflict resolution

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,751,425 B2
- Document ID: US8751425B2
- Status: Granted
- Kind: B2
- Application number: 12/483,647
- Filed: 2009-06-12
- Published: 2010-12-16
- Granted: 2014-06-10
- Earliest claimed: 2009-06-12
- Assignees: Oracle International Corporation
- Applicants: Claire M. Bagley; Joyce Ng; Gao Chen
- Inventors: Claire M. Bagley; Joyce Ng; Gao Chen
- Web page: https://patentgrep.com/patent/US8751425B2

## CPC

- G06G 7/00: Devices in which the computing operation is performed by varying electric or magnetic quantities
- G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06N 5/04: Inference or reasoning models
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06G: ANALOGUE COMPUTERS (analogue optical computing devices G06E3/00)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A solver solves constraint satisfaction problems. The solver receives a user decision and propagates the user decision over a constraint satisfaction problem network. The solver then determines if there is a conflict on the network based on the propagation. If there is a conflict, the solver allows a user to resolve the conflict interactively by either canceling the user decision or dropping one or more previously made user decisions.

## Claims

### Claim 1

A non-transitory computer readable medium having instructions stored thereon that, when executed by a processor, causes the processor to solve a constraint satisfaction problem (CSP), the solving the CSP comprising:
receiving a first user decision, wherein the first user decision comprises a selection of a value for a variable of the CSP;
propagating the first user decision over a CSP network, wherein the propagating is performed before receiving another user decision subsequent to the first user decision;
determining a conflict based on the propagation, wherein the conflict prevents the CSP from being solved; and
resolving the conflict by interactively allowing a user to cancel the first user decision or drop one or more previous user decisions and displaying the one or more previous user decisions out of the previous user decisions that would resolve the conflict when dropped, the displaying comprising separately identifying the one or more previous user decisions out of all other previous user decisions as user decisions that will resolve the conflict when dropped.

### Claim 2 (depends on 1)

The computer readable medium of claim 1, wherein the one or more previous user decisions are generated by determining a first Minimum Conflict Set.

### Claim 3 (depends on 2)

The computer readable medium of claim 2, the solving the CSP further comprising:
dropping a first previous user decision; and
determining a second Minimum Conflict Set.

### Claim 4 (depends on 2)

The computer readable medium of claim 2, wherein the interactively allowing comprises generating a user interface that displays the first user decision and the first Minimum Conflict Set.

### Claim 5 (depends on 3)

The computer readable medium of claim 3, further comprising:
canceling the first user decision; and
restoring the first previous user decision.

### Claim 6 (depends on 2)

The computer readable medium of claim 2, wherein the Minimum Conflict Set comprises a minimal set of previous user decisions that are responsible for the conflict.

### Claim 7 (depends on 1)

The computer readable medium of claim 1, wherein the CSP is a product configuration and the first user decision is a choice for configuring a product.

### Claim 8 (depends on 1)

The computer readable medium of claim 1, wherein the one or more previous user decisions are generated by determining a minimal set of previously made user decisions together with the first user decision that is responsible for the conflict.

### Claim 9

A computer implemented method for solving a constraint satisfaction problem (CSP), the method comprising:
receiving a first user decision, wherein the first user decision comprises a selection of a value for a variable of the CSP;
propagating the first user decision over a CSP network, wherein the propagating is performed before receiving another user decision subsequent to the first user decision;
determining a conflict based on the propagation, wherein the conflict prevents the CSP from being solved; and
resolving the conflict by interactively allowing a user to cancel the first user decision or drop one or more previous user decisions and displaying the one or more previous user decisions out of the previous user decisions that would resolve the conflict when dropped, the displaying comprising separately identifying the one or more previous user decisions out of all other previous user decisions as user decisions that will resolve the conflict when dropped.

### Claim 10 (depends on 9)

The method of claim 9, wherein the one or more previous user decisions are generated by determining a first Minimum Conflict Set.

### Claim 11 (depends on 10)

The method of claim 10, wherein the interactively allowing comprises generating a user interface that displays the first user decision and the first Minimum Conflict Set.

### Claim 12 (depends on 10)

The method of claim 10, further comprising:
dropping a first previous user decision; and
determining a second Minimum Conflict Set.

### Claim 13 (depends on 9)

The method of claim 9, wherein the one or more previous user decisions are generated by determining a minimal set of previously made user decisions together with the first user decision that is responsible for the conflict.

### Claim 14 (depends on 9)

The method of claim 9, wherein the CSP is a product configuration and the first user decision is a choice for configuring a product.

### Claim 15

A solver system for solving a constraint satisfaction problem (CSP), the system comprising:
a processor;
a memory coupled to the processor; and
a constraint solver module coupled to the memory, the constraint solver module comprising functionality of receiving a first user decision, propagating the first user decision over a CSP network, determining a conflict based on the propagation, and resolving the conflict by interactively allowing a user to cancel the first user decision or drop one or more previous user decisions that were generated by determining a Minimum Conflict Set and displaying the one or more previous user decisions out of the previous user decisions that would resolve the conflict when dropped, the displaying comprising separately identifying the one or more previous user decisions out of all other previous user decisions as user decisions that will resolve the conflict when dropped;
wherein the first user decision comprises a selection of a value for a variable of the CSP;
wherein the propagating is performed before receiving another user decision subsequent to the first user decision; and
wherein the conflict prevents the CSP from being solved.

### Claim 16 (depends on 15)

The solver system of claim 15, wherein the system is a product configurator and the first user decision is a choice of a configuration of a product.

### Claim 17 (depends on 15)

The solver system of claim 15, wherein the interactively allowing comprises generating a user interface that displays the first user decision and the Minimum Conflict Set.

### Claim 18 (depends on 15)

The solver system of claim 15, wherein the one or more previous user decisions are generated by determining a minimal set of previously made user decisions together with the first user decision that is responsible for the conflict.

### Claim 19 (depends on 15)

The solver system of claim 15, further comprising:
dropping a first previous user decision; and
determining a second Minimum Conflict Set.