Learn R Programming

QCA (version 3.26)

minimize: Minimize a truth table

Description

This function performs the QCA minimization of an input truth table, or if the input is a dataset it minimizes a set of causal conditions with respect to an outcome. Three minimization methods are available: the classical Quine-McCluskey, the enhanced Quine-McCluskey and the latest Consistency Cubes algorithm that is built for performance.

All algorithms return the same, exact solutions, see Dusa (2018) and Dusa and Thiem (2015).

Usage

minimize(input, include = "", dir.exp = NULL, details = FALSE, pi.cons = 0,
         sol.cons = 0, all.sol = FALSE, row.dom = FALSE, first.min = FALSE,
         max.comb = 0, use.labels = FALSE, method = "CCubes", ...)

Value

An object of class "qca" when using a single outcome, or class "mqca"

when using multiple outcomes. These objects are lists having the following components:

tt

The truth table object.

options

Values for the various options used in the function (including defaults).

negatives

The line number(s) of the negative configuration(s).

initials

The initial positive configuration(s).

PIchart

A list containing the PI chart(s).

primes

The prime implicant(s).

solution

A list of solution model(s).

certification

For consistency-based CCubes searches with returned models, a list with status (certified, inconclusive, smaller-model-exists, or verification-failed), minimum (the independently proved size, otherwise NA), scope (global or pi.depth), domain, verification work, and resource stop reason.

essential

A list of essential PI(s).

pims

A list of PI membership scores.

IC

The matrix containing the inclusion and coverage scores for the model(s).

SA

A list of simplifying assumptions.

i.sol

A list of components specific to intermediate model(s), each having a PI chart, prime implicant membership scores, (non-simplifying) easy counterfactuals and difficult counterfactuals.

complex

Flag solutions from a too complex PI chart

call

The user's command which produced all these objects and result(s).

Arguments

input

A truth table object (preferred) or a data frame containing calibrated causal conditions and an outcome.

include

A vector of other output values to include in the minimization process.

dir.exp

Character, a vector of directional expectations to derive the intermediate solution.

details

Logical, print more details about the solution.

pi.cons

Numerical fuzzy value between 0 and 1, minimal consistency threshold for a prime implicant to be declared as sufficient.

sol.cons

Numerical fuzzy value between 0 and 1, minimal consistency threshold for a model to be declared as sufficient.

all.sol

Logical, search for all possible models, including the non-minimal.

row.dom

Logical, perform row dominance in the prime implicants' chart to eliminate redundant prime implicants.

first.min

Logical, to return only the very first minimal solution (see Details).

max.comb

Numeric real, to limit the size of the PI chart (see Details).

use.labels

Logical, use category labels if present (see Examples).

method

Minimization method, one of "CCubes" (default), or "QMC" the classical Quine-McCluskey, or "eQMC" the enhanced Quine-McCluskey.

...

Other arguments, passed to other functions.

Author

Adrian Dusa

Details

Most of the times, this function takes a truth table object as the input for the minimization procedure, but the same argument can refer to a data frame containing calibrated columns.

For the later case, the function minimize() originally had some additional formal arguments which were sent to the function truthTable(): outcome, conditions, n.cut, incl.cut, show.cases, use.letters and inf.test.

All of these parameters are still possible with function minimize(), but since they are sent to the truthTable() function anyway, it is unnecessary to duplicate their explanation here. The only situation which does need an additional description relates to the argument outcome, where unlike truthTable() which accepts a single one, the function minimize() accepts multiple outcomes and performs a minimization for each of them (a situation when all columns are considered causal conditions).

The argument include specifies which other truth table rows are included in the minimization process. Most often, the remainders are included but any value accepted in the argument explain is also accepted in the argument include.

The argument dir.exp is used to specify directional expectations, as described by Ragin (2003). They can be specified using SOP (sum of products) expressions, which opens up the possibility to experiment with conjunctural directional expectations. "Don't care" conditions are simply left unspecified.

If at least one of the conditions included in the analysis is multi-value, the entire dir.exp expression should be specified in multi-value notation using squared brackets. If a condition X is crisp or fuzzy, the multi-value notation X[0] is interpreted as its absence, as in the ~X notation.

Activating the details argument has the effect of printing parameters of fit for each prime implicant and each overall model, the essential prime implicants being listed in the top part of the table. It also prints the truth table, in case the argument input has been provided as a data frame instead of a truth table object.

The default method (when all.sol = FALSE), is to find the minimal number (k) of prime implicants needed to cover all initial positive output configurations (minterms), then exhaustively search through all possible disjunctions of k prime implicants which do cover those configurations.

The minimal number k is determined by solving the set covering problem on the PI chart. During prime implicant generation, duplicate and dominated coverage columns are marked and omitted from the chart passed to every solver backend; the complete PI chart remains available for output and solution enumeration. Every available backend returns a proven minimum. By default, the internal hybrid solver combines a level-2 Lagrangian relaxation bound with reduced-cost fixing and a progress-adaptive branch-and-bound search. When that search is inconclusive, the reduced core is completed by the internal lp_solve backend (see findmin() for details). Setting hybrid = FALSE instead uses an integer programming formulation, solved with the Gurobi library when available or with the internal lp_solve library otherwise. The choice of backend can therefore only affect the solving time, never the solutions.

Once the PI chart is constructed using the prime implicants found in the previous stages, the argument row.dom can be used to further eliminate irrelevant prime implicants when solving the PI chart, applying the principle of row dominance: if a prime implicant A covers the same (intial) positive output configurations as another prime implicant B and in the same time covers other configurations which B does not cover, then B is irrelevant and eliminated.

A large number of causal conditions (i.e. over 15), combined with a large number of cases (i.e. hundreds) usually produce a very large number of prime implicants, resulting in a huge and extremely complex PI chart with sometimes thousands of rows and hundreds of columns.

For such a complex PI chart, even finding a minimum is a formidable task, and exhaustively solving it is very likely impossible in polynomial time. For this reason, after each level of complexity the CCubes algorithm determines if the PI chart is too difficult, by calculating the total number of combinations of minimum k PIs necessary to cover all columns.

The argument max.comb controls this maximum number of combinations. It is a rational number counted in (fractions of) billions, defaulted at zero to signal searching to the maximum possible extent. If the total number of combinations exceeds a positive value of max.comb, the PI chart is determined as too complex, the search is stopped and CCubes attempts to return all possible models using the PIs from the previous levels of complexity, when the PI chart was still not too complex.

In the extreme situation even this is not feasible, the argument first.min controls returning only one (the very first found) minimal model, if at all possible.

For ordinary truth-table minimization, CCubes uses one stalled complexity level as a trigger for exact checks. With first.min = TRUE, a bounded weighted integer search and a native SAT solver check whether a smaller binary cover can exist. A one-term cover is already minimal for a nonempty outcome. When the check finds a smaller cover is possible, generation continues so that the systematic chart contains the terms needed for a minimum model.

With the default first.min = FALSE, the check instead asks whether a legal term exists that contains none of the chart's prime implicants as a subterm. CCubes uses the complete chart to enumerate models. The native checks are bounded and apply to ordinary point tables with up to 15 conditions. Inconclusive checks continue through the applicable systematic depth. For searches using pi.cons or sol.cons, an independent finite-domain verifier reconstructs eligible prime implicants from the truth table and calibrated cases. A complete-family proof may end PI generation at a stalled level. After model search, the verifier checks a smallest returned model and exhaustively excludes all smaller PI models. It uses the same ordered double sums, membership operations and threshold tolerances as QCA, with no rounded integer weights or floating-point pruning bounds. With sol.cons > 0, feasibility uses the case-wise union's consistency and sol.cov; otherwise it requires covering the positive truth-table rows. The domain consists of eligible prime implicants, not arbitrary narrower conjunctions that might have better fit.

The returned certification component reports whether minimum size was independently certified. Its scope is global when PI depth is unrestricted, or relative to pi.depth otherwise. A minimum-size certificate does not assert that all returned irredundant models have that size, or that all minimum models have been enumerated under other search limits. Verification uses bounded work and memory: exhaustion leaves the existing search and PI-chart fallbacks, including lp_solve, available and reports an inconclusive certificate. It never changes an inconclusive check into a minimum claim.

Consistency-based PI generation also respects that depth. In the CCubes search with remainders, a positive pi.depth imposes a hard limit on the number of conditions in each prime implicant, regardless of pi.cons or all.sol. The default pi.depth = 0 leaves conjunction depth unrestricted by the user and retains automatic stopping. A positive limit can exclude deeper terms and increase the minimum number of terms in a model; any minimum is then relative to the permitted terms. The limit is respected even if no cover exists within it. A positive max.comb can also limit the search.

With sol.cons > 0, model sizes are searched in increasing order, so the first successful size establishes the minimum for the generated prime implicants. The default sol.depth = 0 no longer imposes a seven-term cap. With max.comb = 0, consistency-based enumeration stops once all branches are redundant with accepted models or provably unable to meet the fit thresholds at any larger size. A size with no new models is not sufficient to stop. Larger irredundant models remain available with all.sol = TRUE. A positive sol.depth is an explicit model-size limit. See causalChain for the data-derived upper bound and resource behavior. This stopping rule concerns consistency-based enumeration, not Petrick's method.

The arguments pi.cons and sol.cons are not specific to the traditional QCA minimization, that uses crisp (truth table) values of 0s and 1s. They mimic a CNA-style search with granular consistency levels for both prime implicants and / or solution models.

References

Cebotari, V.; Vink, M.P. (2013) “A Configurational Analysis of Ethnic Protest in Europe”. International Journal of Comparative Sociology vol.54, no.4, pp.298-324, tools:::Rd_expr_doi("10.1177/0020715213508567").

Cebotari, V.; Vink, M.P. (2015) “Replication Data for: A configurational analysis of ethnic protest in Europe”, Harvard Dataverse, V2, tools:::Rd_expr_doi("10.7910/DVN/PT2IB9").

Cronqvist, L.; Berg-Schlosser, D. (2009) “Multi-Value QCA (mvQCA)”, in Rihoux, B.; Ragin, C. (eds.) Configurational Comparative Methods. Qualitative Comparative Analysis (QCA) and Related Techniques, SAGE.

Dusa, A.; Thiem, A. (2015) “Enhancing the Minimization of Boolean and Multivalue Output Functions With eQMC” Journal of Mathematical Sociology vol.39, no.2, pp.92-108,
tools:::Rd_expr_doi("10.1080/0022250X.2014.897949").

Dusa, A. (2018) “Consistency Cubes: A Fast, Efficient Method for Boolean Minimization”, R Journal vol.10, issue 2, pp. 357-370, tools:::Rd_expr_doi("10.32614/RJ-2018-080")

Dusa, A. (2019) QCA with R. A Comprehensive Resource. Springer International Publishing, tools:::Rd_expr_doi("10.1007/978-3-319-75668-4").

Ragin, C. (2003) Recent Advances in Fuzzy-Set Methods and Their Application to Policy Questions. WP 2003-9, COMPASSS Working Papers series.

Ragin, C. (2009) “Qualitative Comparative Analysis Using Fuzzy-Sets (fsQCA)”, in Rihoux, B.; Ragin, C. (eds.) Configurational Comparative Methods. Qualitative Comparative Analysis (QCA) and Related Techniques, SAGE.

Ragin, C.C.; Strand, S.I. (2008) “Using Qualitative Comparative Analysis to Study Causal Order: Comment on Caren and Panofsky (2005).” Sociological Methods & Research vol.36, no.4, pp.431-441, tools:::Rd_expr_doi("10.1177/0049124107313903").

Rihoux, B.; De Meur, G. (2009) “Crisp Sets Qualitative Comparative Analysis (mvQCA)”, in Rihoux, B.; Ragin, C. (eds.) Configurational Comparative Methods. Qualitative Comparative Analysis (QCA) and Related Techniques, SAGE.

See Also

truthTable, factorize

Examples

Run this code
if (FALSE) {
# -----
# Lipset binary crisp data

# the associated truth table
ttLC <- truthTable(LC, SURV, sort.by = "incl, n", show.cases = TRUE)
ttLC

# conservative solution (Rihoux & De Meur 2009, p.57)
cLC <- minimize(ttLC)
cLC

# view the Venn diagram for the associated truth table
library(venn)
venn(cLC)

# add details and case names
minimize(ttLC, details = TRUE)

# negating the outcome
ttLCn <- truthTable(LC, ~SURV, sort.by = "incl, n", show.cases = TRUE)
minimize(ttLCn)

# parsimonious solution, positive output
pLC <- minimize(ttLC, include = "?", details = TRUE)
pLC

# the associated simplifying assumptions
pLC$SA

# parsimonious solution, negative output
pLCn <- minimize(ttLCn, include = "?", details = TRUE)
pLCn


# -----
# Lipset multi-value crisp data (Cronqvist & Berg-Schlosser 2009, p.80)

# truth table, conditions all columns from DEV to IND
# note the sequence operator ":"
ttLM <- truthTable(LM, SURV, conditions = DEV:IND,
        sort.by = "incl", show.cases = TRUE)

# conservative solution, positive output
minimize(ttLM, details = TRUE)

# parsimonious solution, positive output
minimize(ttLM, include = "?", details = TRUE)

# negate the outcome
ttLMn <- truthTable(LM, ~SURV, conditions = DEV:IND,
         sort.by = "incl", show.cases = TRUE)

# conservative solution, negative output
minimize(ttLMn, details = TRUE)

# parsimonious solution, positive output
minimize(ttLMn, include = "?", details = TRUE)


# -----
# Lipset fuzzy sets data (Ragin 2009, p.112)

ttLF <- truthTable(LF, SURV, incl.cut = 0.8, sort.by = "incl", show.cases = TRUE)

# conservative solution
minimize(ttLF, details = TRUE)

# parsimonious solution
minimize(ttLF, include = "?", details = TRUE)

# intermediate solution
minimize(ttLF, include = "?", details = TRUE,
         dir.exp = c(DEV, URB, LIT, IND, STB))

# directional expectations can also be specified using a sequence
minimize(ttLF, include = "?", details = TRUE, dir.exp = DEV:STB)

# URB as a don't care condition (left unspecified) and
# conjunctural directional expectations
minimize(ttLF, include = "?", details = TRUE,
         dir.exp = c(DEV, STB, ~LIT*IND))


# -----
# Cebotari & Vink (2013, 2015)

ttCVF <- truthTable(CVF, outcome = PROTEST, incl.cut = 0.8,
                    sort.by = "incl, n", show.cases = TRUE)

pCVF <- minimize(ttCVF, include = "?", details = TRUE)
pCVF

# inspect the PI chart
pCVF$PIchart

# DEMOC*ETHFRACT*~POLDIS is dominated by DEMOC*ETHFRACT*GEOCON
# using row dominance to solve the PI chart
pCVFrd <- minimize(ttCVF, include = "?", row.dom = TRUE, details = TRUE)

# plot the prime implicants on the outcome
pims <- pCVFrd$pims

par(mfrow = c(2, 2))
for(i in 1:4) {
    XYplot(pims[, i], CVF$PROTEST, cex.axis = 0.6)
}


# -----
# temporal QCA (Ragin & Strand 2008) serving the input as a dataset,
# which will automatically be passed to truthTable() as an intermediary
# step before the minimization

minimize(RS, outcome = REC, details = TRUE)


# -----
# employ category labels

ttLF <- truthTable(LF, SURV, incl.cut = 0.8, sort.by = "incl", show.cases = TRUE)

minimize(ttLF, include = "?", use.labels = TRUE)

# or

ttLF <- truthTable(
    LF, SURV, incl.cut = 0.8, sort.by = "incl", show.cases = TRUE,
    use.labels = TRUE
)

minimize(ttLF, include = "?")

}

Run the code above in your browser using DataLab