# US 2012/0253754 A1 · Method and apparatus for identifying inconsistent constraints

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

- Number: US 2012/0253754 A1
- Document ID: US20120253754A1
- Status: Published application
- Kind: A1
- Application number: 13/074,940
- Filed: 2011-03-29
- Published: 2012-10-04
- Earliest claimed: 2011-03-29
- Assignees: Synopsys, Inc.
- Inventors: Dhiraj Goswami; Soe Myint; Ngai Ngai William Hung; Rajarshi Mukherjee
- Web page: https://patentgrep.com/patent/US20120253754A1

## CPC

- 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)}
- G06F 30/23: using finite element methods [FEM] or finite difference methods [FDM]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and apparatuses are described for identifying inconsistent constraints. During operation, a system can receive a set of constraints, wherein each constraint is defined over one or more random variables from a set of random variables. If an inconsistency or conflict is detected while solving the set of constraints, the system can identify a phase in a series of phases of the constraint solver where the inconsistency was detected. The system can then try to solve different subsets of the set of constraints to identify smaller subsets of the set of constraints that contain the inconsistency. When the system tries to solve a subset of the set of constraints, the system can determine whether or not an inconsistency is detected in the identified phase while solving the subset of the set of constraints. Next, the system can report the smallest subset of inconsistent constraints that was found to a user.

## Claims

### Claim 1

A method for identifying inconsistent constraints, the method comprising:
receiving a set of constraints, wherein each constraint is defined over one or more random variables from a set of random variables;
identifying, by computer, a phase in a series of phases of a constraint solver where an inconsistency is detected while solving the set of constraints;
receiving a subset of the set of constraints; and
in response to determining that an inconsistency is not detected in the identified phase while solving the subset of the set of constraints, returning a result of said determining without processing subsequent phases in the series of phases.

### Claim 2 (depends on 1)

The method of claim 1, wherein the constraint solver is a canonical-representation-based constraint solver.

### Claim 3 (depends on 1)

The method of claim 1, wherein the constraint solver is a Satisfiability (SAT)-based constraint solver.

### Claim 4 (depends on 1)

The method of claim 1, wherein the constraint solver is a Satisfiability Modulo Theories (SMT)-based constraint solver.

### Claim 5 (depends on 1)

The method of claim 1, wherein the constraint solver is an Automatic Test Pattern Generation (ATPG)-based constraint solver.

### Claim 6 (depends on 1)

The method of claim 1, wherein the constraint solver is a hybrid constraint solver that combines multiple types of constraint solving techniques.

### Claim 7 (depends on 1)

The method of claim 1, wherein each phase in the series of phases attempts to further restrict the solution space of the set of constraints.

### Claim 8

A non-transitory computer-readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method for identifying inconsistent constraints, the method comprising:
receiving a set of constraints, wherein each constraint is defined over one or more random variables from a set of random variables;
identifying a phase in a series of phases of a constraint solver where an inconsistency is detected while solving the set of constraints;
receiving a subset of the set of constraints; and
in response to determining that an inconsistency is not detected in the identified phase while solving the subset of the set of constraints, returning a result of said determining without processing subsequent phases in the series of phases.

### Claim 9 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the constraint solver is a canonical-representation-based constraint solver.

### Claim 10 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the constraint solver is a Satisfiability (SAT)-based constraint solver.

### Claim 11 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the constraint solver is a Satisfiability Modulo Theories (SMT)-based constraint solver.

### Claim 12 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the constraint solver is an Automatic Test Pattern Generation (ATPG)-based constraint solver.

### Claim 13 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein the constraint solver is a hybrid constraint solver that combines multiple types of constraint solving techniques.

### Claim 14 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein each phase in the series of phases attempts to further restrict the solution space of the set of constraints.

### Claim 15

A system, comprising:
a processor; and
a storage medium storing instructions that, when executed by the processor, cause the system to perform a method for identifying inconsistent constraints, the method comprising:
receiving a set of constraints, wherein each constraint is defined over one or more random variables from a set of random variables;
identifying a phase in a series of phases of a constraint solver where an inconsistency is detected while solving the set of constraints;
receiving a subset of the set of constraints;
in response to determining that an inconsistency is not detected in the identified phase while solving the subset of the set of constraints, returning a result of said determining without processing subsequent phases in the series of phases.

### Claim 16 (depends on 15)

The system of claim 15, wherein the constraint solver is a canonical-representation-based constraint solver.

### Claim 17 (depends on 15)

The system of claim 15, wherein the constraint solver is a Satisfiability (SAT)-based constraint solver.

### Claim 18 (depends on 15)

The system of claim 15, wherein the constraint solver is a Satisfiability Modulo Theories (SMT)-based constraint solver.

### Claim 19 (depends on 15)

The system of claim 15, wherein the constraint solver is an Automatic Test Pattern Generation (ATPG)-based constraint solver.

### Claim 20 (depends on 15)

The system of claim 15, wherein the constraint solver is a hybrid constraint solver that combines multiple types of constraint solving techniques.

### Claim 21 (depends on 15)

The system of claim 15, wherein each phase in the series of phases attempts to further restrict the solution space of the set of constraints.
