...;.....o..
`
`HAMILTON & TERRILE, LLP
`.__._
`€0-------------------------------------------~------------------------
`~ c::n
`8911 North Capital of Texas Highway
`Westech Center Suite 3150
`Austin, Texas 78759
`512.338.9100 Telephone
`512.345.7225 Facsimile
`
`. ''
`
`October 4, 2004
`
`COMMISSIONER FOR PATENTS
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`Enclosed herewith for filing is a patent application, as follows:
`Nathan E. Little, Brandon M. Beck, Brian K. Showers
`Inventor(s):
`Title:
`Complex Configuration Processing Using Configuration Sub-Models
`DocketNo.:
`T00121
`Customer No.:
`33438
`
`X Return Receipt Postcard
`X Check for $1,650.00 for Filing Fee
`X Transmittal Letter
`22 page(s) Specification (not including Claims)
`10
`page(s) Claims
`_1_ page(s) Abstract
`8
`sheet(s) of Drawings
`-2- page(s) Declaration For Patent Application and Power of Attorney
`page(s) Recordation Form Cover Sheet
`page(s) Assignment
`page(s) Nonpublication Request
`
`For
`
`CLAIMS AS FILED (fees com(!uted under §1.9(!))
`Number
`Number
`Filed
`Extra
`
`Rate
`
`Total Claims
`
`46
`
`-20
`
`26
`
`X
`
`$18
`
`Basic Fee
`790.00
`
`468.00
`
`$
`
`$
`
`~ ..
`
`X
`
`$
`
`$
`
`Independent Claims
`$88
`4
`7
`-3
`0 Application contains one or more multiple dependent claims ($300 total fee)
`CSI Fee for Recordation Form Cover Sheet and Assignment
`CSI Check enclosed for total fees in the amount of:
`$1,650.00
`CSI The Commissioner is hereby authorized to charge any additional fees which may be required,
`or credit any overpayment to Deposit Account 502264.
`
`352.00
`
`0.00
`
`$40.00
`
`EXPRESS MAIL LABEL NO:
`EV469744168US
`
`Respectfully submitted,
`
`~~
`
`Kent B. Chambers
`Attorney for Applicant(s)
`Reg. No. 38,839
`
`Page 1 of 507
`
`FORD 1004
`
`

`
`PTO/SB/35 (11-00)
`Approved through use through I 0/31n002 OMB 0651-0031
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of 1995. no persons are required to resoond to collection of information unless it displays a valid OMB control number.
`
`NONPUBLICATION REQUEST
`UNDER
`35 u.s.c. 122(b)(2)(B)(i)
`
`First Named Nathan E. Little
`Inventor
`~---------r------------------------~
`Complex Configuration
`Processing Using Configuration
`Sub-Models
`
`Title
`
`Attorney
`Docket
`Number
`
`T00121
`
`I hereby certify that the invention disclosed in the attached application has not and will
`not be the subject of an application filed in another country, or under a multilateral
`agreement, that requires publication at eighteen months after filing. I hereby request that
`the attached application not be published under 35 U.S.C. 122(b).
`
`Oc_/o/;er if 200'/
`Date
`
`?'
`
`Signature
`
`Kent B. Chambers, Reg. No. 38,839
`Typed or printed name
`
`This request must be signed in compliance with 37 CFR 1.33(b) and submitted with the
`application upon filing.
`
`Applicant may rescind this nonpublication request at any time. If applicant rescinds a
`request that an application not be published under 35 U.S.C. 122(b), the application will
`be scheduled for publication at eighteen months from the earliest claimed filing date for
`which a benefit is claimed.
`
`If applicant subsequently files an application directed to the invention disclosed in the
`attached application in another country, or under a multilateral international agreement,
`that requires publication of applications eighteen months after filing, the applicant must
`notify the United States Patent and Trademark Office of such filing within forty-five ( 45)
`days after the date of the filing of such foreign or international application. Failure to do
`so will result in abandonment of this application (35 U.S.C. 122(b)(2)(B)(iii)).
`
`Burden Hour Statement: Thts collectiOn ofmformatmn ts required by 37 CFR 1.213(a). The mformatmn IS used by the pubhc to
`request that an application not be published under 35 U.S.C. 122(b) (and the PTO to process that request). Confidentiality is governed
`by 35 U.S.C. 122 and 37 CFR 1.14.
`
`Page 2 of 507
`
`FORD 1004
`
`

`
`...;.....o..
`
`HAMILTON & TERRILE, LLP
`.__._
`€0-------------------------------------------~------------------------
`~ c::n
`8911 North Capital of Texas Highway
`Westech Center Suite 3150
`Austin, Texas 78759
`512.338.9100 Telephone
`512.345.7225 Facsimile
`
`. ''
`
`October 4, 2004
`
`COMMISSIONER FOR PATENTS
`P.O. Box 1450
`Alexandria, VA 22313-1450
`
`Enclosed herewith for filing is a patent application, as follows:
`Nathan E. Little, Brandon M. Beck, Brian K. Showers
`Inventor(s):
`Title:
`Complex Configuration Processing Using Configuration Sub-Models
`DocketNo.:
`T00121
`Customer No.:
`33438
`
`X Return Receipt Postcard
`X Check for $1,650.00 for Filing Fee
`X Transmittal Letter
`22 page(s) Specification (not including Claims)
`10
`page(s) Claims
`_1_ page(s) Abstract
`8
`sheet(s) of Drawings
`-2- page(s) Declaration For Patent Application and Power of Attorney
`page(s) Recordation Form Cover Sheet
`page(s) Assignment
`page(s) Nonpublication Request
`
`For
`
`CLAIMS AS FILED (fees com(!uted under §1.9(!))
`Number
`Number
`Filed
`Extra
`
`Rate
`
`Total Claims
`
`46
`
`-20
`
`26
`
`X
`
`$18
`
`Basic Fee
`790.00
`
`468.00
`
`$
`
`$
`
`~ ..
`
`X
`
`$
`
`$
`
`Independent Claims
`$88
`4
`7
`-3
`0 Application contains one or more multiple dependent claims ($300 total fee)
`CSI Fee for Recordation Form Cover Sheet and Assignment
`CSI Check enclosed for total fees in the amount of:
`$1,650.00
`CSI The Commissioner is hereby authorized to charge any additional fees which may be required,
`or credit any overpayment to Deposit Account 502264.
`
`352.00
`
`0.00
`
`$40.00
`
`EXPRESS MAIL LABEL NO:
`EV469744168US
`
`Respectfully submitted,
`
`~~
`
`Kent B. Chambers
`Attorney for Applicant(s)
`Reg. No. 38,839
`
`Page 3 of 507
`
`FORD 1004
`
`

`
`PTO/SB/35 (11-00)
`Approved through use through I 0/31n002 OMB 0651-0031
`U.S. Patent and Trademark Office; U.S. DEPARTMENT OF COMMERCE
`Under the Paperwork Reduction Act of 1995. no persons are required to resoond to collection of information unless it displays a valid OMB control number.
`
`NONPUBLICATION REQUEST
`UNDER
`35 u.s.c. 122(b)(2)(B)(i)
`
`First Named Nathan E. Little
`Inventor
`~---------r------------------------~
`Complex Configuration
`Processing Using Configuration
`Sub-Models
`
`Title
`
`Attorney
`Docket
`Number
`
`T00121
`
`I hereby certify that the invention disclosed in the attached application has not and will
`not be the subject of an application filed in another country, or under a multilateral
`agreement, that requires publication at eighteen months after filing. I hereby request that
`the attached application not be published under 35 U.S.C. 122(b).
`
`Oc_/o/;er if 200'/
`Date
`
`?'
`
`Signature
`
`Kent B. Chambers, Reg. No. 38,839
`Typed or printed name
`
`This request must be signed in compliance with 37 CFR 1.33(b) and submitted with the
`application upon filing.
`
`Applicant may rescind this nonpublication request at any time. If applicant rescinds a
`request that an application not be published under 35 U.S.C. 122(b), the application will
`be scheduled for publication at eighteen months from the earliest claimed filing date for
`which a benefit is claimed.
`
`If applicant subsequently files an application directed to the invention disclosed in the
`attached application in another country, or under a multilateral international agreement,
`that requires publication of applications eighteen months after filing, the applicant must
`notify the United States Patent and Trademark Office of such filing within forty-five ( 45)
`days after the date of the filing of such foreign or international application. Failure to do
`so will result in abandonment of this application (35 U.S.C. 122(b)(2)(B)(iii)).
`
`Burden Hour Statement: Thts collectiOn ofmformatmn ts required by 37 CFR 1.213(a). The mformatmn IS used by the pubhc to
`request that an application not be published under 35 U.S.C. 122(b) (and the PTO to process that request). Confidentiality is governed
`by 35 U.S.C. 122 and 37 CFR 1.14.
`
`Page 4 of 507
`
`FORD 1004
`
`

`
`AttomeyDocketNo.: TOOJ21
`
`"Express Mail" mailing label number:
`
`EV 4697 44168 US
`
`COMPLEX CONFIGURATION PROCESSING USING CONFIGURATION
`SUB-MODELS
`
`Nathan E. Little, Brandon M. Beck, and Brian K. Showers
`
`BACKGROUND OF THE INVENTION
`
`Field of the Invention
`
`(1)
`
`The present invention relates in general to the field of information processing,
`
`and more specifically to a system and method for processing complex configuration
`
`problems using configuration sub-models.
`
`DESCRIPTION OF THE RELATED ART
`
`(2)
`
`Computer assisted product configuration continues to offer substantial benefits
`
`to a wide range of users and industries. Figure 1 depicts a conventional product
`
`configuration process 100 performed by a configuration engine 101. The
`
`configuration process 100 represents one embodiment of an inference procedure. In
`
`one embodiment of a conventional inference procedure, configuration query 102 is
`
`formulated based on user configuration input, a configuration engine performs the
`
`configuration query 102 using a configuration model 104, and the configuration
`
`engine provides an answer 106 to the configuration query 102 based on the
`
`configuration query 102 and the contents of the configuration model104. The answer
`
`106 represents a particular response to the configuration query 102.
`
`(3)
`
`A configuration model104 uses, for example, data, rules, and/or constraints
`
`(collectively referred to as "data") to define compatibility relationships between parts
`
`(also commonly referred to as "features") contained in a specific type of product. A
`
`part represents a single component or attribute from a larger, more complex system.
`
`Parts may be combined in different ways in accordance with rules and/or constraints
`
`to define different instances of the more complex system. For example, "V6 engine"
`
`or the exterior color "red" can be parts on a vehicle, and a specific hard disk drive can
`
`-1-
`
`Page 5 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: TOO 121
`
`be a part on a computer. A part group, also called a group, represents a collection of
`
`related parts. For example, an "Engines" group might contain the parts "V6 engine"
`
`and "4 cylinder engine". A product configuration is a set of parts that define a
`
`product. For example, a vehicle configuration containing the parts "V6 engine" and
`
`"red" represents a physical vehicle that has a red exterior and a V6 engine. A product
`
`can be a physical product such as a vehicle, computer, or any other product that
`
`consists of a number of configurable features such as an insurance product.
`
`Additionally, a product can also represent a service. A configuration query (also
`
`referred to as a "query") is essentially a question that is asked about the parts and
`
`relationships in a configuration model. The answer returned from a configuration
`
`query will depend on the data in the configuration model, the approach used for
`
`answering the question, and the specifics of the question itself. For example, one
`
`possible configuration query, translated to an English sentence, is the following: For
`
`the given configuration model, are the parts "red" and "V6 engine" compatible with
`
`each other.
`
`(4)
`
`The configuration model104 can be used to determine, for example, which
`
`parts are compatible with other parts, and provide additional details around specific
`
`relationships. For example, a vehicle configuration model can indicate that "red" (a
`
`part) is the standard color feature for a specific vehicle, but that the color red is not
`
`compatible with "V6 engine" (a part). Configuration mode1104 may also contain
`
`additional information needed to support specific product related queries.
`
`Configuration models can be developed in any number of ways. U.S. Patent no.
`
`5,825,651 entitled "Method and Apparatus for Maintaining and Configuring
`
`Systems", inventors Gupta et al., and assigned to Trilogy Development Group, Inc.,
`
`describes an example ·configuration engine and rules based configuration model. U.S.
`
`Patent no. 5,825,651 is incorporated herein by reference in its entirety. U.S. Patent
`
`no. 5,515,524 entitled "Method and Apparatus for Configuring Systems", inventors
`
`John Lynch and David Franke, and assigned to Trilogy Development Group, Inc.,
`
`describes another example configuration engine and constraint based configuration
`
`model. U.S. Patent no. 5,515, 524 is also incorporated by reference in it entirety.
`
`(5)
`
`Figure 2 depicts an example configuration model200 of a product represented
`
`in a graphical, tree based form. The product can be configured to include part
`
`-2-
`
`Page 6 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: T00121
`
`combinations Al, Bl or B2, Cl, Xl or X2, and Yl or configured to include part
`
`combinations A2, B2, C2, X2, and Yl or Y2. The configuration model 200 includes
`
`rules to define these part relationships. Table 1 represents an example rule set,
`
`wherein "S" represents "standard" and "0" represents optional. Configuration model
`
`200 represents a relatively non-complex configuration model. Actual configuration
`
`models for a single product can include hundreds of thousands or more parts and
`
`rules.
`
`Example Configuration Rules for a Product
`
`'
`
`Al SALL
`
`A20ALL
`
`Bl SAl
`
`B2SA2
`
`B20Al
`
`Cl SAl
`
`C2 SA2
`
`Xl SCI
`
`X2 SC2
`
`X20Cl
`
`Yl OCl
`
`Yl SC2
`
`Y2 SCI
`
`Table 1
`
`-3-
`
`Page 7 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: T00121
`
`(6)
`
`Solving configuration problems using computer assisted technology often
`
`requires a significant amount of data processing capabilities. Consequently,
`
`configuration technologies have attempted to exploit increased data processing
`
`capabilities, memory capacities, and network data transfer throughput rates by
`
`increasing the capabilities of the configuration engines and/or enhancing the
`
`complexity of configuration models and configuration queries. The complexity of a
`
`configuration model can be defined in any number of ways, such as by the diversity of
`
`parts, part groups, rules, and constraints supported by the configuration model, by the
`
`number of parts, rules, and constraints, and by the complexity of part and part group
`
`relationships defined by configuration rules and constraints. In any event, the
`
`practical complexity achievable for configuration models has been limited by the
`
`ability of computer systems to process data within a given period oftime, T, and/or
`
`limited by other processing constraints, such as a lack of memory. The time period,
`
`T, represents an amount of time considered reasonable to perform a configuration
`
`task. Time T can vary depending upon the application and expectation of
`
`configuration system users.
`
`(7)
`
`Figure 3 depicts a graph 300 representing the practical limitations of
`
`configuration model and configuration query complexity in terms of data processing
`
`capabilities. Graph 300 compares data processing capabilities of a particular
`
`computer system being used to configure a product versus configuration model and
`
`query complexity. Conventional inference procedures, such as configuration
`
`processes, have an exponential complexity associated with them as depicted by
`
`exponential performance curve 302. Sufficien~ data processing capability exists to
`
`process a configuration model and configuration query having the complexity
`
`represented by point A. The dashed line 304 represents the maximum data processing
`
`capability of the particular computer system being used. Thus, the computer system
`
`could not reasonably process configuration models and configuration queries having a
`
`complexity represented by point B.
`
`SUMMARY OF THE INVENTION
`
`(8)
`
`In one embodiment, a sub-model inference procedure provides a way to scale
`
`queries to larger and more complicated configuration models. In one embodiment of
`
`-4-
`
`Page 8 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: TOOI21
`
`the present invention, a method for using computer assisted configuration technology
`
`to solve product configuration problems using configuration sub-models includes
`
`processing one or more configuration queries using configuration sub-models,
`
`wherein the configuration sub-models collectively model a configurable product and
`
`generating an answer to the configuration problem based upon the processed one or
`
`more configuration queries and the configuration sub-models.
`
`(9)
`
`In another embodiment of the present invention, a computer system to
`
`implement an inference procedure for solving product configuration problems using
`
`configuration sub-models includes a processor and a storage medium having data
`
`encoded therein. The data includes processor executable code for processing one or
`
`more configuration queries using configuration sub-models, wherein the configuration
`
`sub-models collectively model a configurable product and generating an· answer to the
`
`configuration problem based upon the processed one or more configuration queries
`
`and the configuration sub-models.
`
`(10)
`
`In another embodiment of the present invention, a computer storage medium
`
`comprising data embedded therein to cause a computer system to solve product
`
`configuration problems using configuration. The data includes code for processing
`
`one or more configuration queries using configuration sub-models, wherein the
`
`configuration sub-models collectively model a configurable product and generating an
`
`answer to the configuration problem based upon the processed one or more
`
`configuration queries and the configuration sub-models.
`
`(11)
`
`In another embodiment of the present invention, a computer system to
`
`implement an inference procedure for solving product configuration problems using
`
`configuration sub-models. The system includes means for processing one or more
`
`configuration queries using configuration sub-models, wherein the configuration sub(cid:173)
`
`models collectively model a configurable product and means for generating an answer
`
`to the configuration problem based upon the processed one or more configuration
`
`queries and the configuration sub-models.
`
`-5-
`
`Page 9 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: TOO 121
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`(12) The present invention may be better understood, and its numerous objects,
`
`features and advantages made apparent to those skilled in the art by referencing the
`
`accompanying drawings. The use of the same reference number throughout the
`
`several figures designates a like or similar element.
`
`(13)
`
`Figure 1 (prior art) depicts a conventional product configuration process.
`
`(14)
`
`Figure 2 (prior art) depicts a configuration model in graphical, tree based
`
`form.
`
`(15)
`
`Figure 3 (prior art) depicts a graph representing data processing capabilities of
`
`a computer system versus configuration model and query complexity.
`
`(16)
`
`Figure 4 depicts a configuration model dividing and configuration sub-model
`
`inference processing system that performs a configuration model dividing and
`
`configuration sub-model inference procedure.
`
`(17)
`
`Figure 5 depicts the data processing capability of a computer system being
`
`used to configure a product versus configuration sub-model and sub-query
`
`complexity.
`
`(18)
`
`Figure 6 depicts the division of a consolidated configuration model into
`
`configuration sub-models.
`
`(19)
`
`Figure 7 depicts a block diagram illustrating a network environment in which
`
`the system and process of Figure 4 may be practiced.
`
`(20)
`
`Figure 8 depicts an example data processing system used in the network of
`
`Figure 7.
`
`DETAILED DESCRIPTION
`
`(21) A configuration model dividing and configuration sub-model inference
`
`processing system and procedure addresses the issue of configuration model and
`
`-6-
`
`Page 10 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: TOOI21
`
`query complexity by breaking a configuration problem down into a set of smaller
`
`problems, solving them individually and recombining the results into a single result
`
`that is equivalent to a conventional inference procedure. In one embodiment, a
`
`configuration model is divided into configuration sub-models that can respectively be
`
`processed using existing data processing resources. The sub-model inference
`
`procedure does not change the exponential nature of configuration model and query
`
`complexity but instead generates configuration sub-models on the side of the
`
`achievable performance curve. Accordingly, a sub-model inference procedure
`
`provides a way to scale queries to larger and more complicated configuration models.
`
`Embodiments of the configuration model dividing and configuration sub-model
`
`processing system and inference procedure allows processing by a data processing
`
`system of configuration models and queries whose collective complexity exceeds the
`
`complexity of otherwise unprocessable conventional, consolidated configuration
`
`models and queries.
`
`(22)
`
`Figure 4 depicts the configuration model dividing and configuration sub(cid:173)
`
`model inference processing system 400 (referred to herein as "sub-model processing
`
`system 400") that performs configuration model dividing and configuration sub(cid:173)
`
`model inference procedure 402 (referred to herein as "sub-model inference procedure
`
`402"). The sub-model inference procedure 402 includes operations 404, 406, 408,
`
`and 410. The sub-model processing system 400 can include software code that is
`
`executable by a processor of a computer system, such as a server computer system. In
`
`a network environment, the sub-model processing system 400 can be accessed by and
`
`communicates with any number client systems 401(1) through 401(n).
`
`(23) Operation 404 receives, as an input, a conventional, consolidated
`
`configuration model412 and divides the consolidated configuration model412 into a
`
`set of configuration sub-models CM1 through CMn, where n is an integer
`
`representing the number of configuration sub-models. The configuration sub-models
`
`are an input to this process. In one embodiment, the configuration sub-models meet
`
`the following criteria:
`
`a. Each configuration sub-model should represent a portion of the source
`
`configuration model 412;
`
`-7-
`
`Page 11 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: T00121
`
`b. The data collectively contained in the configuration sub-models should
`
`be sufficient to provide an answer for each of the sub-queries Q 1
`
`through Qn or query being processed; and
`
`c. The configuration sub-models should be divided in such a way that the
`
`results of the sub-queries or query can be recombined to provide an
`
`answer to the input configuration query 414.
`
`(24)
`
`In another embodiment, a consolidated configuration model412 is never
`
`actually created, and model developers develop only configuration sub-models to
`
`collectively model a configurable product.
`
`(25)
`
`Figure 5 depicts the data processing capability of a computer system being
`
`used to configure a product versus configuration sub-model and sub-query
`
`complexity. In general, the consolidated configuration model412 is divided
`
`sufficiently so that the complexity of each configuration sub-model CM1, CM2,
`
`through CMn is low enough to allow processing using available data processing
`
`capabilities while still representing the relationships included in the consolidated
`
`configuration model412, which, in this embodiment, would otherwise not be cable of
`
`being processed by the computer system. Thus, the sub-model inference procedure
`
`402 does not change the exponential nature of configuration model and query
`
`complexity but instead generates configuration sub-models on the side of the
`
`achievable performance curve. Accordingly, the sub-model inference procedure 402
`
`provides a way to scale queries to larger and more complicated configuration models.
`
`(26)
`
`In one embodiment, operation 406 divides the conventional, consolidated
`
`configuration query 414 into a set of sub-queries Q 1 through Qn, which together
`
`contain enough information to represent the original query 414. Each sub-query
`
`generated will be used to query against at least one configuration sub-model. A query
`
`is divided into enough sub-queries to perform a query on at least enough of the sub(cid:173)
`
`models to produce an answer.
`
`(27) Whether to perform operation 406 and divide query 414 into sub-queries can
`
`depend upon the nature of the problem being solved. "Configuration completion" and
`
`"configuration validation" problems represent examples of two problems having
`
`-8-
`
`Page 12 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: T00121
`
`different natures that result in different sub-query approaches. Configuration
`
`completion relates to determining whether a configuration is valid according to the
`
`Configuration Model. A configuration is considered complete if there is a part present
`
`from every required part group in the configuration model. For example, when
`
`performing configuration completion, dividing the query 414 into sub-queries allows
`
`the sub-queries to each be processed using at least one configuration sub-model.
`
`Configuration validation relates to determining whether a configuration is "valid" or
`
`"not valid" according to the configuration model. "Valid" indicates that the parts are
`
`all compatible with each other according to the part relationships in the configuration
`
`model, and "not valid" indicates that the parts are not compatible with each other. In
`
`performing configuration validation, dividing the query 414 into sub-queries is
`
`unnecessary to determine validation, because the query 414 can be applied in whole
`
`against configuration sub-models. If any answer generated by processing query 414
`
`in accordance with a configuration sub-model results in an invalid (i.e. a non(cid:173)
`
`configurable) answer, then the configuration is invalid. Otherwise, the configuration
`
`is valid.
`
`(28)
`
`In one embodiment, the following criteria are used by operation 406:
`
`a. A single sub-query can be used to query against multiple sub-models.
`In other words, each sub-model does not have to have to process one
`
`and only one unique sub-query;
`
`b. The query 414 can be processed as a sub-query;
`
`c. When dividing a query into sub-queries, it is possible that there will be
`
`overlapping pieces of information contained in the sub-queries. It is
`
`not necessarily desired or a requirement that the sub-queries contain
`
`entirely independent questions;
`
`d. The way the query is divided into sub-queries depends on the structure
`
`of the configuration sub-models. Specifically, it depends on the way
`
`the sub-models are related, and the relationships between the parts in
`
`the overall model. For example, assume the sub-models were
`
`originally generated by dividing up the model along family lines with
`
`some overlap. The sub-queries will generally (though are not required
`
`-9-
`
`Page 13 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: T00121
`
`to) be divided up along similar family lines, with at least as many
`
`families present; and
`
`e.
`
`It will be understood by those of ordinary skill in the art that the way
`
`the query is divided into sub-queries also depends on the type of
`
`configuration query being performed. A configuration validation
`
`query might need a different Query Division approach than a
`
`Configuration Completion query.
`
`(29) Operation 408 processes the individual sub-queries.Ql through Qn against the
`
`configuration sub-models, producing a set of sub-answers. Enough sub-queries
`
`should be processed such that the sub-answers contain enough information to
`
`recombine them into a single answer to the input configuration query.
`
`(30) Operation 410 combines the sub-answers A1 through An together to create a
`
`single answer A. The answer A represents a correct answer for the input
`
`configuration query. However, for some queries, there are multiple correct answers.
`
`Thus, the answer determined by operation 410 is correct but may or may not be
`
`identical to an answer provided had the configuration query been performed using the
`
`conventional process depicted in Figure 1. For example,' in the case where the
`
`conventional process would return an "optimal" answer, the sub-model inference
`
`procedure 402 may return a sub-optimal, albeit correct, answer. Also, in the case that
`
`there is more than one "optimal" answer, the sub-model inference procedure 402 may
`
`return a different optimal answer than the conventional process.
`
`(31)
`
`In one embodiment, operations 404, 406, 408, and 410 are performed in order.
`
`However, operations 404,406, 408, and 410 can be overlapping. For example, it is
`
`not required that any given operation finish completely before the next operation
`
`begins. For example, as each sub-query is processed in operation 408, the resulting
`
`sub-answer can be determined to generate a growing, cumulative answer A before the
`
`next sub-query is processed.
`
`-10-
`
`Page 14 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: TOOI21
`
`(32) The following pseudo code represents the sub-model inference procedure 402:
`
`result inference-procedure(model, query)
`{
`
`sub-models= divide-model(model) (Operation 404, implementation
`dependent on the specific problem) OR initially develop configuration sub(cid:173)
`models
`sub-queries divide-query( query) (Operation 406, implementation
`dependent on the specific problem)
`
`II This loop encompasses Operation 408 II
`answers={}
`for(model in sub-models) {
`sub-query
`find-sub-query(sub-queries, model)
`II Get the right sub-query to be asking this sub-model II
`
`answers[ model]= model.inference-procedure(sub-query)
`II Run the inference procedure for this sub-query on the sub-
`
`model//
`}
`
`II Recombine the answers to each of the sub-queries into a single
`unified answer (Operation 410) // ·
`result combine(answers)
`
`return result
`
`}
`
`(33) The following examples illustrate embodiments of sub-model processing
`
`system 400 and sub-model inference procedure 402.
`
`(34) Example: Configuration Validation
`
`(35) The following example details sub-model inference procedure 402 in a context
`
`wherein an incoming configuration is complete (a part is present from every required
`
`part group). A query is generated using conventional processes to query against the
`
`configuration sub-models to determine if the configuration is valid.
`
`(36) The following pseudo code represents the embodiment of sub-model inference
`
`procedure 402 used for configuration validation:
`
`//for the complete feature string validation problem
`divide-model =procedure which breaks a consolidated model up into sub(cid:173)
`. models along family lines OR initially develop configuration sub-models.
`
`divide-query = returns the original query unchanged
`
`-11-
`
`Page 15 of 507
`
`FORD 1004
`
`

`
`AttomeyDocketNo.: TOOI21
`
`combine = loop which takes each boolean answer and uses the logical
`AND operator to combine them
`into a single boolean answer II
`
`boolean isBuildable(sub-models, query)
`{
`
`sub-queries= divide( query) (Operation 406);
`II Break the query into sub-queries. For a configuration validation
`query type, it is unnecessary to divide the query 414 into multiple sub-queries.
`Thus, in this embodiment of operation 406 query 414 = sub-query Q 1 and
`n=l. In other words, operation 406 can just return the entire original query
`414 II
`
`answers = [] (operation 408)
`for(model in sub-models) {
`sub-query
`find(sub-queries, model);
`II Get the right sub-query to be asking this sub-model II
`
`answers[ model) = model.isBuildable(sub-query);
`II Query against each sub-model II
`
`}
`
`result= True
`for( answerin answers) I I Operation 410 I I {
`result && answer; I I "&&" is a logical AND operator I I
`result
`II Recombine answers to sub-queries (this particular query type can
`just use a boolean and operator) II
`}
`return result;
`
`}
`
`(37) Table 2 represents a conventional configuration model and query for a
`
`configuration validation problem:
`
`-12-
`
`Page 16 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: T00\21
`
`Conventional Model:
`
`Al S ALL
`
`A20ALL
`
`Bl SAl
`
`B2SA2
`
`B20Al
`
`Xl SALL
`
`X20ALL
`
`Conventional Query:
`
`AreAl, Bland Xl buildable together? Yes
`
`Are A2, B 1 and Xl buildable together? No
`
`Table 2
`
`(38) The sub-model inference procedure 402 uses the conventional model as an
`
`input. In one embodiment, operation 404 divides the conventional model into the
`
`following configuration sub-models represented in Table 3, Table 4, and Table 5:
`
`Family A model:
`
`Al S ALL
`
`A20ALL
`
`Table 3
`
`-13-
`
`Page 17 of 507
`
`FORD 1004
`
`

`
`Attorney Docket No.: T00121
`
`Family B model:
`
`Bl SAl
`
`B20Al
`
`B2 SA2
`
`Table 4
`
`Family X model:
`
`Xl S ALL
`
`X20ALL
`
`Table 5
`
`(39) Table 6 and Table 7 represent one embodiment of sub-queries generated by
`
`operation 406 and s