Logic, Optimization, and Artificial Intelligence

# Logic, Optimization, and Artificial Intelligence
Source: [https://arxiv.org/html/2607.15532](https://arxiv.org/html/2607.15532)
11institutetext:Carnegie Mellon University,11email:jh38@andrew\.cmu\.edu1\. Introduction 2\. Probabilistic Logic 3\. Belief Logics 4\. Nonmonotonic and Many\-valued Logics 5\. Statistical Inference of Logical Formulas 6\. Inference as Projection 7\. Transparency through Postoptimality Analysis 8\. Answer Set Programming Modulo Theories 9\. Possible Research Directions References

## 1Introduction

Logic and optimization have played an essential role in artificial intelligence \(AI\) since its inception\. The very first AI program \(1956\),Logic Theorist[NewSim56](https://arxiv.org/html/2607.15532#bib.bib107), proved theorems of logic and mathematics, including several from Russell and Whitehead’s famous treatisePrincipia Mathematica\. The following year, the pathbreaking AI systemGeneral Problem Solver[NewShaSim59](https://arxiv.org/html/2607.15532#bib.bib106)applied means\-end analysis in a manner similar to logic programming\. As for optimization, the advent of machine learning and artificial neural networks immediately posed the problem of adjusting parameters to fit training data\. This optimization problem remains a central and challenging element of machine learning today\.

Logic and optimization are not only individually useful in AI, but they have much to offer when combined\. Together, they provide an ideal approach to implementing rule\-based AI\. While connectionist machine learning has achieved impressive results, it increasingly poses the issue of transparency, which is important for reproducibility, explainability, trustworthiness, and fairness[BurHub21](https://arxiv.org/html/2607.15532#bib.bib29);[Hai20](https://arxiv.org/html/2607.15532#bib.bib60);[Wal21](https://arxiv.org/html/2607.15532#bib.bib127);[ZhoChe18](https://arxiv.org/html/2607.15532#bib.bib135)\. Rule\-based AI provides a natural solution to transparency, because it allows knowledge to be explicitly encoded in rules from which relevant information can be inferred, and allows decisions to be deduced from a rule\-based production system\. While neural networks provide a useful model of cognition, a rule\-based framework has long served as an alternative model\. The well\-known ACT\-R framework inspired by AI pioneer Alan Newell, for example, places the agent’s executive function in a rule\-based production system[AndBotByrDouLebQin04](https://arxiv.org/html/2607.15532#bib.bib7);[LebAnd93](https://arxiv.org/html/2607.15532#bib.bib89);[New94](https://arxiv.org/html/2607.15532#bib.bib105)\.

Logic and optimization are natural partners in a rule\-based environment\. Logic provides the obvious framework for stating rules and deducing their implications, and even for their ethical assessment[KimHooDon21](https://arxiv.org/html/2607.15532#bib.bib83)\. Optimization comes into play as a powerful method for computing logical inferences, as well as conceptual elucidation of the various logics used in AI\. Optimization solvers, particularly for linear and integer programming, not only deduce inferences but can provide a traceback of how they are derived, thus enhancing the natural transparency of rule\-based AI\. These solvers have also improved enormously over the years\. For example, one study documents that integer programming solvers reduced solution times by a factor of 5 million between 1989 and 2024, quite apart from reductions due to faster machines[Sol24](https://arxiv.org/html/2607.15532#bib.bib121)\. More fundamentally, we will see that optimization and logical inference are special cases of the same basic problem\.

This paper presents a sampling of logic\-optimization partnerships that have developed in parallel with machine learning and deserve ongoing consideration, especially in view of today’s advanced optimization technology and concern for transparency\. We begin with probabilistic logic, which has a linear programming formulation that can be solved by modern column generation methods\. We also describe various extensions, including Bayesian logic, which combines probabilistic logic with Bayesian networks and makes use of nonlinear programming\. We examine belief logics as well, including Dempster\-Shafer theory and variants that have easily\-solved linear programming formulations\. We then take up two nonstandard logics that have seen application in AI, default logic \(a variety of nonmonotonic reasoning\) and many\-valued logics\. Both benefit from integer programming models\. At this point we turn from deducing implications of logical formulas to inferring the formulas themselves from noisy data\. We describe a form of Boolean regression that can be calibrated by integer programming and measures statistical significance\. We then delve into the underlying connection between logic and optimization just mentioned by observing that both, at root, pose a projection problem\. We show how this problem can be addressed by applying a recently developed optimization method, logic\-based Benders decomposition, to a knowledge base represented as a binary decision diagram \(BDD\)\. We next specify three ways in which optimization methods can provide tracebacks that are potentially useful for enhancing transparency in AI\. One is classical linear programming sensitivity analysis, and the other two are inference\-based and BDD\-based postoptimality analysis for integer programming\. Following this, we combine default logic, logic\-based Benders decomposition, and postoptimality analysis to illustrate the central role of optimization in answer set programming modulo theories\. We conclude by suggesting some possible avenues of future research\.

The emphasis throughout is on conveying the basic ideas and their motivation, rather than providing a complete technical description\. Details are available in the cited references, which cover both the methods discussed here and subsequent developments\.

## 2Probabilistic Logic

Although George Boole is best known for his work in propositional logic, he regarded probabilistic logic[Boo1854](https://arxiv.org/html/2607.15532#bib.bib22)as his most important contribution\. It in fact displays stunning originality\. Although forgotten for more than a century, it is highly relevant to the project of artificial intelligence today\. It allows one to determine with what confidence one can draw inferences from propositions that are known only to be true with certain probabilities\.

Hailperin[Hai76](https://arxiv.org/html/2607.15532#bib.bib61)observed in 1976 that Boole’s probabilistic logic can be given a linear programming model\. A decade after Hailperin’s work, Nilsson independently published a similar model in the AI literature[Nil86](https://arxiv.org/html/2607.15532#bib.bib109)\. His paper gave rise to a number of subsequent contributions, many of which are surveyed in[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31);[HanJau00](https://arxiv.org/html/2607.15532#bib.bib62);[KliPar11](https://arxiv.org/html/2607.15532#bib.bib86)\.

We begin by describing Boole’s probabilistic logic and its linear programming model\. We show how the well\-known technique of column generation can deal with the exponentially many variables in the model\. We then incorporate second\-order probabilities without sacrificing linearity\. Conditional independence assumptions introduce nonlinear constraints, but we indicate how exploiting the structure of a Bayesian network can somewhat ameliorate the resulting computational challenge\.

### 2\.1The Basic Model

Probabilistic logic is best explained by an example[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31)\. Suppose the probabilities of three logical propositions are given as follows:

Pr​\(x1\)=0\.9\\displaystyle\\mathrm\{Pr\}\(x\_\{1\}\)=0\.9\(1\)Pr​\(x1⊃x2\)=0\.8\\displaystyle\\mathrm\{Pr\}\(x\_\{1\}\\supset x\_\{2\}\)=0\.8\(2\)Pr​\(x2⊃x3\)=0\.7\\displaystyle\\mathrm\{Pr\}\(x\_\{2\}\\supset x\_\{3\}\)=0\.7\(3\)We are also given the conditional probability

Pr​\(x1\|x2,x3\)=Pr​\(x1,x2,x3\)Pr​\(x2,x3\)=0\.8\\mathrm\{Pr\}\(x\_\{1\}\\,\|\\,x\_\{2\},x\_\{3\}\)=\\frac\{\\mathrm\{Pr\}\(x\_\{1\},x\_\{2\},x\_\{3\}\)\}\{\\mathrm\{Pr\}\(x\_\{2\},x\_\{3\}\)\}=0\.8\(4\)Note that Pr\(x1⊃x2\)\(x\_\{1\}\\supset x\_\{2\}\)is not the conditional probability Pr\(x2\|x1\)\(x\_\{2\}\\,\|\\,x\_\{1\}\)\. It is the probability of the material conditionalx1⊃x2x\_\{1\}\\supset x\_\{2\}, which is equivalent to¬x1∨x2\\neg x\_\{1\}\\vee x\_\{2\}\. We wish to determine with what probability we can inferx3x\_\{3\}\. Boole observed that we cannot deduce a precise probability forx3x\_\{3\}, but we can deduce that its probability lies in a particularrange\.

In probabilistic logic, each possible assignment of truth values to𝒙=\(x1,x2,x3\)\{\\bm\{x\}\}=\(x\_\{1\},x\_\{2\},x\_\{3\}\)is regarded as a “possible world” \(values 0 and 1 correspond to false and true\)\. Each possible world𝒙\{\\bm\{x\}\}has a probabilityp𝒙p\_\{\\bm\{x\}\}, initially unknown\. For example,p000p\_\{000\}is the probability of the world in which\(x1,x2,x3\)=\(0,0,0\)\(x\_\{1\},x\_\{2\},x\_\{3\}\)=\(0,0,0\), and analogously forp001,…,p111p\_\{001\},\\ldots,p\_\{111\}\. Then the probability 0\.9 of propositionx1x\_\{1\}, for example, is

p100\+p101\+p110\+p111p\_\{100\}\+p\_\{101\}\+p\_\{110\}\+p\_\{111\}sincex1x\_\{1\}is true in the corresponding possible worlds, and similarly for propositionsx1⊃x2x\_\{1\}\\supset x\_\{2\}andx2⊃x3x\_\{2\}\\supset x\_\{3\}\. The probability assignments \([1](https://arxiv.org/html/2607.15532#Ch0.E1)\)–\([3](https://arxiv.org/html/2607.15532#Ch0.E3)\) can be written as the linear equations

p100\+p101\+p110\+p111=0\.9\\displaystyle p\_\{100\}\+p\_\{101\}\+p\_\{110\}\+p\_\{111\}=0\.9\(5\)p000\+p001\+p010\+p011\+p110\+p111=0\.8\\displaystyle p\_\{000\}\+p\_\{001\}\+p\_\{010\}\+p\_\{011\}\+p\_\{110\}\+p\_\{111\}=0\.8\(6\)p000\+p001\+p011\+p100\+p101\+p111=0\.7\\displaystyle p\_\{000\}\+p\_\{001\}\+p\_\{011\}\+p\_\{100\}\+p\_\{101\}\+p\_\{111\}=0\.7\(7\)The conditional probability assignment \([4](https://arxiv.org/html/2607.15532#Ch0.E4)\) can be linearized as

Pr​\(x1,x2,x3\)=0\.8​Pr​\(x2,x3\)\\mathrm\{Pr\}\(x\_\{1\},x\_\{2\},x\_\{3\}\)=0\.8\\mathrm\{Pr\}\(x\_\{2\},x\_\{3\}\)and therefore written

p111−0\.8​\(p011\+p111\)=0p\_\{111\}\-0\.8\(p\_\{011\}\+p\_\{111\}\)=0\(8\)
We can now deduce the range of possible values for the probability ofx3x\_\{3\}, which is equal to

p001\+p011\+p101\+p111p\_\{001\}\+p\_\{011\}\+p\_\{101\}\+p\_\{111\}\(9\)A sharp upper bound on this probability is the maximum of \([9](https://arxiv.org/html/2607.15532#Ch0.E9)\) subject to the constraints \([5](https://arxiv.org/html/2607.15532#Ch0.E5)\)–\([8](https://arxiv.org/html/2607.15532#Ch0.E8)\) and the normalization and nonnegativity constraints

p000\+p001\+p010\+p011\+p100\+p101\+p110\+p111=1\\displaystyle p\_\{000\}\+p\_\{001\}\+p\_\{010\}\+p\_\{011\}\+p\_\{100\}\+p\_\{101\}\+p\_\{110\}\+p\_\{111\}=1\(10\)p000,…,p111≥0\\displaystyle p\_\{000\},\\ldots,p\_\{111\}\\geq 0\(11\)This is a linear programming problem with maximum value 0\.7\. A sharp lower bound on the probability ofx3x\_\{3\}is the minimum of \([9](https://arxiv.org/html/2607.15532#Ch0.E9)\) subject to these constraints, which is 0\.5\. The probability ofx3x\_\{3\}must therefore be confined to the interval\[0\.5,0\.7\]\[0\.5,0\.7\]\. Due to the convexity of the feasible set defined by the constraints, every probability in this interval is consistent with the assigned probabilities \([5](https://arxiv.org/html/2607.15532#Ch0.E5)\)–\([8](https://arxiv.org/html/2607.15532#Ch0.E8)\)\.

In general, the probabilistic inference problem is

min/max⁡\{𝒄⊺​𝒑\|A​𝒑=𝝅,B​𝒑=𝟎,1⊺​𝒑=1,𝒑≥𝟎\}\\min/\\max\\;\\big\\\{\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}\\;\\big\|\\;A\{\\bm\{p\}\}=\{\\bm\{\\pi\}\},\\;B\{\\bm\{p\}\}=\{\\bm\{0\}\},\\;\{\\bm\{1\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}=1,\\;\{\\bm\{p\}\}\\geq\{\\bm\{0\}\}\\big\\\}\(12\)where constraintA​𝒑=𝝅A\{\\bm\{p\}\}=\{\\bm\{\\pi\}\}specifies the categorical probabilities,B​𝒑=𝟎B\{\\bm\{p\}\}=\{\\bm\{0\}\}specifies the conditional probabilities, and𝟏=\(1,1,…,1\)\{\\bm\{1\}\}=\(1,1,\\ldots,1\)\. The probability assignments are unsatisfiable if \([12](https://arxiv.org/html/2607.15532#Ch0.E12)\) has no feasible solution\. The example problem in this form is

min/max\{\[0 1 0 1 0 1 0 1\]𝒑\|\[000011111111001111011101\]​𝒑=\[0\.90\.80\.7\]\[0 0 0−0\.8 0 0 0 0\.2\]​𝒑=0\[1 1 1 1 1 1 1 1\]​𝒑=1,𝒑≥𝟎\}\\min/\\max\\left\\\{\[0\\;1\\;0\\;1\\;0\\;1\\;0\\;1\]\{\\bm\{p\}\}\\;\\left\|\\;\\;\\begin\{array\}\[\]\{l\}\\left\[\\begin\{array\}\[\]\{cccccccc\}0&0&0&0&1&1&1&1\\\\ 1&1&1&1&0&0&1&1\\\\ 1&1&0&1&1&1&0&1\\end\{array\}\\right\]\{\\\!\\bm\{p\}\}=\\left\[\\begin\{array\}\[\]\{c\}0\.9\\\\ 0\.8\\\\ 0\.7\\end\{array\}\\right\]\\\\\[15\.0694pt\] \[0\\;0\\;0\-\\\!0\.8\\;0\\;0\\;0\\;0\.2\]\{\\bm\{p\}\}=0\\\\\[2\.15277pt\] \[1\\;1\\;1\\;1\\;1\\;1\\;1\\;1\]\{\\bm\{p\}\}=1,\\;\\;\{\\bm\{p\}\}\\geq\{\\bm\{0\}\}\\end\{array\}\\right\.\\right\\\}\(13\)where𝒑=\(p000,…,p111\)\{\\bm\{p\}\}=\(p\_\{000\},\\ldots,p\_\{111\}\)\. If desired, probability ranges rather than point values can be specified in \([12](https://arxiv.org/html/2607.15532#Ch0.E12)\) while preserving the linear structure of the problem\.

### 2\.2Column Generation

A difficulty with problem \([12](https://arxiv.org/html/2607.15532#Ch0.E12)\) is that it contains2n2^\{n\}variables, wherennis the number of atomic propositionsxix\_\{i\}\. One might think that this makes the problem computationally intractable, and Nilsson suggests as much in[Nil93](https://arxiv.org/html/2607.15532#bib.bib110)\. However, the solution techniquecolumn generation, well known to the optimization community, is designed for just such cases\. It allows one to solve the problem by means of the simplex method while generating only a small fraction of the columns in matricesAAandBB, and thereby using only a small fraction of the variables in𝒑\{\\bm\{p\}\}\.

Column generation is readily applied to probabilistic logic, as initially observed in[Bru88](https://arxiv.org/html/2607.15532#bib.bib27);[GeoKavPap88](https://arxiv.org/html/2607.15532#bib.bib54);[Hoo88a](https://arxiv.org/html/2607.15532#bib.bib64);[JauHanAra91](https://arxiv.org/html/2607.15532#bib.bib75);[KavPap90](https://arxiv.org/html/2607.15532#bib.bib82)\. It begins with a restriction of \([12](https://arxiv.org/html/2607.15532#Ch0.E12)\) in whichAAandBBcontain only a few columns\. It associates dual variables𝒖\{\\bm\{u\}\},𝒗\{\\bm\{v\}\}, andα\\alphawith the constraintsA​𝒑=𝝅A\{\\bm\{p\}\}=\{\\bm\{\\pi\}\},B​𝒑=𝟎B\{\\bm\{p\}\}=\{\\bm\{0\}\}, and𝟏⊺​𝒑=1\{\\bm\{1\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}=1, respectively\. These dual variables, whose values are calculated in the course of the simplex method, are used to compute thereduced costof each variablepjp\_\{j\}:

cj−𝒖⊺​Aj−𝒗⊺​Bj−αc\_\{j\}\-\{\\bm\{u\}\}^\{\\intercal\}A\_\{j\}\-\{\\bm\{v\}\}^\{\\intercal\}B\_\{j\}\-\\alpha\(14\)where\(cj,Aj,Bj,1\)\(c\_\{j\},A\_\{j\},B\_\{j\},1\)is the column of\(𝒄⊺,A,B,𝟏⊺\)\(\{\\bm\{c\}\}^\{\\intercal\},A,B,\{\\bm\{1\}\}^\{\\intercal\}\)corresponding topjp\_\{j\}\. Supposing for the moment that we are solving the minimization problem, each iteration of the simplex method selects a new column\(cj,Aj,Bj,1\)\(c\_\{j\},A\_\{j\},B\_\{j\},1\)with a negative reduced cost for inclusion in the problem \(when maximizing, a positive reduced cost is desired\)\. If no such column remains, an optimal solution has been found, at which point it is likely that only a small fraction of the columns in\(𝒄⊺,A,B,𝟏⊺\)\(\{\\bm\{c\}\}^\{\\intercal\},A,B,\{\\bm\{1\}\}^\{\\intercal\}\)have been selected\.

The problem of finding apjp\_\{j\}with a negative reduced cost, known as thepricing problem, can be solved by minimizing \([14](https://arxiv.org/html/2607.15532#Ch0.E14)\) over all columnsjj\. The nature of the pricing problem is best illustrated in the example\. A column of\(𝒄⊺,A,B,𝟏⊺\)\(\{\\bm\{c\}\}^\{\\intercal\},A,B,\{\\bm\{1\}\}^\{\\intercal\}\)can be represented as\(y0,y1,y2,y3,z1−0\.8​w1,1\)\(y\_\{0\},y\_\{1\},y\_\{2\},y\_\{3\},z\_\{1\}\\\!\-\\\!0\.8w\_\{1\},1\), where the 0–1 variablesyiy\_\{i\},z1z\_\{1\}andw1w\_\{1\}are defined by

y0≡x3y1≡x1y2≡\(x1⊃x2\)y3≡\(x2⊃x3\)z1≡\(x1∧x2∧x3\)w1≡\(x2∧x3\)\\begin\{array\}\[\]\{l\}y\_\{0\}\\equiv x\_\{3\}\\\\ y\_\{1\}\\equiv x\_\{1\}\\\\ y\_\{2\}\\equiv\(x\_\{1\}\\supset x\_\{2\}\)\\\\ y\_\{3\}\\equiv\(x\_\{2\}\\supset x\_\{3\}\)\\\\ z\_\{1\}\\equiv\(x\_\{1\}\\wedge x\_\{2\}\\wedge x\_\{3\}\)\\\\ w\_\{1\}\\equiv\(x\_\{2\}\\wedge x\_\{3\}\)\\end\{array\}\(15\)The pricing problem can now be stated as minimizing

y0−\(u1​y1\+u2​y2\+u3​y3\)−v1​\(z1−0\.8​w1\)−αy\_\{0\}\-\(u\_\{1\}y\_\{1\}\+u\_\{2\}y\_\{2\}\+u\_\{3\}y\_\{3\}\)\-v\_\{1\}\(z\_\{1\}\-0\.8w\_\{1\}\)\-\\alpha\(16\)subject to \([15](https://arxiv.org/html/2607.15532#Ch0.E15)\), which is a special case of the maximum satisfiability problem\. Solution of this problem yields a column with the smallest reduced cost, given by \([16](https://arxiv.org/html/2607.15532#Ch0.E16)\)\. In practice, the problem is first solved by a fast heuristic method\. If this fails to yield a negative reduced cost, the problem is solved to optimality to confirm that no columns with a negative reduced cost remain\. The simplex method terminates when this is confirmed\.

One way to solve the pricing problem to optimality is to formulate it as a 0–1 programming problem as proposed in[Hoo88a](https://arxiv.org/html/2607.15532#bib.bib64), which allows one to take advantage of powerful integer programming solvers\. The formulas in \([15](https://arxiv.org/html/2607.15532#Ch0.E15)\) are converted to linear equations and inequalities, and \([14](https://arxiv.org/html/2607.15532#Ch0.E14)\) then optimized subject to these constraints\. Conversion is straightforward\. For example,y0≡x3y\_\{0\}\\equiv x\_\{3\}becomes simplyy0=x3y\_\{0\}=x\_\{3\}, and the remaining formulas are expressed in conjunctive normal form before conversion to inequalities\. For instance, formulay2≡\(x1⊃x2\)y\_\{2\}\\equiv\(x\_\{1\}\\supset x\_\{2\}\)becomes the conjunction of logical clauses

¬y2∨¬x1∨x2,y2∨x1,y2∨¬x2\\neg y\_\{2\}\\\!\\vee\\\!\\neg x\_\{1\}\\\!\\vee\\\!x\_\{2\},\\;\\;\\;y\_\{2\}\\\!\\vee\\\!x\_\{1\},\\;\\;\\;y\_\{2\}\\\!\\vee\\\!\\neg x\_\{2\}which in turn become the three inequalities

\(1−y2\)\+\(1−x1\)\+x2≥1,y2\+x1≥1,y2\+\(1−x2\)≥1\(\\\!1\-\\\!y\_\{2\}\)\+\(1\\\!\-\\\!x\_\{1\}\)\+x\_\{2\}\\geq 1,\\;\\;\\;y\_\{2\}\+x\_\{1\}\\geq 1,\\;\\;\\;y\_\{2\}\+\(1\\\!\-\\\!x\_\{2\}\)\\geq 1
Another approach is to formulate the pricing problem as pseudo\-Boolean optimization, as proposed in[Bru88](https://arxiv.org/html/2607.15532#bib.bib27);[JauHanAra91](https://arxiv.org/html/2607.15532#bib.bib75)\. In the example, this is accomplished by replacing variablesyiy\_\{i\},z1z\_\{1\}, andw1w\_\{1\}in the objective function \([16](https://arxiv.org/html/2607.15532#Ch0.E16)\) with possibly nonlinear expressions in terms of thexix\_\{i\}s as follows:

y0←x3y1←x1y2←1−x1​x2y3←1−x2​x3z1←x1​x2​x3w1←x2​x3\\begin\{array\}\[\]\{l\}y\_\{0\}\\leftarrow x\_\{3\}\\\\ y\_\{1\}\\leftarrow x\_\{1\}\\\\ y\_\{2\}\\leftarrow 1\-x\_\{1\}x\_\{2\}\\\\ y\_\{3\}\\leftarrow 1\-x\_\{2\}x\_\{3\}\\\\ z\_\{1\}\\leftarrow x\_\{1\}x\_\{2\}x\_\{3\}\\\\ w\_\{1\}\\leftarrow x\_\{2\}x\_\{3\}\\end\{array\}Then \([16](https://arxiv.org/html/2607.15532#Ch0.E16)\) is minimized without constraints, using a heuristic method, or when a proof of optimality is required, using a pseudo\-Boolean optimization method such as those described in[BorHam02](https://arxiv.org/html/2607.15532#bib.bib25)\.

Subsequent developments in computational methods can be found in[HanPer08](https://arxiv.org/html/2607.15532#bib.bib63);[KliPar09](https://arxiv.org/html/2607.15532#bib.bib85);[KliPar11](https://arxiv.org/html/2607.15532#bib.bib86)\. Some computationally easy cases of probabilistic logic are described in[AndHoo97](https://arxiv.org/html/2607.15532#bib.bib4);[AndPre01](https://arxiv.org/html/2607.15532#bib.bib6)\.

### 2\.3Extensions

Problem \([12](https://arxiv.org/html/2607.15532#Ch0.E12)\) is easily modified to derive the range of a conditional probability\. The desired conditional probability can be written𝒄⊺​𝒑/𝒅⊺​𝒑\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}/\{\\bm\{d\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}for suitable coefficient vectors𝒄\{\\bm\{c\}\}and𝒅\{\\bm\{d\}\}\. This results in the linear\-fractional programming problem

min/max⁡\{𝒄⊺​𝒑𝒅⊺​𝒑\|A​𝒑=𝝅,B​𝒑=𝟎,1⊺​𝒑=1,𝒑≥𝟎\}\\min/\\max\\;\\Big\\\{\\frac\{\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}\}\{\{\\bm\{d\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}\}\\;\\Big\|\\;A\{\\bm\{p\}\}=\{\\bm\{\\pi\}\},\\;B\{\\bm\{p\}\}=\{\\bm\{0\}\},\\;\{\\bm\{1\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}=1,\\;\{\\bm\{p\}\}\\geq\{\\bm\{0\}\}\\Big\\\}\(17\)A simple change of variable, and the introduction of a scalar variablett, transforms \([17](https://arxiv.org/html/2607.15532#Ch0.E17)\) to a linear programming problem[ChaCoo62](https://arxiv.org/html/2607.15532#bib.bib32)\. By setting𝒒=t​𝒑\{\\bm\{q\}\}=t\{\\bm\{p\}\}, it is easily seen that \([17](https://arxiv.org/html/2607.15532#Ch0.E17)\) is equivalent to

min/max⁡\{𝒄⊺​𝒒\|A​𝒒=t​𝝅,B​𝒒=𝟎,1⊺​𝒒=t,𝒅⊺​𝒒=1,𝒒≥𝟎,t≥0\}\\min/\\max\\;\\big\\\{\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{q\}\}\\;\\big\|\\;A\{\\bm\{q\}\}=t\{\\bm\{\\pi\}\},\\;B\{\\bm\{q\}\}=\{\\bm\{0\}\},\\;\{\\bm\{1\}\}^\{\\intercal\}\{\\\!\\bm\{q\}\}=t,\\;\{\\bm\{d\}\}^\{\\intercal\}\{\\\!\\bm\{q\}\}=1,\\;\{\\bm\{q\}\}\\geq\{\\bm\{0\}\},\\;t\\geq 0\\big\\\}\(18\)When a solution\(𝒒,t\)\(\{\\bm\{q\}\},t\)of \([18](https://arxiv.org/html/2607.15532#Ch0.E18)\) is found, the corresponding solution of \([17](https://arxiv.org/html/2607.15532#Ch0.E17)\) is𝒑=𝒒/t\{\\bm\{p\}\}=\{\\bm\{q\}\}/t, with optimal value𝒄⊺​𝒑/𝒅⊺​𝒑=𝒄⊺​𝒒\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}/\{\\bm\{d\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}=\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{q\}\}\. As an illustration, suppose we wish to find a probability range forPr​\(x3\|x1,x2\)\\mathrm\{Pr\}\(x\_\{3\}\|x\_\{1\},x\_\{2\}\)in the above example\. In this case,

𝒄⊺​𝒑𝒅⊺​𝒑=\[0 0 0 0 0 0 0 1\]​𝒑\[0 0 0 0 0 0 1 1\]​𝒑\\frac\{\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}\}\{\{\\bm\{d\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}\}=\\frac\{\[0\\;0\\;0\\;0\\;0\\;0\\;0\\;1\]\{\\bm\{p\}\}\}\{\[0\\;0\\;0\\;0\\;0\\;0\\;1\\;1\]\{\\bm\{p\}\}\}The deduced interval forP​r​\(x3\|x1,x2\)=𝒄⊺​𝒒Pr\(x\_\{3\}\|x\_\{1\},x\_\{2\}\)=\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{q\}\}is a point value, namely 4/7\.

A second extension arises when the given probabilitiesπi\\pi\_\{i\}are intervals rather than point values\. Then the inference problem \([12](https://arxiv.org/html/2607.15532#Ch0.E12)\) is

min/max⁡\{𝒄⊺​𝒑\|𝝅lo≤A​𝒑≤𝝅hi,B​𝒑=𝟎,1⊺​𝒑=1,𝒑≥𝟎\}\\min/\\max\\;\\big\\\{\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}\\;\\big\|\\;\{\\bm\{\\pi\}\}^\{\\mathrm\{lo\}\}\\leq A\{\\bm\{p\}\}\\leq\{\\bm\{\\pi\}\}^\{\\mathrm\{hi\}\},\\;B\{\\bm\{p\}\}=\{\\bm\{0\}\},\\;\{\\bm\{1\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}=1,\\;\{\\bm\{p\}\}\\geq\{\\bm\{0\}\}\\big\\\}\(19\)A probability range for𝒄⊺​𝒑\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}can be derived by linear programming as before, but it might be regarded as too conservative\. Probabilities at the ends of a range\[πilo,πihi\]\[\\pi^\{\\mathrm\{lo\}\}\_\{i\},\\pi^\{\\mathrm\{hi\}\}\_\{i\}\]assigned to a premise are generally less likely to be the true probability than those near the middle\. Probabilities at the ends of the derived range may therefore be extremely unlikely, because they typically occur only when a number of the given probabilities are near the ends of their intervals\. The derived range can therefore be misleadingly wide\.

One possible remedy for this problem is to derive a “most likely” probability for𝒄⊺​𝒑\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}by computing a maximum entropy solution[Kan89](https://arxiv.org/html/2607.15532#bib.bib81)\. Yet this poses a difficult nonlinear optimization problem[HanJau00](https://arxiv.org/html/2607.15532#bib.bib62), and it is equally misleading, because the true probability of the inferred proposition may be quite far from its most likely value\. Another remedy, described in[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31), is to specify a second\-order probability distribution over each probability interval\[πilo,πihi\]\[\\pi^\{\\mathrm\{lo\}\}\_\{i\},\\pi\_\{i\}^\{\\mathrm\{hi\}\}\]to indicate that probabilities near the middle of the interval are more likely\. To preserve the linearity of the optimization problem, we can suppose the logarithm of the second\-order probability density function is piecewise linear and therefore the lower envelope of a set of lines:

log⁡Pr​\(πi=ρ\)=mink=1,…,ki⁡\{αi​k​ρ\+βi​k\}\\log\\mathrm\{Pr\}\(\\pi\_\{i\}=\\rho\)=\\min\_\{k=1,\\ldots,k\_\{i\}\}\\\!\\\{\\alpha\_\{ik\}\\rho\+\\beta\_\{ik\}\\\}LetAiA^\{i\}be rowiiofAA, which corresponds to propositionii\. Assuming independence of the second order probabilities, the logarithm of the joint probability that themmpropositions have probabilitiesA1​𝒑,…,Am​𝒑A^\{1\}\{\\bm\{p\}\},\\ldots,A^\{m\}\{\\bm\{p\}\}is

∑i=1mmink=1,…,ki⁡\{αi​k​Ai​𝒑\+βi​k\}\\sum\_\{i=1\}^\{m\}\\min\_\{k=1,\\ldots,k\_\{i\}\}\\\!\\\{\\alpha\_\{ik\}A^\{i\}\{\\bm\{p\}\}\+\\beta\_\{ik\}\\\}\(20\)To eliminate solutions that are extremely unlikely, one can impose a lower boundLLon \([20](https://arxiv.org/html/2607.15532#Ch0.E20)\)\. The probabilistic inference problem becomes the linear programming problem

min/max\{𝒄⊺𝒑\|∑i=1mℓi≥L,ℓi≤αi​k​Ai​𝒑\+βi​k,k=1,…,ki,i=1,…,m𝝅lo≤A​𝒑≤𝝅hi,B​𝒑=𝟎,1⊺​𝒑=1,𝒑≥𝟎\}\\min/\\max\\;\\left\\\{\{\\bm\{c\}\}^\{\\\!\\intercal\}\{\\\!\\bm\{p\}\}\\;\\left\|\\begin\{array\}\[\]\{l\}\\sum\_\{i=1\}^\{m\}\\ell\_\{i\}\\geq L,\\;\\ell\_\{i\}\\leq\\alpha\_\{ik\}A^\{i\}\{\\bm\{p\}\}\+\\beta\_\{ik\},\\;k=1,\\ldots,k\_\{i\},\\;i=1,\\ldots,m\\\\\[3\.01385pt\] \{\\bm\{\\pi\}\}^\{\\mathrm\{lo\}\}\\leq A\{\\bm\{p\}\}\\leq\{\\bm\{\\pi\}\}^\{\\mathrm\{hi\}\},\\;B\{\\bm\{p\}\}=\{\\bm\{0\}\},\\;\{\\bm\{1\}\}^\{\\intercal\}\{\\\!\\bm\{p\}\}=1,\\;\{\\bm\{p\}\}\\geq\{\\bm\{0\}\}\\end\{array\}\\right\.\\right\\\}which can again be solved by column generation\. The probability range can now be reduced to a more realistic interval by increasingLL\. Second\-order distributions of the conditional probabilities can be similarly accommodated\. A similar model in[AndHoo96](https://arxiv.org/html/2607.15532#bib.bib5)shows how to assign probabilities point values that are uncertain, where the degree of uncertainty is based on information from several sources\.

### 2\.4Bayesian Logic

One of our most valuable sources of probabilistic knowledge is the independence of most events\. It is convenient, for example, that the probability of an earthquake in Asia is independent of the weather in North America\. Ironically, the independence relations that make things easier to understand also make a probabilistic logic model harder to solve, because they introduce nonlinearities\. Despite this, it would be desirable to incorporate independence assumptions into Boole’s probabilistic logic\.Bayesian logicaccomplishes this by identifying the nodes of a Bayesian network with logical formulas[AndHoo94](https://arxiv.org/html/2607.15532#bib.bib3), thereby taking advantage of the elegant way in which Bayesian networks represent conditional independence\.

Figure[1](https://arxiv.org/html/2607.15532#Ch0.F1)represents a small Bayesian network for formulasf1,…,f6f\_\{1\},\\ldots,f\_\{6\}\. We can suppose that probabilities are specified \(or bounded\) for some or all of the nodes, conditioned on the node’s immediate predecessors, as in the conditional probability Pr\(f1\|f2,f3\)\(f\_\{1\}\|f\_\{2\},f\_\{3\}\)\. Marginal probabilities can be specified \(or bounded\) for nodes without predecessors, such asf5f\_\{5\}andf6f\_\{6\}\. The formulasfif\_\{i\}contain propositional variablesxjx\_\{j\}as in probabilistic logic\. The formulas are therefore related logically as well as through conditional probabilities\.

![Refer to caption](https://arxiv.org/html/2607.15532v1/x1.png)Figure 1:A simple Bayesian network\.The essence of a Bayesian network is a Markovian property according to which conditional probabilities depend only on immediate parent nodes\. Thus in Fig\.[1](https://arxiv.org/html/2607.15532#Ch0.F1), Pr\(f1\|f2,f3,f4\)=Pr​\(f1\|f2,f3\)\(f\_\{1\}\|f\_\{2\},f\_\{3\},f\_\{4\}\)=\\mathrm\{Pr\}\(f\_\{1\}\|f\_\{2\},f\_\{3\}\)\. Consequently, a set of nodes with common parents are conditionally independent when their probabilities are conditioned on their parents\. For example,f2f\_\{2\}andf3f\_\{3\}are conditionally independent givenf4f\_\{4\}, so that Pr\(f2\|f3,f4\)=Pr​\(f2\|f4\)\(f\_\{2\}\|f\_\{3\},f\_\{4\}\)=\\mathrm\{Pr\}\(f\_\{2\}\|f\_\{4\}\)\. Sincef4f\_\{4\}is a proposition, one may wish to suppose thatf2f\_\{2\}andf3f\_\{3\}are independent given¬f4\\neg f\_\{4\}as well as givenf4f\_\{4\}\. We will indicate this by writing Pr\(f2\|f3​F4\)=Pr​\(f2\|F4\)\(f\_\{2\}\|f\_\{3\}F\_\{4\}\)=\\mathrm\{Pr\}\(f\_\{2\}\|F\_\{4\}\), whereF4F\_\{4\}varies overf4f\_\{4\}and¬f4\\neg f\_\{4\}\.

An optimization model is obtained by adding network\-encoded nonlinear independence conditions to the linear programming model for probabilistic logic\. For example, the independence assumption Pr\(f2\|f3​F4\)=Pr​\(f2\|F4\)\(f\_\{2\}\|f\_\{3\}F\_\{4\}\)=\\mathrm\{Pr\}\(f\_\{2\}\|F\_\{4\}\)is captured by the constraints

Pr​\(f2,f3,F4\)​Pr​\(F4\)=Pr​\(f2,F4\)​Pr​\(f3,F4\),for​F4=f4,¬f4\\mathrm\{Pr\}\(f\_\{2\},f\_\{3\},F\_\{4\}\)\\mathrm\{Pr\}\(F\_\{4\}\)=\\mathrm\{Pr\}\(f\_\{2\},F\_\{4\}\)\\mathrm\{Pr\}\(f\_\{3\},F\_\{4\}\),\\;\\;\\mbox\{for\}\\;F\_\{4\}=f\_\{4\},\\neg f\_\{4\}\(21\)where Pr\(f2,f3,F4\)\(f\_\{2\},f\_\{3\},F\_\{4\}\)is the joint probability off2f\_\{2\},f3f\_\{3\}, andF4F\_\{4\}\. Such constraints are not only nonlinear but can grow exponentially in number\. If the probabilities are conditioned on several formulas, one must write constraints for all true\-false combinations of these formulas\.

Fortunately, it is shown in[AndHoo94](https://arxiv.org/html/2607.15532#bib.bib3);[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31)that the number of constraints is substantially limited in many networks\. The idea is illustrated in Figs\.[2](https://arxiv.org/html/2607.15532#Ch0.F2)and[3](https://arxiv.org/html/2607.15532#Ch0.F3)\. To compute bounds on the probability of the rightmost node, the number of independence constraints is at worst exponential in the size of the largestextended ancestral setof that node\. Figure[2](https://arxiv.org/html/2607.15532#Ch0.F2)shows the ancestral sets, and Fig\.[3](https://arxiv.org/html/2607.15532#Ch0.F3)the extended ancestral sets\. The ancestral sets are defined recursively in terms of parent sets\. Given a setSSof nodes, the parent sets ofSSare obtained by identifying the setS′S^\{\\prime\}of nodes outsideSSthat are immediate predecessors of some node inSS, and then splittingS′S^\{\\prime\}into maximal dependent subsets\. The ancestral sets of a node are its parent sets, the parent sets of its parent sets and so forth\. An extended ancestral set consists of an ancestral set augmented by the nodes in its parent sets\.

![Refer to caption](https://arxiv.org/html/2607.15532v1/x2.png)Figure 2:Ancestral sets of the rightmost node\.![Refer to caption](https://arxiv.org/html/2607.15532v1/x3.png)Figure 3:Extended ancestral sets of the rightmost node\.A variation of Bayesian logic was recently proposed for alogical credal network[MarQiaGraBhaBarGaoRieSah22](https://arxiv.org/html/2607.15532#bib.bib99)\. Credal networks are modified Bayesian networks in which probabilities are specified in various imprecise ways, generalizing the intervallic specifications used here\. A logical credal network associates logical formulas with nodes as does Bayesian logic\. In[MarQiaGraBhaBarGaoRieSah22](https://arxiv.org/html/2607.15532#bib.bib99), the Markovian property of conventional Bayesian networks is replaced by a modified property that permits the network to contain cycles\. Exact and heuristic solution methods for computing probability bounds in logical credal networks are described in[CozMarLeeGraRieBha24](https://arxiv.org/html/2607.15532#bib.bib41);[MarLeeBhaCozGra24](https://arxiv.org/html/2607.15532#bib.bib98);[MarQiaGraBhaBarGaoRieSah22](https://arxiv.org/html/2607.15532#bib.bib99)\. Credal networks in general, including optimization methods for solving them, are comprehensively surveyed in[MauCoz20](https://arxiv.org/html/2607.15532#bib.bib100)\. Integer programming methods are described in[MaudeCamBenZaf12](https://arxiv.org/html/2607.15532#bib.bib101)\.

## 3Belief Logics

Like probabilistic logic, a logic of belief functions distributes probability mass over subsets of possible worlds\. It differs in that the probability mass indicates the degree of evidence for, or credibility of, propositions rather than their probability in a classical sense\. It might therefore be referred to as evidence mass\. A further difference is that, whereas assigning a specific probability mass to a set of possible worldsfixesthe total probability of those worlds, assigning a specific evidence massadds tothe total evidence for those worlds\.

We begin below with a basic belief logic and its linear programming formulation\. Unlike probabilistic logic, it does not contain exponentially many variables and therefore has no need of column generation for its solution\. We then describe how Dempster\-Shafer theory augments this basic model with a rule for combining possibly contradictory evidence sources \(Dempster’s combination rule\)\. Following this, we drop the nonlinear independence assumption of Dempster\-Shafer theory, while retaining Dempster’s combination rule, to permit a linear programming formulation\.

### 3\.1Logic of Belief Functions

Belief functions can be illustrated by a small example, taken from[AndHoo94](https://arxiv.org/html/2607.15532#bib.bib3)\. Suppose we have propositionsx1x\_\{1\},x2x\_\{2\}, andx1∧x2x\_\{1\}\\\!\\wedge\\\!x\_\{2\}, which correspond to possible world setsS1=\{\(1,0\),\(1,1\)\}S\_\{1\}=\\\{\(1,0\),\(1,1\)\\\},S2=\{\(0,1\),\(1,1\)\}S\_\{2\}=\\\{\(0,1\),\(1,1\)\\\}, andS0=\{\(1,1\)\}S\_\{0\}=\\\{\(1,1\)\\\}, respectively\. We have some evidence forx1x\_\{1\}andx2x\_\{2\}and wish to determine the implied evidential support forx1∧x2x\_\{1\}\\\!\\wedge\\\!x\_\{2\}\. Letm​\(S1\)m\(S\_\{1\}\)be the fraction of available evidence that specifically supports the propositionx1x\_\{1\}corresponding to setS1S\_\{1\}, and similarly form​\(S2\)m\(S\_\{2\}\)andm​\(S0\)m\(S\_\{0\}\)\. We also suppose thatm​\(Θ\)m\(\\Theta\)is the fraction of evidence that supports no particular proposition, whereΘ\\Thetais the set of all possible worlds\. Dempster and Shafer refer tom​\(Si\)m\(S\_\{i\}\)as a “basic probability number,” but we will refer to it as anevidence allotment\. We must havem​\(Θ\)\+∑im​\(Si\)=1m\(\\Theta\)\+\\sum\_\{i\}m\(S\_\{i\}\)=1\.

The accumulated evidence forx1x\_\{1\}consists of the evidence that supportsx1x\_\{1\}and any propositions that implyx1x\_\{1\}, in this casex1∧x2x\_\{1\}\\\!\\wedge\\\!x\_\{2\}\. Thus the total support for setS1S\_\{1\}isBel\(S1\)=m​\(S0\)\+m​\(S1\)\(S\_\{1\}\)=m\(S\_\{0\}\)\+m\(S\_\{1\}\), whereBelis abelief function\. The belief valuesBel\(S2\)\(S\_\{2\}\)andBel\(S0\)\(S\_\{0\}\)are similarly defined\. If we are given thatBel\(S1\)=0\.9\(S\_\{1\}\)=0\.9andBel\(S2\)=0\.8\(S\_\{2\}\)=0\.8, we have

m​\(S0\)\+m​\(S1\)=0\.9m​\(S0\)\+m​\(S2\)=0\.8m​\(S0\)\+m​\(S1\)\+m​\(S2\)\+m​\(Θ\)=1m​\(Si\)≥0,all​i\\begin\{array\}\[\]\{l\}m\(S\_\{0\}\)\+m\(S\_\{1\}\)=0\.9\\\\ m\(S\_\{0\}\)\+m\(S\_\{2\}\)=0\.8\\\\ m\(S\_\{0\}\)\+m\(S\_\{1\}\)\+m\(S\_\{2\}\)\+m\(\\Theta\)=1\\\\ m\(S\_\{i\}\)\\geq 0,\\;\\mbox\{all\}\\;i\\end\{array\}\(22\)The evidence allotmentsm​\(Si\)m\(S\_\{i\}\)must satisfy these constraints\. Since evidence is allocated to no proper subset ofS0S\_\{0\}, the evidential support forx1∧x2x\_\{1\}\\\!\\wedge\\\!x\_\{2\}isBel\(S0\)=m​\(S0\)\(S\_\{0\}\)=m\(S\_\{0\}\)\. This support level must fall in the range obtained by maximizing and minimizingm​\(S0\)m\(S\_\{0\}\)subject to \([22](https://arxiv.org/html/2607.15532#Ch0.E22)\), which yields the interval\[0\.7,0\.8\]\[0\.7,0\.8\]\.

In general, suppose we are given belief valuesBel\(Si\)\(S\_\{i\}\)fori=1,…,mi=1,\\ldots,m\. The linear programming model is

min/max\{∑S⊆S0m\(S\)\|∑S⊆Sim​\(S\)=𝐵𝑒𝑙​\(Si\),i=1,…,mm​\(Θ\)\+∑i=1mm​\(Si\)=1m​\(Θ\)≥0,m​\(Si\)≥0,i=1,…,m\}\\min/\\max\\;\\left\\\{\\sum\_\{S\\subseteq S\_\{0\}\}\\\!m\(S\)\\;\\left\|\\;\\begin\{array\}\[\]\{l\}\{\\displaystyle\\sum\_\{S\\subseteq S\_\{i\}\}\\\!m\(S\)=\\mathrm\{\\it Bel\}\(S\_\{i\}\),\\;i=1,\\ldots,m\}\\\\\[\-4\.30554pt\] \{\\displaystyle m\(\\Theta\)\+\\sum\_\{i=1\}^\{m\}m\(S\_\{i\}\)=1\}\\\\\[12\.91663pt\] m\(\\Theta\)\\geq 0,\\;m\(S\_\{i\}\)\\geq 0,\\;i=1,\\ldots,m\\end\{array\}\\right\.\\right\\\}Note that possible worlds do not play an explicit role in this model\. The model therefore grows only linearly with the number of propositions assigned belief values and can therefore be solved very rapidly\. In practice, set inclusionS⊆SiS\\\!\\subseteq\\\!S\_\{i\}can be interpreted as logical entailment between the propositions corresponding toSSandSiS\_\{i\}\.

### 3\.2Dempster\-Shafer Theory

The belief logic of the previous section supposes that all available evidence has been pooled, so that evidence allotmentsm​\(S\)m\(S\)can be made on that basis\. It also recognizes that the belief level of a given proposition may be underdetermined by available evidence\. Dempster\-Shafer theory[Dem67](https://arxiv.org/html/2607.15532#bib.bib43);[Dem68](https://arxiv.org/html/2607.15532#bib.bib44);[Sha76](https://arxiv.org/html/2607.15532#bib.bib118)addresses the issue of how to combine different sources of evidence to obtain a single evidence allotment functionm​\(⋅\)m\(\\cdot\)\. It accomplishes this in such a way as to obtain point values for the functionm​\(⋅\)m\(\\cdot\), and therefore for any belief valueBel\(S0\)\(S\_\{0\}\)one wishes to deduce from the evidence base\. The method rests on rather strong independence and normalization assumptions\. However, one can drop the independence assumption and deduce intervals form​\(⋅\)m\(\\cdot\), rather than point values, by means of linear\-fractional programming\.

We again illustrate with an example\. As before, the propositions of interest arex1x\_\{1\},x2x\_\{2\}, andx1∧x2x\_\{1\}\\\!\\wedge x\_\{2\}, corresponding to setsS1,S2S\_\{1\},S\_\{2\}andS0S\_\{0\}, and we wish to deduce the level of evidence forx1∧x2x\_\{1\}\\\!\\wedge x\_\{2\}\. Suppose that evidence source 1 determines an evidence allotment functionm1​\(⋅\)m\_\{1\}\(\\cdot\)by specifyingm1​\(S1\)=0\.9m\_\{1\}\(S\_\{1\}\)=0\.9andm1​\(Θ\)=0\.1m\_\{1\}\(\\Theta\)=0\.1\. Evidence source 2 specifiesm2​\(S2\)=0\.8m\_\{2\}\(S\_\{2\}\)=0\.8andm2​\(Θ\)=0\.2m\_\{2\}\(\\Theta\)=0\.2\. ThenDempter’s combination rulederives a combined allotment functionm^​\(⋅\)=m1​\(⋅\)⊗m2​\(⋅\)\\widehat\{m\}\(\\cdot\)=m\_\{1\}\(\\cdot\)\\otimes m\_\{2\}\(\\cdot\)by taking cross\-products of evidence allotments to intersecting sets as shown in Table[1](https://arxiv.org/html/2607.15532#Ch0.T1)\. This operation assumes that evidence sources are independent in some sense\. Since none of the intersections are empty, we can setm​\(⋅\)=m^​\(⋅\)m\(\\cdot\)=\\widehat\{m\}\(\\cdot\); empty intersections require renormalization, as explained below\. BecauseS0S\_\{0\}contains neither of the other sets, its belief value is simplyBel\(S0\)=m​\(S0\)=0\.72\(S\_\{0\}\)=m\(S\_\{0\}\)=0\.72\. Note that this point value lies within the interval\[0\.7,0\.8\]\[0\.7,0\.8\]that was derived forBel\(S0\)\(S\_\{0\}\)in the previous section\.

Table 1:Example of Dempster’s combination rule that does not require normalization\.In general, we have

m^​\(S\)=m1​\(S\)⊗m2​\(S\)=∑A,BS=A∩Bm1​\(A\)​m2​\(B\)\\widehat\{m\}\(S\)=m\_\{1\}\(S\)\\otimes m\_\{2\}\(S\)=\\hskip\-4\.30554pt\\sum\_\{\\begin\{subarray\}\{c\}A,B\\\\ S=A\\cap B\\end\{subarray\}\}\\hskip\-5\.59721ptm\_\{1\}\(A\)m\_\{2\}\(B\)If there are three evidence sources, one can computem^​\(S\)\\widehat\{m\}\(S\)recursively asm^​\(S\)=m1​\(S\)⊗\(m2​\(S\)⊗m3​\(S\)\)\\widehat\{m\}\(S\)=m\_\{1\}\(S\)\\otimes\(m\_\{2\}\(S\)\\otimes m\_\{3\}\(S\)\), and similarly for more numerous sources\. If one or more intersectionsA∩BA\\cap Bare empty, we must renormalize the evidence allotments\. For example, the allotment functions shown in Table[2](https://arxiv.org/html/2607.15532#Ch0.T2)assign positive evidence to contradictory propositions, sinceS¯1\\overline\{S\}\_\{1\}is the complement ofS1S\_\{1\}\. Since there can be no evidence for a logical contradiction, we assignm​\(S1∩S¯1\)=m​\(∅\)=0m\(S\_\{1\}\\\!\\cap\\overline\{S\}\_\{1\}\)=m\(\\varnothing\)=0\. We now renormalize the remaining evidence allotments, yieldingm​\(S1\)=13m\(S\_\{1\}\)=\\frac\{1\}\{3\},m​\(S¯1\)=16m\(\\overline\{S\}\_\{1\}\)=\\frac\{1\}\{6\}, andm​\(Θ\)=12m\(\\Theta\)=\\frac\{1\}\{2\}\. More generally,

m​\(S\)=\{m^​\(S\)1−m^​\(∅\),if​S≠∅0,if​S=∅m\(S\)=\\left\\\{\\begin\{array\}\[\]\{ll\}\{\\displaystyle\\frac\{\\widehat\{m\}\(S\)\}\{1\-\\widehat\{m\}\(\\varnothing\)\},\}&\\mbox\{if\}\\;S\\neq\\varnothing\\\\\[8\.61108pt\] 0,&\\mbox\{if\}\\;S=\\varnothing\\end\{array\}\\right\.In this manner, Dempster’s combination rule can reconcile conflicting evidence sources, although one might question whether renormalization is a justifiable method for doing so\. Finally, the belief value ofS0S\_\{0\}is simply

𝐵𝑒𝑙​\(S0\)=∑S⊆S0m​\(S\)\\mathrm\{\\it Bel\}\(S\_\{0\}\)=\\sum\_\{S\\subseteq S\_\{0\}\}\\hskip\-2\.15277ptm\(S\)
Table 2:Example of Dempster’s combination rule that requires normalization\.
### 3\.3Belief Logic with Dempster’s Combination Rule

The independence assumption in Dempster\-Shafer theory can be dropped if we are content with inferred intervals rather than point values for the evidence allotment functionm​\(⋅\)m\(\\cdot\)\. This yields a belief logic similar to that described in Section[3\.1](https://arxiv.org/html/2607.15532#Ch0.S3.SS1), but with a mechanism for combining evidence sources\. It also permits a linear programming model\.

In the example of Table[1](https://arxiv.org/html/2607.15532#Ch0.T1), we observe that

m^​\(S1∩S2\)\+m^​\(S1\)=0\.9m^​\(S2\)\+m^​\(Θ\)=0\.1m^​\(S1∩S2\)\+m^​\(S2\)=0\.8m^​\(S1\)\+m^​\(Θ\)=0\.2m^​\(S1\),m^​\(S2\),m^​\(S1∩S2\),m^​\(Θ\)≥0\\begin\{array\}\[\]\{l\}\\widehat\{m\}\(S\_\{1\}\\\!\\cap\\\!S\_\{2\}\)\+\\widehat\{m\}\(S\_\{1\}\)=0\.9\\\\\[1\.29167pt\] \\widehat\{m\}\(S\_\{2\}\)\+\\widehat\{m\}\(\\Theta\)=0\.1\\\\\[1\.29167pt\] \\widehat\{m\}\(S\_\{1\}\\\!\\cap\\\!S\_\{2\}\)\+\\widehat\{m\}\(S\_\{2\}\)=0\.8\\\\\[1\.29167pt\] \\widehat\{m\}\(S\_\{1\}\)\+\\widehat\{m\}\(\\Theta\)=0\.2\\\\\[1\.29167pt\] \\widehat\{m\}\(S\_\{1\}\),\\widehat\{m\}\(S\_\{2\}\),\\widehat\{m\}\(S\_\{1\}\\\!\\cap\\\!S\_\{2\}\),\\widehat\{m\}\(\\Theta\)\\geq 0\\end\{array\}\(23\)where any one of the four equations is redundant of the others\. By minimizing and maximizingm^​\(S1∩S2\)\\widehat\{m\}\(S\_\{1\}\\\!\\cap\\\!S\_\{2\}\)subject to \([23](https://arxiv.org/html/2607.15532#Ch0.E23)\), we obtain the range\[0\.7,0\.8\]\[0\.7,0\.8\]form^​\(S1∩S2\)\\widehat\{m\}\(S\_\{1\}\\\!\\cap\\\!S\_\{2\}\), which contains the point value 0\.72 obtained under an independence assumption\. A similar approach works when renormalization is necessary\. From Table[2](https://arxiv.org/html/2607.15532#Ch0.T2), we have

m^​\(∅\)\+m^​\(S1\)=0\.4m^​\(S¯1\)\+m^​\(Θ\)=0\.6m^​\(∅\)\+m^​\(S¯1\)=0\.25m^​\(S1\)\+m^​\(Θ\)=0\.75m^​\(S1\),m^​\(S¯1\),m^​\(∅\),m^​\(Θ\)≥0\\begin\{array\}\[\]\{l\}\\widehat\{m\}\(\\varnothing\)\+\\widehat\{m\}\(S\_\{1\}\)=0\.4\\\\\[1\.29167pt\] \\widehat\{m\}\(\\overline\{S\}\_\{1\}\)\+\\widehat\{m\}\(\\Theta\)=0\.6\\\\\[1\.29167pt\] \\widehat\{m\}\(\\varnothing\)\+\\widehat\{m\}\(\\overline\{S\}\_\{1\}\)=0\.25\\\\\[1\.29167pt\] \\widehat\{m\}\(S\_\{1\}\)\+\\widehat\{m\}\(\\Theta\)=0\.75\\\\\[1\.29167pt\] \\widehat\{m\}\(S\_\{1\}\),\\widehat\{m\}\(\\overline\{S\}\_\{1\}\),\\widehat\{m\}\(\\varnothing\),\\widehat\{m\}\(\\Theta\)\\geq 0\\end\{array\}\(24\)Sincem​\(S1\)=m^​\(S1\)/\(1−m^​\(∅\)\)m\(S\_\{1\}\)=\\widehat\{m\}\(S\_\{1\}\)/\(1\-\\widehat\{m\}\(\\varnothing\)\), we can obtain a range form​\(S1\)m\(S\_\{1\}\)by minimizing and maximizing this fraction subject to \([24](https://arxiv.org/html/2607.15532#Ch0.E24)\)\. This can be accomplished by fractional\-linear programming, yielding the interval\[0\.2,0\.4\]\[0\.2,0\.4\], which contains the point valuem​\(S1\)=13m\(S\_\{1\}\)=\\frac\{1\}\{3\}derived above\.

In general, a range form​\(S0\)m\(S\_\{0\}\), given nonemptyS0S\_\{0\}, is found as follows\. Suppose that evidence source 1 provides positive evidence mass for setsS1,…,SmS\_\{1\},\\ldots,S\_\{m\}, and evidence source 2 provides positive mass forT1,…,TnT\_\{1\},\\ldots,T\_\{n\}\. Then we wish to solve

min/max\{m^​\(S0\)1−m^​\(∅\)\|∑j=1nm^​\(Si∩Tj\)=m1​\(Si\),i=1,…,m∑i=1mm^​\(Si∩Tj\)=m2​\(Tj\),j=1,…,nm^​\(⋅\)≥0\}\\min/\\max\\;\\left\\\{\\frac\{\\widehat\{m\}\(S\_\{0\}\)\}\{1\-\\widehat\{m\}\(\\varnothing\)\}\\;\\left\|\\;\\begin\{array\}\[\]\{l\}\\sum\_\{j=1\}^\{n\}\\widehat\{m\}\(S\_\{i\}\\\!\\cap\\\!T\_\{j\}\)=m\_\{1\}\(S\_\{i\}\),\\;i=1,\\ldots,m\\\\\[4\.30554pt\] \\sum\_\{i=1\}^\{m\}\\widehat\{m\}\(S\_\{i\}\\\!\\cap\\\!T\_\{j\}\)=m\_\{2\}\(T\_\{j\}\),\\;j=1,\\ldots,n\\\\\[4\.30554pt\] \\widehat\{m\}\(\\cdot\)\\geq 0\\end\{array\}\\right\.\\right\\\}This becomes a linear programming problem after the variable changeμ​\(⋅\)=m^​\(⋅\)​t\\mu\(\\cdot\)=\\widehat\{m\}\(\\cdot\)t:

min/max\{μ\(S0\)\|∑j=1nμ​\(Si∩Tj\)=m1​\(Si\)​t,i=1,…,m∑i=1mμ​\(Si∩Tj\)=m2​\(Tj\)​t,j=1,…,mt−μ​\(∅\)=1;μ​\(⋅\),t≥0\}\\min/\\max\\;\\left\\\{\\mu\(S\_\{0\}\)\\;\\left\|\\;\\begin\{array\}\[\]\{l\}\\sum\_\{j=1\}^\{n\}\\mu\(S\_\{i\}\\\!\\cap\\\!T\_\{j\}\)=m\_\{1\}\(S\_\{i\}\)t,\\;i=1,\\ldots,m\\\\\[4\.30554pt\] \\sum\_\{i=1\}^\{m\}\\mu\(S\_\{i\}\\\!\\cap\\\!T\_\{j\}\)=m\_\{2\}\(T\_\{j\}\)t,\\;j=1,\\ldots,m\\\\\[4\.30554pt\] t\-\\mu\(\\varnothing\)=1;\\;\\;\\mu\(\\cdot\),t\\geq 0\\end\{array\}\\right\.\\right\\\}
When there are a large number of evidence sources, recursive computation ofm​\(S0\)m\(S\_\{0\}\)can become difficult\. The number of set intersections, and thus the number of sets with positive mass, can increase exponentially with the number of sources\. Methods for simplifying the computations, using a set covering optimization model, are discussed in[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31);[DugSan94](https://arxiv.org/html/2607.15532#bib.bib48)\. In any event, it is likely that only a handful of evidence sources are relevant to a given conclusion in a given application\.

A survey of algorithms for Dempster\-Shafer theory can be found in[Wil00](https://arxiv.org/html/2607.15532#bib.bib133), and a general discussion of semantics for belief logics in[HaeRomWheWil08](https://arxiv.org/html/2607.15532#bib.bib58)\. Other mathematical programming embeddings of logic, including predicate logic, are presented in[BorChaMit02](https://arxiv.org/html/2607.15532#bib.bib23);[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31)\.

## 4Nonmonotonic and Many\-Valued Logics

This section deals with two nonstandard logics that have played a role in artificial intelligence, nonmonotonic logic and many\-valued logic\. It shows how optimization can make substantial contributions to their implementation, and even lend insight into the underlying ideas\.

Innonmonotonic logic, the addition of new facts to a knowledge base may require the withdrawal of previously inferred conclusions\. We show how integer programming can capture the semantics of default logic \(a popular variety of nonmonotonic logic\) and compute satisfying solutions\.

Many\-valued logic can assign truth values between true and false, values that may either be discrete or lie on a continuous scale\. This permits a knowledge base to indicate the degree of confidence with which propositions can be asserted\. Mixed integer/linear programming \(MILP\) is well suited to determine truth values of propositions deduced from the knowledge base\.

### 4\.1Default Logic

Indefault logic, propositions with an “unless” clause are enforced only if the unless clause is not known to be true\. This type of logic is closely related to answer set programming and negation\-as\-failure in logic programming\. A key concept in the semantics of default logic is that of astable model[GelLif88](https://arxiv.org/html/2607.15532#bib.bib53);[MarNerRem94](https://arxiv.org/html/2607.15532#bib.bib97)\. Optimization can be helpful in this context because all stable models can be identified with the assistance of integer programming[BelNerNgSub94](https://arxiv.org/html/2607.15532#bib.bib13);[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31)\.

Default logic is normally applied to a set of guarded rules having the form on the left:

P→xi​unless​G,or​¬P∨xi∨GP\\\!\\rightarrow\\\!x\_\{i\}\\;\\mbox\{unless\}\\;G,\\;\\;\\;\\mbox\{or\}\\;\\;\\;\\neg P\\vee\\\!x\_\{i\}\\vee GwherePPis a conjunction of zero or more atoms \(atomic propositions\) and logical formulaGGis the guard\. The rule is semantically equivalent to the formula on the right\. One is permitted to use the ruleP→xiP\\\!\\rightarrow\\\!x\_\{i\}in a deduction as long asGGis not known to be true\.

In this context, amodelfor a set of guarded rules is a collection of atoms that, when set to true, satisfy the rules when the remaining atoms are presumed false\. The concept of stable model can be explained with the following example\. Consider the guarded rules on the left below, which are semantically equivalent to the formulas on the right\.

x1→x2​unless​x5x1→x3​unless​\(x2∨x4\)\(x1∧x4\)→x5→x1​unless​\(x4∧x5\)¬x1∨x2∨x5¬x1∨x3∨x2∨x4¬x1∨¬x4∨x5x1∨\(x4∧x5\)\\begin\{array\}\[\]\{l\}x\_\{1\}\\\!\\rightarrow\\\!x\_\{2\}\\;\\mbox\{unless\}\\;x\_\{5\}\\\\ x\_\{1\}\\\!\\rightarrow\\\!x\_\{3\}\\;\\mbox\{unless\}\\;\(x\_\{2\}\\\!\\vee\\\!x\_\{4\}\)\\\\ \(x\_\{1\}\\\!\\wedge\\\!x\_\{4\}\)\\\!\\rightarrow\\\!x\_\{5\}\\\\ \\rightarrow\\\!x\_\{1\}\\;\\mbox\{unless\}\\;\(x\_\{4\}\\wedge x\_\{5\}\)\\end\{array\}\\hskip 21\.52771pt\\begin\{array\}\[\]\{l\}\\neg x\_\{1\}\\\!\\vee\\\!x\_\{2\}\\\!\\vee\\\!x\_\{5\}\\\\ \\neg x\_\{1\}\\\!\\vee\\\!x\_\{3\}\\\!\\vee\\\!x\_\{2\}\\\!\\vee\\\!x\_\{4\}\\\\ \\neg x\_\{1\}\\\!\\vee\\\!\\neg x\_\{4\}\\\!\\vee\\\!x\_\{5\}\\\\ x\_\{1\}\\\!\\vee\\\!\(x\_\{4\}\\\!\\wedge\\\!x\_\{5\}\)\\end\{array\}\(25\)Note that a guard can be empty, in which case the rule is always enforced\. A given model allows rules to be used when it fails to activate their guards\. For example, the model\{x1\.x2\}\\\{x\_\{1\}\.x\_\{2\}\\\}admits the rules

x1→x2\(x1∧x4\)→x5→x1\\begin\{array\}\[\]\{l\}x\_\{1\}\\\!\\rightarrow\\\!x\_\{2\}\\\\ \(x\_\{1\}\\\!\\wedge\\\!x\_\{4\}\)\\\!\\rightarrow\\\!x\_\{5\}\\\\ \\rightarrow\\\!x\_\{1\}\\end\{array\}\(26\)where \([26](https://arxiv.org/html/2607.15532#Ch0.E26)\) is known as theGelfond\-Lifschitz transformof \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\) with respect to the given model[GelLif88](https://arxiv.org/html/2607.15532#bib.bib53)\. Astablemodel is one that minimally satisfies its Gelfond\-Lifschitz \(G\-F\) transform; that is, flipping any atom from true to false would no longer satisfy the transform\. It is easily checked that\{x1,x2\}\\\{x\_\{1\},x\_\{2\}\\\}is a stable model\.

Integer programming can identify all stable models by systematically finding all minimal models of the original rule base and checking which ones are minimal for the corresponding Gelfond\-Lifschitz transform\. A minimal model for \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\), for example, is found by minimizing∑ixi\\sum\_\{i\}x\_\{i\}subject to linear inequalities that encode the logical formulas in \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\):

min\{∑ixi\|\(1−x1\)\+x2\+x3≥1\(1−x1\)\+x2\+x3\+x4≥1\(1−x1\)\+\(1−x4\)\+x5≥1x1\+x4≥1,x1\+x5≥1xi∈\{0,1\},all​i\}\\min\\;\\left\\\{\\sum\_\{i\}x\_\{i\}\\;\\left\|\\;\\begin\{array\}\[\]\{l\}\(1\\\!\-\\\!x\_\{1\}\)\+x\_\{2\}\+x\_\{3\}\\geq 1\\\\ \(1\\\!\-\\\!x\_\{1\}\)\+x\_\{2\}\+x\_\{3\}\+x\_\{4\}\\geq 1\\\\ \(1\\\!\-\\\!x\_\{1\}\)\+\(1\\\!\-\\\!x\_\{4\}\)\+x\_\{5\}\\geq 1\\\\ x\_\{1\}\+x\_\{4\}\\geq 1,\\;\\;x\_\{1\}\+x\_\{5\}\\geq 1\\\\ x\_\{i\}\\in\\\{0,1\\\},\\;\\mbox\{all\}\\;i\\end\{array\}\\right\.\\right\\\}\(27\)Rules must be converted to conjunctive normal form before encoding, as illustrated by the last rule in \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\), which is converted to\(x1∨x4\)∧\(x1∨x5\)\(x\_\{1\}\\\!\\vee\\\!x\_\{4\}\)\\wedge\(x\_\{1\}\\\!\\vee\\\!x\_\{5\}\)\. One optimal solution of \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\) is\(x1,…,x5\)=\(1,1,0,0,0\)\(x\_\{1\},\\ldots,x\_\{5\}\)=\(1,1,0,0,0\), which corresponds to the model\{x1,x2\}\\\{x\_\{1\},x\_\{2\}\\\}, already found to be stable\. Another minimal model can be found by adding the constraintx1\+x2≤1x\_\{1\}\+x\_\{2\}\\leq 1to exclude the minimal model\{x1,x2\}\\\{x\_\{1\},x\_\{2\}\\\}, whereupon solution of \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\) yields\(x1,…,x5\)=\(0,0,0,1,1\)\(x\_\{1\},\\ldots,x\_\{5\}\)=\(0,0,0,1,1\)\. This is not minimal in the G–L transform, which consists of the single rule\(x1∧x4\)→x5\(x\_\{1\}\\\!\\wedge\\\!x\_\{4\}\)\\\!\\rightarrow\\\!x\_\{5\}\. In fact, this rule is satisfied by flipping both ones to zero\. Adding the further constraintx4\+x5≤1x\_\{4\}\\\!\+\\\!x\_\{5\}\\leq 1yields a minimal model\{x1,x3,x5\}\\\{x\_\{1\},x\_\{3\},x\_\{5\}\\\}, which is not minimal in the corresponding G–L transform\. Finally, addingx1\+x3\+x5≤2x\_\{1\}\\\!\+\\\!x\_\{3\}\\\!\+\\\!x\_\{5\}\\leq 2makes \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\) infeasible\. Thus \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\) has no more minimal models, and\{x1,x2\}\\\{x\_\{1\},x\_\{2\}\\\}is its only stable model\.

Because the G–L transform is always a Horn system, unit propagation can check for minimality, with no need for integer programming at this stage\. A Horn system consists of rules of the formP→xiP\\\!\\rightarrow x\_\{i\}, wherePPis a conjunction of zero or more atoms, andxix\_\{i\}may be absent \(in which case¬P\\neg Pis asserted\)\. There is exactly one minimal model \(possibly empty\) for a Horn system, which is found by applying unit propagation and noting which atoms are fixed to true\. These atoms comprise the minimal model\. Unit propagation proceeds by finding a rule in whichPPis empty, fixing its consequentxix\_\{i\}to true, and removingxix\_\{i\}from all other antecedentsPPin the rule base\. This is repeated until no empty antecedents remain\. For example, unit propagation applied to \([26](https://arxiv.org/html/2607.15532#Ch0.E26)\) first fixesx1x\_\{1\}to true, and thenx2x\_\{2\}, whereupon the rulex4→x5x\_\{4\}\\\!\\rightarrow\\\!x\_\{5\}remains\. Thus\{x1,x2\}\\\{x\_\{1\},x\_\{2\}\\\}is the unique minimal model of \([26](https://arxiv.org/html/2607.15532#Ch0.E26)\)\. Horn systems can also be solved by linear programming and have a number of interesting polyhedral properties[ChaHoo91](https://arxiv.org/html/2607.15532#bib.bib30);[JerWan90](https://arxiv.org/html/2607.15532#bib.bib78)\.

Subsequent research on integer programming methods for answer set programming and stable semantics includes[Ben05](https://arxiv.org/html/2607.15532#bib.bib14);[LiuJanNie12](https://arxiv.org/html/2607.15532#bib.bib94);[LiuJanNie14](https://arxiv.org/html/2607.15532#bib.bib95);[OsoDiaSan17](https://arxiv.org/html/2607.15532#bib.bib111)\.

### 4\.2Many\-valued Logic

Truth values in many\-valued logic are frequently taken to be equally spaced numbers in the interval\[0,1\]\[0,1\], with larger values corresponding to greater degree of confidence\. If desired, all real values in the interval\[0,1\]\[0,1\]can be regarded as truth values\. Logical operators and connectives are semantically defined as functions of these truth values\. For example, the truth value of¬P\\neg Pisv​\(¬P\)=1−v​\(P\)v\(\\neg P\)=1\-v\(P\), wherev​\(P\)v\(P\)is the truth value ofPP\. The truth value of the conditionalP⊃QP\\supset Qis frequently defined to be

v​\(P⊃Q\)=min⁡\{1,1−v​\(P\)\+v​\(Q\)\}v\(P\\supset Q\)=\\min\\\{1,1\-v\(P\)\+v\(Q\)\\\}\(28\)
Mixed integer/linear programming \(MILP\) provides a natural mechanism for determining what truth values can inferred for a given formula, given premises with specified truth values[Hah94](https://arxiv.org/html/2607.15532#bib.bib59)\. MILP presupposes that the operators and connectives areMILP\-representable, but a necessary and sufficient condition for representability is known, easily checked, and rather weak\. In particular, Jeroslow[Jer87](https://arxiv.org/html/2607.15532#bib.bib76)showed that an optimization problem is \(finitely\) MILP representable if and only if its feasible set111Technically, this condition applies to the epigraph rather than the feasible set, but the distinction is unnecessary here\.is the union of finitely many polyhedra that have the same recession directions\. These are directions in which one can go forever without leaving the set\. Thus𝒅\{\\bm\{d\}\}is a recession direction for setSSif for some𝒗∈S\{\\bm\{v\}\}\\in S,𝒗\+α​𝒅∈S\{\\bm\{v\}\}\+\\alpha\{\\bm\{d\}\}\\in Sfor allα≥0\\alpha\\geq 0\.

In classical logic, the truth value of a formulaPPis indicated by assertingPPor¬P\\neg P\. In multi\-valued logic, one can specify \(or bound\) the truth value ofPPby means of a more generalsigned formula\.222We slightly modify the notation in[Hah94](https://arxiv.org/html/2607.15532#bib.bib59)For example, the signed formula=0\.6=0\.6P\\hskip 1\.29167ptPindicates thatPPhas truth value0\.60\.6, and≤0\.6\\leq 0\.6P\\hskip 1\.29167ptPindicates thatPPhas some truth value in the interval\[0,0\.6\]\[0,0\.6\]\.

To illustrate the role of MILP, assume for the moment that truth values are continuous in the interval\[0,1\]\[0,1\]\. The resulting model is easily modified to allow only a finite number of discrete truth values\. Suppose first that we wish to infer possible truth values ofP⊃QP\\supset Qfrom the premises≤p​P\\framebox\{$\\leq p$\}\\hskip 1\.29167ptPand≤q​Q\\framebox\{$\\leq q$\}\\hskip 1\.29167ptQ\. For example, we may wish to know how falseP⊃QP\\supset Qcan be, given the premises\. We determine this by minimizingttsubject to the condition that≤t​\(P⊃Q\)\\framebox\{$\\leq t$\}\\hskip 1\.29167pt\(P\\supset Q\)can be inferred from the premises\. Ift∗t^\{\*\}is the minimizingtt, then≤t​\(P⊃Q\)\\framebox\{$\\leq t$\}\\hskip 1\.29167pt\(P\\supset Q\)can be inferred for allt∈\[t∗,1\]t\\in\[t^\{\*\},1\], meaning thatP⊃QP\\supset Qcannot be more false thant∗t^\{\*\}\. Using \([28](https://arxiv.org/html/2607.15532#Ch0.E28)\), the minimization problem is

mint,v​\(P\),v​\(Q\)⁡\{t\|t≥min⁡\{1,1−v​\(P\)\+v​\(Q\)\},0≤v​\(P\)≤p,0≤v​\(Q\)≤q\}\\min\_\{t,v\(P\),v\(Q\)\}\\big\\\{t\\;\\big\|\\;t\\geq\\min\\\{1,1\-v\(P\)\+v\(Q\)\\\},\\;0\\leq v\(P\)\\leq p,\\;0\\leq v\(Q\)\\leq q\\big\\\}\(29\)To obtain an MILP model of problem \([29](https://arxiv.org/html/2607.15532#Ch0.E29)\), we observe first that any feasible solution\(t,v​\(P\),v​\(Q\)\)\(t,v\(P\),v\(Q\)\)must satisfy the following \(inclusive\) disjunction:

t≥10≤v​\(P\)≤v​\(Q\)0≤v​\(Q\)≤qort≥1−v​\(P\)\+v​\(Q\)0≤v​\(Q\)≤q0≤v​\(P\)≤p\\begin\{array\}\[\]\{l\}t\\geq 1\\\\ 0\\leq v\(P\)\\leq v\(Q\)\\\\ 0\\leq v\(Q\)\\leq q\\end\{array\}\\hskip 21\.52771pt\\mbox\{or\}\\hskip 21\.52771pt\\begin\{array\}\[\]\{l\}t\\geq 1\-v\(P\)\+v\(Q\)\\\\ 0\\leq v\(Q\)\\leq q\\\\ 0\\leq v\(P\)\\leq p\\end\{array\}\(30\)The feasible set is therefore the union of the two polyhedra described respectively by the two systems in \([30](https://arxiv.org/html/2607.15532#Ch0.E30)\), and illustrated respectively by Fig\.[4](https://arxiv.org/html/2607.15532#Ch0.F4)\(a\) and[4](https://arxiv.org/html/2607.15532#Ch0.F4)\(b\)\. Each polyhedron has the single recession direction\(t,v​\(P\),v​\(Q\)\)=\(1,0,0\)\(t,v\(P\),v\(Q\)\)=\(1,0,0\), and the necessary and sufficient condition for MILP representability is therefore satisfied\.

![Refer to caption](https://arxiv.org/html/2607.15532v1/x4.png)![Refer to caption](https://arxiv.org/html/2607.15532v1/x5.png)

Figure 4:Two polyhedra with the same unique recession direction\(v​\(P\),v​\(Q\),t\)=\(0,0,1\)\(v\(P\),v\(Q\),t\)=\(0,0,1\)\. Heavy lines indicate the edges of the polyhedra\.An MILP model is now obtained as follows\. In general, it is shown in[Jer89](https://arxiv.org/html/2607.15532#bib.bib77)that if the feasible set is a union of polyhedra described byAi​𝒙≤𝒃iA^\{i\}\\bm\{x\}\\leq\\bm\{b\}^\{i\}fori∈Ii\\in I, the MILP constraint set consists of

Ai​𝒙i≤𝒃i​δi,i∈I\\displaystyle A^\{i\}\\bm\{x\}^\{i\}\\leq\\bm\{b\}^\{i\}\\delta\_\{i\},\\;i\\in I𝒙=∑i∈I𝒙i,∑i∈Iδi=1\\displaystyle\\bm\{x\}=\{\\textstyle\\sum\_\{i\\in I\}\\bm\{x\}^\{i\},\\;\\;\\sum\_\{i\\in I\}\\delta\_\{i\}=1\}δi∈\{0,1\},i∈I\\displaystyle\\delta\_\{i\}\\in\\\{0,1\\\},\\;i\\in Iwhere𝒙i\\bm\{x\}^\{i\}andδi\\delta\_\{i\}are new continuous and binary variables, respectively, for alli∈Ii\\in I\. An MILP model of \([29](https://arxiv.org/html/2607.15532#Ch0.E29)\) therefore has the form

min\{t1\+t2\|t1≥δ10≤v1​\(P\)≤v1​\(Q\)0≤v1​\(Q\)≤q​δ1t2≥δ2−v2​\(P\)\+v2​\(Q\)0≤v2​\(Q\)≤q​δ20≤v2​\(P\)≤p​δ2v​\(P\)=v1​\(P\)\+v2​\(P\)v​\(Q\)=v1​\(Q\)\+v2​\(Q\)δ1\+δ2=1,δ1,δ2∈\{0,1\}\}\\min\\left\\\{t\_\{1\}\+t\_\{2\}\\;\\left\|\\;\\begin\{array\}\[\]\{l@\{\\hspace\{3ex\}\}l\}\\begin\{array\}\[\]\{l\}t\_\{1\}\\geq\\delta\_\{1\}\\\\ 0\\leq v\_\{1\}\(P\)\\leq v\_\{1\}\(Q\)\\\\ 0\\leq v\_\{1\}\(Q\)\\leq q\\delta\_\{1\}\\end\{array\}\\hfil\\hskip 12\.91663pt&\\begin\{array\}\[\]\{l\}t\_\{2\}\\geq\\delta\_\{2\}\-v\_\{2\}\(P\)\+v\_\{2\}\(Q\)\\\\ 0\\leq v\_\{2\}\(Q\)\\leq q\\delta\_\{2\}\\\\ 0\\leq v\_\{2\}\(P\)\\leq p\\delta\_\{2\}\\end\{array\}\\\\ \\lx@intercol\\hfil v\(P\)=v\_\{1\}\(P\)\+v\_\{2\}\(P\)\\hfil\\lx@intercol\\\\ \\lx@intercol\\hfil v\(Q\)=v\_\{1\}\(Q\)\+v\_\{2\}\(Q\)\\hfil\\lx@intercol\\\\ \\lx@intercol\\hfil\\delta\_\{1\}\+\\delta\_\{2\}=1,\\;\\delta\_\{1\},\\delta\_\{2\}\\in\\\{0,1\\\}\\hfil\\lx@intercol\\end\{array\}\\right\.\\right\\\}\(31\)It is straightforward \(if somewhat tedious\) to show that \([31](https://arxiv.org/html/2607.15532#Ch0.E31)\) simplifies to the MILP model

min\{t\|t≥δ0≤v​\(P\)≤v​\(Q\)\+1−δ0≤v​\(Q\)≤qt≥1−δ−v​\(P\)\+v​\(Q\)0≤v​\(P\)≤pδ∈\{0,1\}\}\\min\\left\\\{t\\;\\left\|\\;\\begin\{array\}\[\]\{l@\{\\hspace\{3ex\}\}l\}\\begin\{array\}\[\]\{l\}t\\geq\\delta\\\\ 0\\leq v\(P\)\\leq v\(Q\)\+1\-\\delta\\\\ 0\\leq v\(Q\)\\leq q\\end\{array\}\\hfil\\hskip 12\.91663pt&\\begin\{array\}\[\]\{l\}t\\geq 1\-\\delta\-v\(P\)\+v\(Q\)\\\\ 0\\leq v\(P\)\\leq p\\\\ \\delta\\in\\\{0,1\\\}\\end\{array\}\\end\{array\}\\right\.\\right\\\}\(32\)If we wish to recognizem\+1m\+1equally spaced discrete truth values in\[0,1\]\[0,1\]rather than continuous truth values, we can replacev​\(P\)v\(P\)andv​\(Q\)v\(Q\)withvI​\(P\)/mv\_\{I\}\(P\)/mandvI​\(Q\)/mv\_\{I\}\(Q\)/m, respectively in \([32](https://arxiv.org/html/2607.15532#Ch0.E32)\), and require thatvI​\(P\)v\_\{I\}\(P\)andvI​\(Q\)v\_\{I\}\(Q\)be integers\. Then ift∗t^\{\*\}is the optimal solution of the resulting MILP problem, we can infer≤t​\(P⊃Q\)\\framebox\{$\\leq t$\}\\hskip 1\.29167pt\(P\\supset Q\)for allt∈\{t∗/m,\(t∗\+1\)/m,…,1\}t\\in\\\{t^\{\*\}/m,\(t^\{\*\}\\\!\+\\\!1\)/m,\\ldots,1\\\}\.

The MILP model for more complex formulas can be constructed recursively\. For example, the formula\(P⊃Q\)⊃¬P\(P\\\!\\supset\\\!Q\)\\supset\\neg Phas the truth function\.

v​\(\(P⊃Q\)⊃¬P\)=min⁡\{1,1−min⁡\{1,1−v​\(P\)\+v​\(Q\)\}\+1−v​\(P\)\}v\\big\(\(P\\\!\\supset\\\!Q\)\\supset\\neg P\\big\)=\\min\\big\\\{1,\\;1\-\\min\\\{1,\\;1\\\!\-\\\!v\(P\)\\\!\+\\\!v\(Q\)\\\}\+1\\\!\-\\\!v\(P\)\\big\\\}An MILP model can be written by allowing the constraints in \([32](https://arxiv.org/html/2607.15532#Ch0.E32)\) to represent the possible truth valuesttof the inner implicationP⊃QP\\supset Q, and observing that the truth value of¬P\\neg Pis1−v​\(P\)1\-v\(P\)\. Then we can write additional constraints to represent the possible truth valuest′t^\{\\prime\}of the outer implication\. Usingδ′\\delta^\{\\prime\}as the binary variable in the latter, this yields the model

min\{t′\|t′≥δ′0≤t≤\(1−v​\(P\)\)\+1−δ′t′≥1−δ′−t\+\(1−v​\(P\)\)0≤t≤1,δ′∈\{0,1\}constraints in \([32](https://arxiv.org/html/2607.15532#Ch0.E32)\)\}\\min\\left\\\{t^\{\\prime\}\\;\\left\|\\;\\begin\{array\}\[\]\{l@\{\\hspace\{3ex\}\}l\}\\begin\{array\}\[\]\{l\}t^\{\\prime\}\\geq\\delta^\{\\prime\}\\\\ 0\\leq t\\leq\(1\\\!\-\\\!v\(P\)\)\+1\\\!\-\\\!\\delta^\{\\prime\}\\\\ \\end\{array\}\\hfil\\hskip 12\.91663pt&\\begin\{array\}\[\]\{l\}t^\{\\prime\}\\geq 1\\\!\-\\\!\\delta^\{\\prime\}\-t\+\(1\\\!\-\\\!v\(P\)\)\\\\ 0\\leq t\\leq 1,\\;\\;\\delta^\{\\prime\}\\in\\\{0,1\\\}\\end\{array\}\\\\ \\lx@intercol\\hfil\\mbox\{constraints in \\eqref\{eq:multi5\}\}\\hfil\\lx@intercol\\end\{array\}\\right\.\\right\\\}\(33\)The valid boundt≤1t\\leq 1ensures that the polyhedra whose union \([33](https://arxiv.org/html/2607.15532#Ch0.E33)\) represents have the same recession direction\(t′,t,v​\(P\),v​\(Q\)\)=\(1,0,0,0\)\(t^\{\\prime\},t,v\(P\),v\(Q\)\)=\(1,0,0,0\)\.

As an example, suppose the upper bounds onv​\(P\)v\(P\)andv​\(Q\)v\(Q\)are\(p,q\)=\(0\.3,0\.7\)\(p,q\)=\(0\.3,0\.7\)\. The minimum value oft′t^\{\\prime\}is 0\.7, indicating that\(P⊃Q\)⊃¬P\(P\\\!\\supset\\\!Q\)\\\!\\supset\\\!\\neg Pcannot be more false than 0\.7\. This solution is achieved when\(t,v​\(P\),v​\(Q\)\)=\(1,0\.3,0\.3\)\(t,v\(P\),v\(Q\)\)=\(1,0\.3,0\.3\)and\(δ,δ′\)=\(0,0\)\(\\delta,\\delta^\{\\prime\}\)=\(0,0\)\. A branch\-and\-bound solution of this problem instance appears in Section[7\.2](https://arxiv.org/html/2607.15532#Ch0.S7.SS2)\.

Additional discussion of MILP models for multivalued logic can be found in[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31);[Hah94](https://arxiv.org/html/2607.15532#bib.bib59)\.

## 5Statistical Inference of Logical Formulas

As noted in the introduction, the estimation of weights in a neural network poses an optimization problem\. The same is true for the calibration of a vector support machine, which is a hyperplane that classifies by separating two \(possibly overlapping\) clusters of data points\. There is a third data fitting possibility that is often overlooked\. One can fit alogical formulato data in a manner analogous to classical regression, which likewise gives rise to an optimization problem\. This represents yet another instance in which logic and optimization combine to serve the purposes of AI\. Like logic\-based methods in general, it has the advantage of transparency, since one can examine precisely what rules are inferred from training data\. It also offers the possibility of computing the statistical significance of an inferred formula, as is routinely done in regression analysis\. A similar approach can be used to reduce a trained neural network to a logical formula that approximates its predictions, for the sake of transparency, by fitting the formula to the output of the network for various inputs\.

### 5\.1Boolean Regression

Boolean regression[BorHamHoo95](https://arxiv.org/html/2607.15532#bib.bib26)infers a logical formula from Boolean data points of the form\(𝒙,y\)\(\\bm\{x\},y\), where the independent variables𝒙=\(x1,…,xm\)\\bm\{x\}=\(x\_\{1\},\\ldots,x\_\{m\}\)represent observed attributes and the dependent variableyyrepresents the observed outcome\. Following classical regression analysis, it supposes there is noise in the observations and therefore writes

y=f​\(𝒙\)⊕ϵy=f\(\\bm\{x\}\)\\oplus\\epsilonwheref​\(𝒙\)f\(\\bm\{x\}\)is the true outcome, andϵ\\epsilonis the observation error\. Here,⊕\\oplusis a binary sum, so thata⊕b=\(a\+b\)mod2a\\oplus b=\(a\+b\)\\bmod 2\. The Boolean error termϵ\\epsilonis a simple Bernoulli variable that takes the value 1 with probabilityppand 0 with probability1−p1\-p\. The value ofppis estimated along with the regression formula, much as the error variance is estimated along with the regression coefficients in classical statistics\. An independent variablexix\_\{i\}that is non\-Boolean and takes discrete values0,1,2,…,k0,1,2,\\ldots,kcan be accommodated by replacing it with Boolean variablesxi​0,…,xi​ℓx\_\{i0\},\\ldots,x\_\{i\\ell\}, wherexi=xi​0\+2​xi​1\+⋯\+2ℓ​xi​ℓx\_\{i\}=x\_\{i0\}\+2x\_\{i1\}\+\\cdots\+2^\{\\ell\}x\_\{i\\ell\}\.

The dataset may contain multiple observations ofyyfor a given value of𝒙\\bm\{x\}, and no observation ofyyat all for other values of𝒙\\bm\{x\}\. This is illustrated by an example taken from[BorHamHoo95](https://arxiv.org/html/2607.15532#bib.bib26), whose dataset \(Table[3](https://arxiv.org/html/2607.15532#Ch0.T3)\) is designed to contain a great deal of noise\. We wish to identify a Boolean functionf​\(𝒙\)f\(\\bm\{x\}\)that best fits the data, whereffbelongs to a specified classFFof Boolean functions, such as the class of functions expressed by a Boolean formula of a certain form\.

Table 3:Small dataset for Boolean regression\.ObservationsNumber ofof𝒙\\bm\{x\}observations withx1x\_\{1\}x2x\_\{2\}x3x\_\{3\}x4x\_\{4\}x5x\_\{5\}y=0y=0y=1y=101011715110019310011821000137110105170011192A classical least\-squares fit is based on maximum likelihood estimation, and a similar approach can be used here\. We seek a functionffthat maximizes the likelihood of the errors displayed in Table[3](https://arxiv.org/html/2607.15532#Ch0.T3)\. Thus if𝒚=\(y1,…,yn\)\\bm\{y\}=\(y\_\{1\},\\ldots,y\_\{n\}\)represents the set of observations, we wish to identify a functionf∈Ff\\in Fand probabilityppthat maximize the likelihood function

Pr​\(𝒚\|f,p\)=\(1−p\)n−e​\(f\)​pe​\(f\)\\mathrm\{Pr\}\(\\bm\{y\}\|f,p\)=\(1\-p\)^\{n\-e\(f\)\}p^\{e\(f\)\}\(34\)wherennis the number of observations, ande​\(f\)e\(f\)is the number of errors made by functionffon the observed values of𝒙\\bm\{x\}\. For example, if\(𝒙1,…,𝒙6\)\(\\bm\{x\}^\{1\},\\ldots,\\bm\{x\}^\{6\}\)are the observed values of𝒙\\bm\{x\}in Table[3](https://arxiv.org/html/2607.15532#Ch0.T3), and\(f​\(𝒙1\),…,f​\(𝒙6\)\)=\(0,…,0\)\(f\(\\bm\{x\}^\{1\}\),\\ldots,f\(\\bm\{x\}^\{6\}\)\)=\(0,\\ldots,0\), thenP​r​\(𝒚\|f,p\)=\(1−p\)41​p46Pr\(\\bm\{y\}\|f,p\)=\(1\-p\)^\{41\}p^\{46\}\. If\(f​\(𝒙1\),…,f​\(𝒙6\)\)=\(0,0,0,0,0,1\)\(f\(\\bm\{x\}^\{1\}\),\\ldots,f\(\\bm\{x\}^\{6\}\)\)=\(0,0,0,0,0,1\), thenP​r​\(𝒚\|f,p\)=\(1−p\)34​p53Pr\(\\bm\{y\}\|f,p\)=\(1\-p\)^\{34\}p^\{53\}, and so forth\.

We can note right away that \([34](https://arxiv.org/html/2607.15532#Ch0.E34)\) is maximized with respect toppwhenp=e​\(f\)/np=e\(f\)/n\. It therefore suffices to maximize the following overf∈Ff\\in F:

Pr​\(𝒚\|f,e​\(f\)/n\)=\(1−e​\(f\)n\)n−e​\(f\)​\(e​\(f\)n\)e​\(f\)\\mathrm\{Pr\}\\big\(\\bm\{y\}\\big\|f,e\(f\)/n\\big\)=\\Big\(1\-\\frac\{e\(f\)\}\{n\}\\Big\)^\{n\-e\(f\)\}\\Big\(\\frac\{e\(f\)\}\{n\}\\Big\)^\{e\(f\)\}\(35\)Interestingly, since \([35](https://arxiv.org/html/2607.15532#Ch0.E35)\) is convex ine​\(f\)e\(f\), it is maximized either by a functionffthat minimizese​\(f\)e\(f\)or by a function that maximizese​\(f\)e\(f\)\. Most applications call for a fit that minimizes errors, but there are cases in which it may be appropriate to maximize errors[BorHamHoo95](https://arxiv.org/html/2607.15532#bib.bib26)\. For present purposes, we assume that the data are such that a maximum likelihood fit is error minimizing\. Iff^\\hat\{f\}is the error minimizing function, thenp^=e​\(f^\)/n\\hat\{p\}=e\(\\hat\{f\}\)/nis a \(biased\) estimator ofpp\.

Suppose now that we wish to fit to the data of Table[3](https://arxiv.org/html/2607.15532#Ch0.T3)a regression formula that is a logical clause with positive literals:

β0∨β1​x1∨⋯∨β5​x5\\beta\_\{0\}\\vee\\beta\_\{1\}x\_\{1\}\\vee\\cdots\\vee\\beta\_\{5\}x\_\{5\}\(36\)The binary coefficientβi=1\\beta\_\{i\}=1\(fori≥1i\\geq 1\) indicates thatxix\_\{i\}is present in the clause, andβi=0\\beta\_\{i\}=0indicates thatxix\_\{i\}is absent\. The clause is a tautology ifβ0=1\\beta\_\{0\}=1, andβ0\\beta\_\{0\}disappears from the clause ifβ0=0\\beta\_\{0\}=0\. The task is to find a maximum likelihood estimate ofβ0,…,β5\\beta\_\{0\},\\ldots,\\beta\_\{5\}, which is accomplished by maximizing \([35](https://arxiv.org/html/2607.15532#Ch0.E35)\) over all functionsffthat result from some setting ofβ0,…,β5∈\{0,1\}\\beta\_\{0\},\\ldots,\\beta\_\{5\}\\in\\\{0,1\\\}\.

The maximization problem can be solved by formulating it as a pseudo\-Boolean optimization problem, mentioned earlier in the context of probabilistic logic\. Letf𝜷f\_\{\\bm\{\\beta\}\}be the Boolean function that results from a given tuple𝜷=\(β0,…,β5\)\\bm\{\\beta\}=\(\\beta\_\{0\},\\ldots,\\beta\_\{5\}\)of parameters in \([36](https://arxiv.org/html/2607.15532#Ch0.E36)\)\. We first note that if

β0=β2=β4=β5=0\\beta\_\{0\}=\\beta\_\{2\}=\\beta\_\{4\}=\\beta\_\{5\}=0\(37\)thenf𝜷​\(𝒙1\)=0f\_\{\\bm\{\\beta\}\}\(\\bm\{x\}^\{1\}\)=0, and line 1 of Table[3](https://arxiv.org/html/2607.15532#Ch0.T3)generates 15 errors\. If \([37](https://arxiv.org/html/2607.15532#Ch0.E37)\) does not hold, thenf𝜷​\(𝒙1\)=1f\_\{\\bm\{\\beta\}\}\(\\bm\{x\}^\{1\}\)=1, and there are 7 errors\. So, line 1 generates

15​β¯0​β¯2​β¯4​β¯5\+7​\(1−β¯0​β¯2​β¯4​β¯5\)15\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{2\}\\bar\{\\beta\}\_\{4\}\\bar\{\\beta\}\_\{5\}\+7\(1\-\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{2\}\\bar\{\\beta\}\_\{4\}\\bar\{\\beta\}\_\{5\}\)errors, whereβ¯i=1−βi\\bar\{\\beta\}\_\{i\}=1\-\\beta\_\{i\}\. Summing expressions of this sort for𝒙1,…,𝒙6\\bm\{x\}^\{1\},\\ldots,\\bm\{x\}^\{6\}and collecting terms, we obtain the pseudo\-Boolean functione​\(f𝜷\)e\(f\_\{\\bm\{\\beta\}\}\)equal to

41\+8​β¯0​β¯2​β¯4​β¯5−6​β¯0​β¯1​β¯2​β¯5−6​β¯0​β¯1​β¯4​β¯5\+4​β¯0​β¯1​β¯5\+12​β¯0​β¯1​β¯2​β¯4−7​β¯0​β¯3​β¯4​β¯541\+8\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{2\}\\bar\{\\beta\}\_\{4\}\\bar\{\\beta\}\_\{5\}\-6\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{1\}\\bar\{\\beta\}\_\{2\}\\bar\{\\beta\}\_\{5\}\-6\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{1\}\\bar\{\\beta\}\_\{4\}\\bar\{\\beta\}\_\{5\}\+4\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{1\}\\bar\{\\beta\}\_\{5\}\+12\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{1\}\\bar\{\\beta\}\_\{2\}\\bar\{\\beta\}\_\{4\}\-7\\bar\{\\beta\}\_\{0\}\\bar\{\\beta\}\_\{3\}\\bar\{\\beta\}\_\{4\}\\bar\{\\beta\}\_\{5\}The minimum error solution is𝜷=\(0,0,1,0,0,0\)\\bm\{\\beta\}=\(0,0,1,0,0,0\), withe​\(f𝜷\)=32e\(f\_\{\\bm\{\\beta\}\}\)=32errors, which means the estimated error probability isp^=e​\(f𝜷\)/n=32/87≈0\.368\\hat\{p\}=e\(f\_\{\\bm\{\\beta\}\}\)/n=32/87\\approx 0\.368\. This solution corresponds to the simple logical formulax2x\_\{2\}, which ignores all but one of the independent variables\. To obtain a more satisfactory formula, one might allow negative as well as positive literals:

β0∨β1​x1∨⋯∨β5​x5∨γ1​\(¬x1\)∨⋯∨γ5​\(¬x5\)\\beta\_\{0\}\\vee\\beta\_\{1\}x\_\{1\}\\vee\\cdots\\vee\\beta\_\{5\}x\_\{5\}\\vee\\gamma\_\{1\}\(\\neg x\_\{1\}\)\\vee\\cdots\\vee\\gamma\_\{5\}\(\\neg x\_\{5\}\)\(38\)The best\-fit formula isx2∨¬x4x\_\{2\}\\vee\\neg x\_\{4\}, which results ine​\(f𝜷,𝜸\)=28e\(f\_\{\\bm\{\\beta\},\\bm\{\\gamma\}\}\)=28errors andp^≈0\.322\\hat\{p\}\\approx 0\.322\.

In general, the regression formula can be any expression of the form

f​\(𝒙β\)=⋁i∈Iβi​Pi​\(𝒙\)f\(\\bm\{x\}\_\{\\beta\}\)=\\bigvee\_\{i\\in I\}\\beta\_\{i\}P\_\{i\}\(\\bm\{x\}\)\(39\)where eachPi​\(𝒙\)P\_\{i\}\(\\bm\{x\}\)is any desired logical proposition that contains atomic propositions in𝒙=\(x1,…,xm\)\\bm\{x\}=\(x\_\{1\},\\ldots,x\_\{m\}\)\. For example, eachPi​\(𝒙\)P\_\{i\}\(\\bm\{x\}\)could be a conjunction of literals \(atomic propositions or their negations\); in fact, any propositional formula can be written as \([39](https://arxiv.org/html/2607.15532#Ch0.E39)\) withPi​\(𝒙\)P\_\{i\}\(\\bm\{x\}\)s in this form\. If𝒙1,…,𝒙n\\bm\{x\}^\{1\},\\ldots,\\bm\{x\}^\{n\}are the observations of independent variables, lety0​\(𝒙j\)y\_\{0\}\(\\bm\{x\}^\{j\}\)be the number of observations off​\(𝒙j\)f\(\\bm\{x\}^\{j\}\)for whichy=0y=0, andy1​\(𝒙j\)y\_\{1\}\(\\bm\{x\}^\{j\}\)the number for whichy=1y=1\. The pseudo\-Boolean function to be minimized is

e​\(f𝜷\)=∑j=1ny0​\(𝒙j\)\+∑j=1n\(y1​\(𝒙j\)−y0​\(𝒙j\)\)​∏i\|Pi​\(𝒙j\)=1β¯ie\(f\_\{\\bm\{\\beta\}\}\)=\\sum\_\{j=1\}^\{n\}y\_\{0\}\(\{\\bm\{x\}\}^\{j\}\)\+\\sum\_\{j=1\}^\{n\}\\big\(y\_\{1\}\(\\bm\{x\}^\{j\}\)\-y\_\{0\}\(\\bm\{x\}^\{j\}\)\\big\)\\hskip\-8\.61108pt\\prod\_\{i\|P\_\{i\}\(\\bm\{x\}^\{j\}\)=1\}\\hskip\-10\.76385pt\\bar\{\\beta\}\_\{i\}
Solution methods for pseudo\-Boolean optimization are extensively discussed in[BorHam02](https://arxiv.org/html/2607.15532#bib.bib25)\. Recent developments in solution methods include[ElfNor18](https://arxiv.org/html/2607.15532#bib.bib49);[ElfNor20](https://arxiv.org/html/2607.15532#bib.bib50);[SmiBerJar22](https://arxiv.org/html/2607.15532#bib.bib120), and schemes for integrating MILP techniques are described in[DevGleNor21](https://arxiv.org/html/2607.15532#bib.bib45);[DevGocDemNorStu21](https://arxiv.org/html/2607.15532#bib.bib46)\.

### 5\.2Statistical Significance

Boolean regression can provide measures of statistical significance, including confidence levels and the significance of regression, the latter of which enables stepwise regression\. A potential barrier to calculating significance is that the distribution of estimated regression parameters depends on the distribution of observational error, which is unknowna priori\. Classical regression deals with this problem by identifying a “pivot” statistic whose distribution depends only on the number of data points \(or more precisely, the degrees of freedom\)\. For example, thett\-statistic allows one to compute confidence intervals based on the pre\-computed distribution of thett\-statistic\. Apparently, no pivot statistic has been identified for Boolean regression, but one can nonetheless obtain useful significance indicators from a Bayesian model\. We follow here the analysis of[BorHamHoo95](https://arxiv.org/html/2607.15532#bib.bib26)\.

A Bayesian significance model identifies the confidence level of a deduced regression formulaffwith the posterior probability thatffis the true formula, given the observed data and prior probabilities\. Thus, given observations𝒚=\(y1,…,yn\)\\bm\{y\}=\(y\_\{1\},\\ldots,y\_\{n\}\), the confidence level offfis Pr\(f\|𝒚\)\(f\|\\bm\{y\}\)\. Using Bayes’ rule, this is

Pr​\(f\|𝒚\)=Pr​\(𝒚\|f\)​Pr​\(f\)Pr​\(𝒚\)\\mathrm\{Pr\}\(f\|\\bm\{y\}\)=\\frac\{\\mathrm\{Pr\}\(\\bm\{y\}\|f\)\\mathrm\{Pr\}\(f\)\}\{\\mathrm\{Pr\}\(\\bm\{y\}\)\}\(40\)where Pr\(f\)\(f\)is the prior probability that functionffis the correct one\. The conditional probability Pr\(𝒚\|f\)\(\\bm\{y\}\|f\)is obtained by integrating over possible error probabilitiespp:

Pr​\(𝒚\|f\)=∫01Pr​\(𝒚\|f,p\)​π​\(p\)​𝑑p\\mathrm\{Pr\}\(\\bm\{y\}\|f\)=\\int\_\{0\}^\{1\}\\mathrm\{Pr\}\(\\bm\{y\}\|f,p\)\\pi\(p\)dp\(41\)whereπ​\(p\)\\pi\(p\)is a prior probability density function forpp, and Pr\(𝒚\|f,p\)\(\\bm\{y\}\|f,p\)is given by \([34](https://arxiv.org/html/2607.15532#Ch0.E34)\)\. Also Pr\(𝒚\)\(\\bm\{y\}\)is

Pr​\(𝒚\)=∑f′∈FPr​\(𝒚\|f′\)​Pr​\(f′\)\\mathrm\{Pr\}\(\\bm\{y\}\)=\\sum\_\{f^\{\\prime\}\\in F\}\\mathrm\{Pr\}\(\\bm\{y\}\|f^\{\\prime\}\)\\mathrm\{Pr\}\(f^\{\\prime\}\)Since nothing is known in advance about which formula could be correct, we assume Pr\(f′\)\(f^\{\\prime\}\)is the same for allf′∈Ff^\{\\prime\}\\in Fand can therefore ignore this term\. As for the probabilityppof error, we can suppose it is no greater than some valueρ≤12\\rho\\leq\\frac\{1\}\{2\}, since even a random guess is right half the time\. Since we know nothing beyond this, we assumeppis uniformly distributed over\[0,ρ\]\[0,\\rho\], withπ​\(p\)=1/ρ\\pi\(p\)=1/\\rhoin this range\. Thus, using \([34](https://arxiv.org/html/2607.15532#Ch0.E34)\), \([41](https://arxiv.org/html/2607.15532#Ch0.E41)\) becomes

Pr​\(Y\|f\)=1ρ​∫0ρ\(1−p\)n−e​\(f\)​pe​\(f\)​𝑑p\\mathrm\{Pr\}\(Y\|f\)=\\frac\{1\}\{\\rho\}\\int\_\{0\}^\{\\rho\}\(1\-p\)^\{n\-e\(f\)\}p^\{e\(f\)\}dpEvaulating the integral, we obtain

P​r​\(𝒚\|f\)=ρe​\(f\)n\+1​∑i=0n−e​\(f\)\(n−e​\(f\)i\)​\(ni\)−1​\(1−ρ\)n−e​\(f\)−iPr\(\\bm\{y\}\|f\)=\\frac\{\\rho^\{e\(f\)\}\}\{n\+1\}\\sum\_\{i=0\}^\{n\-e\(f\)\}\\hskip\-2\.15277pt\\Big\(\\begin\{array\}\[\]\{@\{\}c@\{\}\}n\-e\(f\)\\\\ i\\end\{array\}\\Big\)\\Big\(\\begin\{array\}\[\]\{@\{\}c@\{\}\}n\\\\ i\\end\{array\}\\Big\)^\{\\\!\-1\}\\hskip\-6\.45831pt\(1\-\\rho\)^\{n\-e\(f\)\-i\}\(42\)
It is reported in[BorHamHoo95](https://arxiv.org/html/2607.15532#bib.bib26)that, using this analysis, the maximum likelihood formulax2x\_\{2\}can be inferred from the data in Table[3](https://arxiv.org/html/2607.15532#Ch0.T3)with confidence level 0\.282 whenρ=12\\rho=\\frac\{1\}\{2\}\. This says one cannot have much confidence that the formula is exactly right\. One might calculate a confidence sphere that is analogous to an confidence interval in classical regression\. A confidence sphere could consist of all binary vectors𝜷\\bm\{\\beta\}within a Hamming distance ofddfrom the inferred vector𝜷\\bm\{\\beta\}of coefficients\. In the example, the confidence level increases to 0\.433 whend=1d=1and0\.5720\.572whend=2d=2, still rather low due to the large amount of noise in the dataset\.

The significance of regression, however, is more encouraging\. We can compute it by considering the hypotheses:

H0:βi=0fori=1,…,5\(null hypothesis\)\\displaystyle H\_\{0\}:\\;\\beta\_\{i\}=0\\;\\mbox\{for\}\\;i=1,\\ldots,5\\;\\mbox\{\(null hypothesis\)\}H1:βi=1​for at least one​i∈\{1,…,5\}\\displaystyle H\_\{1\}:\\;\\beta\_\{i\}=1\\;\\mbox\{for at least one\}\\;i\\in\\\{1,\\ldots,5\\\}The best fit under the null hypothesis is the functionf0f\_\{0\}defined byβ0=1\\beta\_\{0\}=1, with Pr\(f0\|𝒚\)=0\.0104\(f\_\{0\}\|\\bm\{y\}\)=0\.0104\. The best fit underH1H\_\{1\}is again the functionffcorresponding to𝜷=\(0,0,1,0,0,0\)\\bm\{\\beta\}=\(0,0,1,0,0,0\)with Pr\(f\|𝒚\)=0\.282\(f\|\\bm\{y\}\)=0\.282\. The significance of regression is

Pr​\(f0\|𝒚\)Pr​\(f0\|𝒚\)\+Pr​\(f\|𝒚\)=0\.036\\frac\{\\mathrm\{Pr\}\(f\_\{0\}\|\\bm\{y\}\)\}\{\\mathrm\{Pr\}\(f\_\{0\}\|\\bm\{y\}\)\+\\mathrm\{Pr\}\(f\|\\bm\{y\}\)\}=0\.036This means that it is very likely \(96\.4% probability\) that an expression of the formβ1​x1∨⋯∨β5​x5\\beta\_\{1\}x\_\{1\}\\vee\\cdots\\vee\\beta\_\{5\}x\_\{5\}captures a relationship that is not purely the result of chance\.

We can also perform stepwise regression by adding negative literals to the formula as in \([38](https://arxiv.org/html/2607.15532#Ch0.E38)\)\. This significantly improves the fit if we can rejectH0H\_\{0\}:

H0:βi=0fori=6,…,10\(i\.e\., the negative literals do not improve the fit\)\\displaystyle H\_\{0\}:\\;\\beta\_\{i\}=0\\;\\mbox\{for\}\\;i=6,\\ldots,10\\;\\mbox\{\(i\.e\., the negative literals do not improve the fit\)\}H1:β=1​for at least one​i∈\{6,…,10\}\\displaystyle H\_\{1\}:\\;\\beta=1\\;\\mbox\{for at least one\}\\;i\\in\\\{6,\\ldots,10\\\}We can rejectH0H\_\{0\}with probability1−0\.073=0\.9271\-0\.073=0\.927, which means that the improvement in fit is significant at the 10% level but not at the 5% level\. In addition, the confidence level of the expanded regression formulax2∨¬x4x\_\{2\}\\vee\\neg x\_\{4\}is only 0\.11, because it is competing with a much larger collection of admissible formulas\.

Related research on learning Boolean functions appears in[Ant10](https://arxiv.org/html/2607.15532#bib.bib8);[CheBra17](https://arxiv.org/html/2607.15532#bib.bib33);[MukPelNevKuoZiySpeGraSpe09](https://arxiv.org/html/2607.15532#bib.bib102);[MukSpe07](https://arxiv.org/html/2607.15532#bib.bib103);[SanTriCheLia02](https://arxiv.org/html/2607.15532#bib.bib116);[SloSzoTur10](https://arxiv.org/html/2607.15532#bib.bib119)\. An important class of Boolean functions are monotone, meaning that𝒙′≥𝒙\\bm\{x\}^\{\\prime\}\\geq\\bm\{x\}impliesf​\(𝒙′\)≥f​\(𝒙\)f\(\\bm\{x\}^\{\\prime\}\)\\geq f\(\\bm\{x\}\), where𝒙′≥𝒙\\bm\{x\}^\{\\prime\}\\geq\\bm\{x\}whenxj′≥xjx^\{\\prime\}\_\{j\}\\geq x\_\{j\}for eachjj\. For example, a monotone Boolean function implies that observing additional indicators of a particular disease cannot reverse a prediction that the disease is present\. The problem of learning monotone Boolean functions from noisy and incomplete data is addressed in[AmaMar06](https://arxiv.org/html/2607.15532#bib.bib2);[BluBurLan98](https://arxiv.org/html/2607.15532#bib.bib20);[BorHamHoo94](https://arxiv.org/html/2607.15532#bib.bib24)\.

## 6Inference as Projection

Optimization and logical inference are fundamentally related because they are both special cases of projection[Hoo16](https://arxiv.org/html/2607.15532#bib.bib68)\. Theprojectionof a setSSof tuples𝒙=\(x1,…,xn\)\\bm\{x\}=\(x\_\{1\},\\ldots,x\_\{n\}\)onto variables𝒙¯=\(x1,…,xk\)\\bar\{\\bm\{x\}\}=\(x\_\{1\},\\ldots,x\_\{k\}\)is

S\|𝒙¯=\{\(x1,…,xk\)\|\(x1,…,xn\)∈S\}S\|\_\{\\bar\{\\bm\{x\}\}\}=\\big\\\{\(x\_\{1\},\\ldots,x\_\{k\}\)\\;\\big\|\\;\(x\_\{1\},\\ldots,x\_\{n\}\)\\in S\\big\\\}Optimization is a special case of projection because any optimization problem can be writtenmin/max⁡\{z\|\(z,𝒙\)∈S\}\\min/\\max\\\{z\\;\|\\;\(z,\\bm\{x\}\)\\in S\\\}and solved by computing the projectionS\|zS\|\_\{z\}\. The minimum and maximum values ofzz, if they exist, are then easily recognized as the smallest and largest elements ofS\|zS\|\_\{z\}\. Inference can be seen as a special case of projection if we letS​\(F\)S\(F\)denote the set of assignments to𝒙\\bm\{x\}that satisfy a setFFof logical formulas\. Then a formulaffcontaining variables𝒙¯\\bar\{\\bm\{x\}\}can be inferred fromFFif and only if all the assignments in the projectionS​\(F\)\|𝒙¯S\(F\)\|\_\{\\bar\{\\bm\{x\}\}\}satisfyff\.

This linkage of optimization and inference through projection provides a novel opportunity to apply optimization to inference\. The projection ofS​\(F\)S\(F\)onto𝒙¯\\bar\{\\bm\{x\}\}can be obtained with the assistance of a binary decision diagram \(BDD\), which compactly and transparently displays satisfying solutions ofFF\. The projection can be computed using a generalization of Benders decomposition, a well\-known optimization method that, in effect, \(partially\) computes the projection of the feasible set onto a subset of variables\. The first subsection below illustrates how a BDD represents the satisfying setS​\(F\)S\(F\), and how it relates to projection\. The second subsection shows how Benders decomposition can accelerate the computation of the projection, thereby deducing all formulas that can be inferred fromFF\.

This methodology can be useful to AI because it allows one to infer everything that can be deduced from a knowledge base regarding a specific topic, rather than check which individual formulas can be deduced\. For example, one may be interested in whether substances A, B, and C can interact to cause allergic reactions D and E\. Rather than check whether one can deduce that A and B interact to cause D \(i\.e\.\(A∧B\)⊃D\(A\\wedge B\)\\supset D\), whether one can deduce that B and C cause reaction E, and so forth, one can project the knowledge base onto the five variables A, B, C, D, and E\. Since one is projecting onto a handful of variables, the projection can be computed fairly rapidly\. The rather small number of assignments in the projection \(at most252^\{5\}\) is easily converted to a few logical formulas that capture everything that is known about allergic reactions to A, B and C\.

### 6\.1Projection in a Binary Decision Diagram

Binary decision diagrams were introduced in the 1970s and have been used for logic circuit verification, product configuration, and more recently, discrete optimization[Ake78](https://arxiv.org/html/2607.15532#bib.bib1);[BerCirHoeHoo16a](https://arxiv.org/html/2607.15532#bib.bib16);[BolSauSieWeg2010](https://arxiv.org/html/2607.15532#bib.bib21);[Bry92](https://arxiv.org/html/2607.15532#bib.bib28);[PopBalOst23](https://arxiv.org/html/2607.15532#bib.bib115)\. We are interested in their potential for computing projections\. A BDD is a graphical representation of a Boolean functionf​\(𝒙\)f\(\\bm\{x\}\)\. Any setFFof propositional formulas defines a Boolean functionf​\(𝒙\)f\(\\bm\{x\}\)that takes the value 1 when𝒙\\bm\{x\}satisfiesFFand 0 otherwise, where𝒙=\(x1,…,xn\)\\bm\{x\}=\(x\_\{1\},\\ldots,x\_\{n\}\)are the variables inFF\. Thus, any setFFof formulas is represented by a suitable BDD\.

Consider, for example, the setFFof formulas

x1​x2⊃\(x3​x¯4​x5​x¯6\)\(f1\)x¯1​x¯2⊃\(x¯4​x5​x¯6∨x3​x4​x5​x6\)\(f2\)\(x1​x¯2∨x¯1​x2\)⊃x¯3​x¯4​x¯5​x6\(f3\)\\begin\{array\}\[\]\{l@\{\\hspace\{4ex\}\}l\}x\_\{1\}x\_\{2\}\\supset\(x\_\{3\}\\bar\{x\}\_\{4\}x\_\{5\}\\bar\{x\}\_\{6\}\)\\hfil\\hskip 17\.22217pt&\(f\_\{1\}\)\\\\ \\bar\{x\}\_\{1\}\\bar\{x\}\_\{2\}\\supset\(\\bar\{x\}\_\{4\}x\_\{5\}\\bar\{x\}\_\{6\}\\vee x\_\{3\}x\_\{4\}x\_\{5\}x\_\{6\}\)\\hfil\\hskip 17\.22217pt&\(f\_\{2\}\)\\\\ \(x\_\{1\}\\bar\{x\}\_\{2\}\\vee\\bar\{x\}\_\{1\}x\_\{2\}\)\\supset\\bar\{x\}\_\{3\}\\bar\{x\}\_\{4\}\\bar\{x\}\_\{5\}x\_\{6\}\\hfil\\hskip 17\.22217pt&\(f\_\{3\}\)\\end\{array\}\(43\)where, for readability,xi​xjx\_\{i\}x\_\{j\}meansxi∧xjx\_\{i\}\\wedge x\_\{j\}andx¯i\\bar\{x\}\_\{i\}means¬xi\\neg x\_\{i\}\. The setFFis represented by theordered BDD333Often abbreviated OBDD\. We use the abbreviation BDD since only ordered BDDs are of interest here\.in Fig\.[5](https://arxiv.org/html/2607.15532#Ch0.F5)\(a\)\. The nodes of the BDD are arranged in layers that, except for the terminal node at the bottom, correspond to variablesx1,…,x6x\_\{1\},\\ldots,x\_\{6\}\. A dashed arc leaving a node in layeriitoward a layer below it represents settingxi=0x\_\{i\}=0, and a solid arc represetsxi=1x\_\{i\}=1\. Each path from top to bottom therefore represents an assignment to𝒙\\bm\{x\}\. The BDD is constructed so that the top\-to\-bottom paths correspond exactly to assignments that satisfy the formulas inFF\.444Classically, BDDs also contain paths to a second terminal node that represent non\-satisfying assignments, but these can be omitted for present purposes\.The BDD in Fig\.[5](https://arxiv.org/html/2607.15532#Ch0.F5)\(a\) isreducedin the sense that no smaller BDD that uses the same variable ordering represents \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\)\. In fact, any given Boolean function is uniquely represented by a reduced BDD with a specified variable ordering[Bry92](https://arxiv.org/html/2607.15532#bib.bib28)\. Methods for constructing reduced BDDs are described in[Weg00](https://arxiv.org/html/2607.15532#bib.bib129);[Weg04](https://arxiv.org/html/2607.15532#bib.bib130)\.

![Refer to caption](https://arxiv.org/html/2607.15532v1/x6.png)

![Refer to caption](https://arxiv.org/html/2607.15532v1/x7.png)

![Refer to caption](https://arxiv.org/html/2607.15532v1/x8.png)

Figure 5:\(a\) Reduced binary decision diagram for a small set of logical propositions\. \(b\) Reduced BDD after fixingx2=1x\_\{2\}=1\. \(c\) Reduced BDD after fixing\(x2,x4,x6\)=\(1,0,1\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)=\(1,0,1\)\.Let’s suppose that we wish to know what can be deduced from \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\) regarding the variablesx2x\_\{2\},x4x\_\{4\}, andx6x\_\{6\}\. To deduce all formulas containingx2,x4,x6x\_\{2\},x\_\{4\},x\_\{6\}that are implied by \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\), we can derive the BDDB′B^\{\\prime\}that results fromBBby projecting out variablesx1,x3,x5x\_\{1\},x\_\{3\},x\_\{5\}\. Then the top\-to\-bottom paths inB′B^\{\\prime\}correspond to the assignments in the projection onto\(x2,x4,x6\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)\. The deducible formulas are then easily obtained from this projection, as we will illustrate shortly\.

The classical method for projecting out a variablexix\_\{i\}proceeds by first obtaining the BDDsB1B\_\{1\}andB0B\_\{0\}that result from settingxix\_\{i\}to 1 and 0, respectively, and then computingB′B^\{\\prime\}by taking the disjunction ofB1B\_\{1\}andB0B\_\{0\}\. However, the disjunction operation on BDDs tends to be quite expensive, and it must be performed recursively for each variable to be projected out\.

Since we wish to project \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\) onto a small number of variables, it is more efficient to check directly which assignments to\(x2,x4,x6\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)are represented by top\-to\-bottom paths inBB\. Suppose, for example, we first check\(x2,x4,x6\)=\(1,1,1\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)=\(1,1,1\)\. We might begin by settingx2=1x\_\{2\}=1and removing the dashed arcs corresponding tox2=0x\_\{2\}=0in Fig\.[5](https://arxiv.org/html/2607.15532#Ch0.F5)\(a\)\. This permits the removal of several arcs and nodes because they no longer lie on a top\-to\-bottom path, resulting in the smaller BDD of Fig\.[5](https://arxiv.org/html/2607.15532#Ch0.F5)\(b\)\. Now if we try settingx4=1x\_\{4\}=1and remove all dashed arcs corresponding tox4=0x\_\{4\}=0, this causes all remaining arcs to be removed\. Since this already eliminates all top\-to\-bottom paths,\(x2,x4,x6\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)can be neither\(1,1,0\)\(1,1,0\)nor\(1,1,1\)\(1,1,1\)\. Now if we try\(x2,x4,x6\)=\(1,0,1\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)=\(1,0,1\), the BDD reduces to that in Fig\.[5](https://arxiv.org/html/2607.15532#Ch0.F5)\(c\)\. Since there is a top\-to\-bottom path \(in this case, a single such path\), we conclude that\(1,0,1\)\(1,0,1\)is part of the projection\. Continuing in this fashion, we find that the projection onto\(x2,x4,x6\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)is

\{\(1,0,1\),\(1,0,0\),\(0,1,1\),\(0,0,1\),\(0,0,0\)\}\\big\\\{\(1,0,1\),\(1,0,0\),\(0,1,1\),\(0,0,1\),\(0,0,0\)\\big\\\}\(44\)It is readily seen that these are the satisfying assignments of the formulasx2⊃¬x4x\_\{2\}\\supset\\neg x\_\{4\}andx4⊃x6x\_\{4\}\\supset x\_\{6\}\. These formulas therefore represent everything that can be deduced from \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\) regarding variablesx2,x4,x6x\_\{2\},x\_\{4\},x\_\{6\}\.

A possible barrier to the use of reduced BDDs is their ability to grow exponentially with the number of variables\. However, the size of the BDD depends on other factors as well\. For example, the knowledge base may decouple into sections that deal with different topics and therefore have no variables in common\. In such cases, a BDD can be generated for each section independently of the others, resulting in much smaller diagrams\. A generalization of this approach exploits the structure of the dependency graph of the knowledge base\. The dependency graph contains a vertex for every formula, and two vertices are connected by an edge when the corresponding formulas have at least one variable in common\. The complexity of logical inference is at worst exponential in the treewidth of the dependency graph, which tends to be small when the formulas are loosely coupled\. In such cases, one can build a nonserial BDD as described in[Hoo13](https://arxiv.org/html/2607.15532#bib.bib67), which can be markedly smaller than a conventional serial BDD and is quite suitable for computing projections\. In addition, the size of a serial or nonserial BDD can be very sensitive to the ordering of the variables, and it may be possible to find an ordering that results in a much smaller diagram[Weg00](https://arxiv.org/html/2607.15532#bib.bib129);[Weg04](https://arxiv.org/html/2607.15532#bib.bib130)\. Finally, given that AI’s large language models are based on neural networks that may contain upwards of a trillion parameters, a very large BDD may be acceptable in AI applications\.

### 6\.2Projection with Benders Decomposition

The previous section showed how to compute the projection of \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\) onto\(x2,x4,x6\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)by employing a decision diagram to check every possible assignment to these variables for consistency with \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\)\. It is generally possible, however, to accelerate this process significantly by applying Benders decomposition\. This popular optimization technique was originally applied to mixed integer programming[Ben62](https://arxiv.org/html/2607.15532#bib.bib15), but we use a generalization known as logic\-based Benders decomposition \(LBBD\)[Hoo00](https://arxiv.org/html/2607.15532#bib.bib66);[Hoo24](https://arxiv.org/html/2607.15532#bib.bib69);[HooOtt03](https://arxiv.org/html/2607.15532#bib.bib70)\.

LBBD is applied to a general optimization problem of the form

max⁡\{f​\(𝒙,𝒚\)\|\(𝒙,𝒚\)∈S,𝒙∈D𝒙,𝒚∈D𝒚\}\\max\\big\\\{f\(\\bm\{x\},\\bm\{y\}\)\\;\\big\|\\;\(\\bm\{x\},\\bm\{y\}\)\\in S,\\;\\bm\{x\}\\in D\_\{\\bm\{x\}\},\\;\\bm\{y\}\\in D\_\{\\bm\{y\}\}\\big\\\}whereD𝒙D\_\{\\bm\{x\}\}andD𝒚D\_\{\\bm\{y\}\}are the domains of𝒙\\bm\{x\}and𝒚\\bm\{y\}, respectively \(e\.g\., tuples of integers or reals\)\. For our purposes, we can restrict attention to problems in which the objective function depends only on𝒙\\bm\{x\}:

max⁡\{f​\(𝒙\)\|\(𝒙,𝒚\)∈S,𝒙∈D𝒙,𝒚∈D𝒚\}\\max\\big\\\{f\(\\bm\{x\}\)\\;\\big\|\\;\(\\bm\{x\},\\bm\{y\}\)\\in S,\\;\\bm\{x\}\\in D\_\{\\bm\{x\}\},\\;\\bm\{y\}\\in D\_\{\\bm\{y\}\}\\big\\\}\(45\)The problem is decomposed into a master problem

max⁡\{f​\(𝒙\)\|Benders cuts,𝒙∈D𝒙\}\\max\\big\\\{f\(\\bm\{x\}\)\\;\\big\|\\;\\mbox\{Benders cuts\},\\;\\bm\{x\}\\in D\_\{\\bm\{x\}\}\\big\\\}and a feasibility subproblem that asks whether\(𝒙¯,𝒚\)∈S\(\\bar\{\\bm\{x\}\},\\bm\{y\}\)\\in Sfor some𝒚∈D𝒚\\bm\{y\}\\in D\_\{\\bm\{y\}\}, where𝒙¯\\bar\{\\bm\{x\}\}is the most recent solution of the master problem\. If the subproblem has a feasible solution𝒚¯\\bar\{\\bm\{y\}\}, the original problem \([45](https://arxiv.org/html/2607.15532#Ch0.E45)\) has optimal solution\(𝒙¯,𝒚¯\)\(\\bar\{\\bm\{x\}\},\\bar\{\\bm\{y\}\}\)\. If the subproblem is infeasible, the proof of infeasibility is analyzed to obtain a valid constraint \(Benders cut\)𝒙∈S𝒙¯\\bm\{x\}\\in S\_\{\\bar\{\\bm\{x\}\}\}that is violated by𝒙=𝒙¯\\bm\{x\}=\\bar\{\\bm\{x\}\}as well as by other values of𝒙\\bm\{x\}that the same proof shows to be infeasible\. The Benders cut is added to the constraint set of the master problem, which is re\-solved to obtain the next𝒙¯\\bar\{\\bm\{x\}\}\. The process continues until \(a\) the subproblem is feasible, or \(b\) the master problem is infeasible \(in which case the original problem infeasible\)\.

Of greatest interest to us is the fact that Benders cuts generated during this process at least partially define the projection of the feasible set of \([45](https://arxiv.org/html/2607.15532#Ch0.E45)\) onto𝒙\\bm\{x\}\. A complete description of the projection can be obtained simply by adding the constraint𝒙≠𝒙¯\\bm\{x\}\\neq\\bar\{\\bm\{x\}\}to the master problem \(and continuing to generate cuts\) each time an optimal solution\(𝒙¯,𝒚¯\)\(\\bar\{\\bm\{x\}\},\\bar\{\\bm\{y\}\}\)is found\. When the master problem finally becomes infeasible, the accumulated Benders cuts completely describe the projection onto𝒙\\bm\{x\}\.

To project \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\) onto\(x2,x4,x6\)\(x\_\{2\},x\_\{4\},x\_\{6\}\), we solve the problem

max⁡\{x2\+x4\+x6\|\([43](https://arxiv.org/html/2607.15532#Ch0.E43)\)\}\\max\\big\\\{x\_\{2\}\+x\_\{4\}\+x\_\{6\}\\;\\big\|\\;\\eqref\{eq:proj10\}\\big\\\}\(46\)by LBBD as follows\.555We could just as well minimize, or replace anyxix\_\{i\}by−xi\-x\_\{i\}\.We let𝒙=\(x2,x4,x6\)\\bm\{x\}=\(x\_\{2\},x\_\{4\},x\_\{6\}\)and𝒚=\(x1,x3,x5\)\\bm\{y\}=\(x\_\{1\},x\_\{3\},x\_\{5\}\), so that the master problem is the integer programming problem

max⁡\{x2\+x4\+x6\|Benders cuts,x2,x4,x6∈\{0,1\}\}\\max\\big\\\{x\_\{2\}\+x\_\{4\}\+x\_\{6\}\\;\\big\|\\;\\mbox\{Benders cuts\},\\;x\_\{2\},x\_\{4\},x\_\{6\}\\in\\\{0,1\\\}\\big\\\}\(47\)Initially there are no Benders cuts, and the solution is\(x2,x4,x6\)=\(1,1,1\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)=\(1,1,1\)\. This defines a subproblem that seeks a feasible solution of \([46](https://arxiv.org/html/2607.15532#Ch0.E46)\) in which\(x2,x4,x6\)=\(1,1,1\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)=\(1,1,1\)\. That is, we seek top\-to\-bottom path in the BDD of Fig\.[5](https://arxiv.org/html/2607.15532#Ch0.F5)\(a\) in which arcs corresponding to\(x2,x4,x6\)=\(0,0,0\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)=\(0,0,0\)are removed\. We solved this subproblem in the previous section by first fixingx1=1x\_\{1\}=1and generating the BDD of Fig\.[5](https://arxiv.org/html/2607.15532#Ch0.F5)\(b\)\. At this point we noted that\(x2,x4\)=\(1,1\)\(x\_\{2\},x\_\{4\}\)=\(1,1\)is already infeasible\. This allows us to create a Benders cut \(specifically, anogood constraint\) that excludes solutions in which\(x2,x4\)=\(1,1\)\(x\_\{2\},x\_\{4\}\)=\(1,1\)\. We write the cut as\(1−x2\)\+\(1−x4\)≥1\(1\-x\_\{2\}\)\+\(1\-x\_\{4\}\)\\geq 1and add it to the master problem \([47](https://arxiv.org/html/2607.15532#Ch0.E47)\)\. Re\-solving the master problem, we obtain\(x2,x4,x6\)=\(1,0,1\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)=\(1,0,1\), which defines a feasible subproblem and therefore solves \([46](https://arxiv.org/html/2607.15532#Ch0.E46)\)\. To continue generating Benders cuts, we add the constraint\(x2,x4,x6\)≠\(1,0,1\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)\\neq\(1,0,1\)to the master problem by writing\(1−x2\)\+x4\+\(1−x6\)≥1\(1\-x\_\{2\}\)\+x\_\{4\}\+\(1\-x\_\{6\}\)\\geq 1\. After generating the optimal solutions \([44](https://arxiv.org/html/2607.15532#Ch0.E44)\) in this fashion, the master problem becomes infeasible, and we have the projection onto\(x2,x4,x6\)\(x\_\{2\},x\_\{4\},x\_\{6\}\)\. In larger instances, the Benders cuts speed up this process by eliminating many infeasible assignments to the master problem variables before they are submitted to the subproblem\.

## 7Transparency through Postoptimality Analysis

Optimization\-based inference can contribute significantly to transparency in AI applications by means of postoptimality analysis\. This type of analysis can identify constraints that are essential to proving optimality, and in many cases, whether or how much the optimal solution would change if the constraints were modified a given amount\. When applied to inference, postoptimality analysis can identify premises in the knowledge base that play a role in deriving inferred propositions, and perhaps determine whether and how much the inferred propositions would change if the premises were modified\.

We begin with a brief discussion of postoptimality analysis in linear programming, which we applied in earlier sections to probabilistic logic and various belief logics\. We then describe two methods of postoptimality analysis for mixed integer/linear programming \(MILP\), which we applied to nonmonotonic logic, multivalued logic, Boolean regression, and inference via projection\. One is an inference\-based method that uses dual multipliers obtained in the branch\-and\-bound search tree\. The other is based on a BDD that encodes near\-optimal solutions of the problem\.

### 7\.1Postoptimality Analysis in Linear Programming

Postoptimality analysis in linear programming \(LP\) consists primarily of elementary techniques that have been implemented in LP solvers for decades\. An LP problem has the form

min⁡\{𝒄⊺​𝒙\|A​𝒙≥𝒃,𝒙≥𝟎\}\\min\\big\\\{\\bm\{c\}^\{\\intercal\}\\bm\{x\}\\;\\big\|\\;A\\bm\{x\}\\geq\\bm\{b\},\\;\\bm\{x\}\\geq\\bm\{0\}\\big\\\}\(48\)The correspondingdualproblem is

max⁡\{𝒖⊺​𝒃\|𝒖⊺​A≤𝒄⊺,𝒖≥𝟎\}\\max\\big\\\{\\bm\{u\}^\{\\intercal\}\\bm\{b\}\\;\\big\|\\;\\bm\{u\}^\{\\intercal\}A\\leq\\bm\{c\}^\{\\intercal\},\\;\\bm\{u\}\\geq\\bm\{0\}\\big\\\}The dual variables𝒖=\(u1,…,um\)\\bm\{u\}=\(u\_\{1\},\\ldots,u\_\{m\}\)correspond to themmconstraintsA​𝒙≥𝒃A\\bm\{x\}\\geq\\bm\{b\}of the original problem \([48](https://arxiv.org/html/2607.15532#Ch0.E48)\)\. Under weak conditions, an LP problem has the same optimal valuez∗z^\{\*\}as its dual, and the dual solution is obtained for free as a byproduct of solving the original problem\.

The optimal dual solution𝒖\\bm\{u\}is a key to postoptimality analysis\. The dual multiplieruiu\_\{i\}associated with constraintiiofA​𝒙≥𝒃A\\bm\{x\}\\geq\\bm\{b\}tells us that if the right\-hand sidebib\_\{i\}of constraintiiis changed tobi\+Δ​bib\_\{i\}\+\\Delta b\_\{i\}\(whereΔ​bi\\Delta b\_\{i\}can be negative\), the resulting optimal value is at leastz∗\+ui​Δ​biz^\{\*\}\+u\_\{i\}\\Delta b\_\{i\}\. Also, one can easily compute a range of perturbationsΔ​bi\\Delta b\_\{i\}within which the new optimal value isexactlyz∗\+ui​Δ​biz^\{\*\}\+u\_\{i\}\\Delta b\_\{i\}\. A consequence of this is that only constraints with positive dual multipliersuiu\_\{i\}serve as premises in the proof of optimality, and all other constraints can be dropped without changing the optimal solution\. In fact, it is not hard to state conditions under which this set of premises is irreducible, meaning that they are all essential to the proof\. This and related matters are studied in[Chi96](https://arxiv.org/html/2607.15532#bib.bib34);[Chi97](https://arxiv.org/html/2607.15532#bib.bib35);[Chi01](https://arxiv.org/html/2607.15532#bib.bib36);[ChiDra91](https://arxiv.org/html/2607.15532#bib.bib37)\.

As an example, consider the probabilistic logic problem instance discussed in Section[2\.1](https://arxiv.org/html/2607.15532#Ch0.S2.SS1), in which probablities 0\.9, 0\.8, and 0\.7 are assigned tox1x\_\{1\},x1⊃x2x\_\{1\}\\supset x\_\{2\}, andx2⊃x3x\_\{2\}\\supset x\_\{3\}, respectively\. The inferred probability range forx3x\_\{3\}is\[0\.5,0\.7\]\[0\.5,0\.7\]\. The lower limit 0\.5 is obtained by minimizing Pr\(x3\)\(x\_\{3\}\), and the resulting dual multipliers for the three probability assignments are all 1\.25\. So, reducing the assigned probability 0\.9 to 0\.8, for example, results in new a lower limit of at least0\.5−\(1\.25\)​\(0\.1\)=0\.3750\.5\-\(1\.25\)\(0\.1\)=0\.375\. In fact, the lower limit is exactly 0\.375, because this calculation is exact for any perturbationΔ​b1∈\[−0\.4,0\]\\Delta b\_\{1\}\\in\[\-0\.4,0\]\. As it happens any positive perturbation results in an infeasible problem, and similarly for the other two assigned probabilities\.666The calculated value remains a valid lower bound on the optimal value, because the optimal value of an infeasible minimization problem is∞\\infty\.The upper limit 0\.7, which results from maximizing Pr\(x3\)\(x\_\{3\}\), yields dual multipliers 0, 0, and 1 for the three assigned probabilities\. This means that only the propositionx2⊃x3x\_\{2\}\\supset x\_\{3\}plays a role in inferring the upper limit on Pr\(x3\)\(x\_\{3\}\), and the other two probability assignments can be dropped without affecting it\.

### 7\.2Inference\-Based MILP Postoptimality Analysis

An inference\-based method[DawHoo00](https://arxiv.org/html/2607.15532#bib.bib42)provides comprehensive postoptimality analysis for MILP when the problem has moderate size, and a limited analysis for larger instances\. We will suppose the integer\-valued variables in the problem are binary, in which case it has the form

min⁡\{z=𝒄⊺​𝒙\|A​𝒙≥𝒃,𝒙≥𝟎,xi∈\{0,1\}​for​i∈I\}\\min\\Big\\\{z=\\bm\{c\}^\{\\intercal\}\\bm\{x\}\\;\\big\|\\;A\\bm\{x\}\\geq\\bm\{b\},\\;\\bm\{x\}\\geq\\bm\{0\},\\;x\_\{i\}\\in\\\{0,1\\\}\\;\\mbox\{for\}\\;i\\in I\\big\\\}\(49\)It is convenient to suppose thatA​𝒙≥𝒃A\\bm\{x\}\\geq\\bm\{b\}contains constraintsxi≤1x\_\{i\}\\leq 1fori∈Ii\\in I\. Such problems are normally solved by a branch\-and\-bound method that builds a search tree by branching on binary variables\. For simplicity of exposition, we assume no cutting planes are added to the constraint set during the search\. Letz∗z^\{\*\}be the optimal value ofzzobtained for \([49](https://arxiv.org/html/2607.15532#Ch0.E49)\)\.

Inference\-based postoptimality analysis is based on dual solutions obtained at nodes of the search tree\. An LP relaxation of \([49](https://arxiv.org/html/2607.15532#Ch0.E49)\) is solved at each node of the tree, namely

min⁡\{zLP=𝒄⊺​𝒙\|A​𝒙≥𝒃,𝒙≥𝟎,D​𝒙≥𝒅\}\\min\\Big\\\{z\_\{\\mathrm\{LP\}\}=\\bm\{c\}^\{\\intercal\}\\bm\{x\}\\;\\big\|\\;A\\bm\{x\}\\geq\\bm\{b\},\\;\\bm\{x\}\\geq\\bm\{0\},\\;D\\bm\{x\}\\geq\\bm\{d\}\\big\\\}\(50\)whereD​𝒙≥𝒅D\\bm\{x\}\\geq\\bm\{d\}consists of branching constraints of the formxi≤0x\_\{i\}\\leq 0\(when branching toxi=0x\_\{i\}=0\) orxi≥1x\_\{i\}\\geq 1\(when branching toxi=1x\_\{i\}=1\) that are added along the path from the root of the tree to the current node\. If one or more of the 0–1 variables has a fractional value in the LP solution, the search creates two branches by settingxi=0x\_\{i\}=0andxi=1x\_\{i\}=1for one such variablexix\_\{i\}\.

The LP dual of \([50](https://arxiv.org/html/2607.15532#Ch0.E50)\) is

max⁡\{𝒖⊺​𝒃\+𝒗⊺​𝒅\|𝒖⊺​A\+𝒗⊺​D≤𝒄⊺,𝒖≥𝟎,𝒗≥𝟎\}\\max\\big\\\{\\bm\{u\}^\{\\intercal\}\\bm\{b\}\+\\bm\{v\}^\{\\intercal\}\\bm\{d\}\\;\\big\|\\;\\bm\{u\}^\{\\intercal\}A\+\\bm\{v\}^\{\\intercal\}D\\leq\\bm\{c\}^\{\\intercal\},\\;\\bm\{u\}\\geq\\bm\{0\},\\;\\bm\{v\}\\geq\\bm\{0\}\\big\\\}Let𝒙B\\bm\{x\}\_\{B\}be the variables fixed byB​𝒙≥𝒃B\\bm\{x\}\\geq\\bm\{b\}, and𝒙¯\\bar\{\\bm\{x\}\}the values to which they are fixed\. Then at each leaf node of the tree, one of three cases obtains:

\(a\) Problem \([50](https://arxiv.org/html/2607.15532#Ch0.E50)\) is infeasible\. Then there is a dual feasible extreme ray\(𝒖¯,𝒗¯\)\(\\bar\{\\bm\{u\}\},\\bar\{\\bm\{v\}\}\)for which𝒙B=𝒙¯B\\bm\{x\}\_\{B\}=\\bar\{\\bm\{x\}\}\_\{B\}violates the surrogate inequality𝒖¯⊺​A​𝒙≥𝒖¯⊺​𝒃\\bar\{\\bm\{u\}\}^\{\\intercal\}A\\bm\{x\}\\geq\\bar\{\\bm\{u\}\}^\{\\intercal\}\\bm\{b\}\.

\(b\) Problem \(50\) has an optimal solution𝒙¯\\bar\{\\bm\{x\}\}with valuez¯LP\\bar\{z\}\_\{\\mathrm\{LP\}\}in whichx¯j∈\{0,1\}\\bar\{x\}\_\{j\}\\in\\\{0,1\\\}forj∈Jj\\in J, which means that𝒙¯\\bar\{\\bm\{x\}\}is feasible in \([49](https://arxiv.org/html/2607.15532#Ch0.E49)\) and therefore a candidate solution\. Then if\(𝒖¯,𝒗¯\)\(\\bar\{\\bm\{u\}\},\\bar\{\\bm\{v\}\}\)is an optimal dual solution,𝒙B=𝒙¯B\\bm\{x\}\_\{B\}=\\bar\{\\bm\{x\}\}\_\{B\}violates the surrogate inequality𝒖¯⊺​A​𝒙−𝒄⊺​𝒙\>𝒖¯⊺​𝒃−z¯LP\\bar\{\\bm\{u\}\}^\{\\intercal\}A\\bm\{x\}\-\\bm\{c\}^\{\\intercal\}\\bm\{x\}\>\\bar\{\\bm\{u\}\}^\{\\intercal\}\\bm\{b\}\-\\bar\{z\}\_\{\\mathrm\{LP\}\}\.

\(c\) Problem \([50](https://arxiv.org/html/2607.15532#Ch0.E50)\) has an optimal solution with valuez¯LP\\bar\{z\}\_\{\\mathrm\{LP\}\}that is no smaller than the valuez¯min\\bar\{z\}\_\{\\min\}of the best candidate solution found so far\. Then if\(𝒖¯,𝒗¯\)\(\\bar\{\\bm\{u\}\},\\bar\{\\bm\{v\}\}\)is an optimal dual solution,𝒙B=𝒙¯B\\bm\{x\}\_\{B\}=\\bar\{\\bm\{x\}\}\_\{B\}violates the surrogate inequality𝒖¯⊺​A​𝒙−𝒄⊺​𝒙\>𝒖¯⊺​𝒃−z¯min\\bar\{\\bm\{u\}\}^\{\\intercal\}A\\bm\{x\}\-\\bm\{c\}^\{\\intercal\}\\bm\{x\}\>\\bar\{\\bm\{u\}\}^\{\\intercal\}\\bm\{b\}\-\\bar\{z\}\_\{\\min\}\.

To conduct postoptimality analysis, we first observe that if a constraintiihas a vanishing dual multiplieru¯i\\bar\{u\}\_\{i\}at every leaf node, then the constraint plays no role in the proof of optimality \(or infeasibility, but for simplicity we suppose that the problem is feasible\)\. Constraintiican therefore be dropped without changing the optimal solution\.

Beyond this, we can study which perturbations in the problem data allow one to prove an optimal value of at leastz∗z^\{\*\}\. We first observe that setting𝒙𝑩=𝒙¯𝑩\\bm\{x\}\_\{\\bm\{B\}\}=\\bar\{\\bm\{x\}\}\_\{\\bm\{B\}\}at a leaf node falsifies a logical clause that negates these settings\. For example, if a leaf node is reached by setting\(x1,x2,x3\)=\(1,0,1\)\(x\_\{1\},x\_\{2\},x\_\{3\}\)=\(1,0,1\), the clause¬x1∨x2∨¬x3\\neg x\_\{1\}\\vee x\_\{2\}\\vee\\neg x\_\{3\}is falsified\. We will call this the branching clause at the node\. Since the branching search is exhaustive, the set of branching clauses for all the leaf nodes is unsatisfiable\. We also observe that since𝒙𝑩=𝒙¯𝑩\\bm\{x\}\_\{\\bm\{B\}\}=\\bar\{\\bm\{x\}\}\_\{\\bm\{B\}\}violates the surrogate inequality at any given leaf node, the surrogate inequality must imply a logical clause that implies the branching clause at that node\. We will call this the surrogate clause\. To continue the example, if the surrogate inequality at the leaf node is−4​x1\+3​x2−2​x3≥−3\-4x\_\{1\}\+3x\_\{2\}\-2x\_\{3\}\\geq\-3, it implies the surrogate clause¬x1∨x2\\neg x\_\{1\}\\vee x\_\{2\}, which implies the branching clause¬x1∨x2∨¬x3\\neg x\_\{1\}\\vee x\_\{2\}\\vee\\neg x\_\{3\}\. We conclude that after a perturbation, the original search tree remains exhaustive and proves an optimal value of at leastz∗z^\{\*\}if the perturbed surrogate inequality still implies the original surrogate clause at each node\. The actual optimal value of the perturbed problem may, of course, be larger thanz∗z^\{\*\}\.

This analysis leads to a system of inequalities whose satisfaction by a perturbation ensures that the optimal value will not fall belowz∗z^\{\*\}\. For present purposes, it suffices to illustrate how this works in the many\-valued logic example presented in Section[4\.2](https://arxiv.org/html/2607.15532#Ch0.S4.SS2)\. Recall that the objective is to find the smallest truth valuet′t^\{\\prime\}for which we can infer≥t′​\(\(P⊃Q\)⊃¬P\)\\framebox\{$\\geq t^\{\\prime\}$\}\\,\(\(P\\supset Q\)\\supset\\neg P\), given≤p\\leq pP\\,Pand≤q\\leq qQ\\,Q\. For the sake of illiustration, we suppose\(p,q\)=\(0\.3,0\.7\)\(p,q\)=\(0\.3,0\.7\)\. The smallestt′t^\{\\prime\}is found by minimizingt′t^\{\\prime\}subject to the MILP constraint set in \([33](https://arxiv.org/html/2607.15532#Ch0.E33)\), which is reproduced below in a consistent format \(omitting nonnegativity constraints on the variables\):

1\.t′−δ′≥02\.−t\+v​\(P\)−δ′≥−23\.t−δ≥04\.−v​\(P\)\+v​\(Q\)−δ≥−15\.−v​\(Q\)≥−0\.7\(u1\)\(u2\)\(u3\)\(u4\)\(u5\)6\.t′\+δ′\+t\+v​\(P\)≥27\.−t≥−18\.t\+v​\(P\)−v​\(Q\)\+δ≥19\.−v​\(P\)≥−0\.3δ,δ′∈\{0,1\}\(u6\)\(u7\)\(u8\)\(u9\)\\begin\{array\}\[\]\{ll@\{\\hspace\{5ex\}\}ll\}\\begin\{array\}\[\]\{l\}1\.\\;\\;t^\{\\prime\}\-\\delta^\{\\prime\}\\geq 0\\\\ 2\.\\;\\;\-t\+v\(P\)\-\\delta^\{\\prime\}\\geq\-2\\\\ 3\.\\;\\;t\-\\delta\\geq 0\\\\ 4\.\\;\\;\-v\(P\)\+v\(Q\)\-\\delta\\geq\-1\\\\ 5\.\\;\\;\-v\(Q\)\\geq\-0\.7\\end\{array\}&\\begin\{array\}\[\]\{l\}\(u\_\{1\}\)\\\\ \(u\_\{2\}\)\\\\ \(u\_\{3\}\)\\\\ \(u\_\{4\}\)\\\\ \(u\_\{5\}\)\\end\{array\}\\hfil\\hskip 21\.52771pt&\\begin\{array\}\[\]\{l\}6\.\\;\\;t^\{\\prime\}\+\\delta^\{\\prime\}\+t\+v\(P\)\\geq 2\\\\ 7\.\\;\\;\-t\\geq\-1\\\\ 8\.\\;\\;t\+v\(P\)\-v\(Q\)\+\\delta\\geq 1\\\\ 9\.\\;\\;\-v\(P\)\\geq\-0\.3\\\\ \\;\\;\\;\\;\\;\\delta,\\delta^\{\\prime\}\\in\\\{0,1\\\}\\end\{array\}&\\begin\{array\}\[\]\{l\}\(u\_\{6\}\)\\\\ \(u\_\{7\}\)\\\\ \(u\_\{8\}\)\\\\ \(u\_\{9\}\)\\\\ \\end\{array\}\\end\{array\}\(51\)The dual multipliersuiu\_\{i\}are indicated to the right of the constraints\. The search tree for this problem consists of three nodes, as shown in Fig\.[6](https://arxiv.org/html/2607.15532#Ch0.F6)\. Sinceδ′\\delta^\{\\prime\}is a fraction 0\.35 in the solution of the LP relaxation at the root node, the search branches onδ′\\delta^\{\\prime\}to create nodes 2 and 3\. The LP relaxation at node 2 has an integral solution with\(δ,δ′\)=\(0,0\)\(\\delta,\\delta^\{\\prime\}\)=\(0,0\)and optimal valuet¯LP′=0\.7\\bar\{t\}^\{\\prime\}\_\{\\mathrm\{LP\}\}=0\.7, so that case \(b\) applies\. The solution at node 3 is nonintegral, but since the optimal valuet¯LP′=1\\bar\{t\}^\{\\prime\}\_\{\\mathrm\{LP\}\}=1is worse than the best previous solution value 0\.7, case \(c\) applies, and there is no need for further branching\. The minimum value oft′t^\{\\prime\}is therefore 0\.7, and so\(P⊃Q\)⊃¬P\(P\\supset Q\)\\supset\\neg Phas a truth value no less than 0\.7\.

![Refer to caption](https://arxiv.org/html/2607.15532v1/x9.png)Figure 6:Branch\-and\-bound search tree for the multi\-valued logic problem \([33](https://arxiv.org/html/2607.15532#Ch0.E33)\)\. Only nonzero dual multipliersuiu\_\{i\}are indicated\. The surrogate inequalities reflect a perturbation of the problem data\.We are particularly interested in the sensitivity of the solution to changes in truth value bounds\(p,q\)=\(0\.3,0\.7\)\(p,q\)=\(0\.3,0\.7\), which are encoded in constraints 5 and 9\. Figure[6](https://arxiv.org/html/2607.15532#Ch0.F6)indicates the nonzero dual multipliers at each leaf node, and we note that the multiplieru5u\_\{5\}corresponding tov​\(Q\)≤0\.7v\(Q\)\\leq 0\.7is zero at both leaf nodes\. This means that the lower bound of 0\.7 on the truth value of\(P⊃Q\)⊃¬P\(P\\supset Q\)\\supset\\neg Premains valid even if the bound onv​\(Q\)v\(Q\)is dropped\.777This does not mean that the bound onv​\(Q\)v\(Q\)cannot affect the actual minimum value oft′t^\{\\prime\}\. For example, settingv​\(Q\)=0\.1v\(Q\)=0\.1results int¯′=0\.9\\bar\{t\}^\{\\prime\}=0\.9\. Yett¯′\\bar\{t\}^\{\\prime\}is still at least 0\.7\.

To proceed to a deeper analysis, we begin by examining node 2\. To obtain the surrogate inequality, we first take a linear combination of perturbed constraints 6, 7, and 9 with multipliers\(u6,u7,u9\)=\(1,1,1\)\(u\_\{6\},u\_\{7\},u\_\{9\}\)=\(1,1,1\)\. Constraint 9 is perturbed by replacing the bound0\.30\.3with0\.3\+Δ​p0\.3\+\\Delta pto allow us to account for the effect of perturbations in this bound\. Constraint 6 is perturbed by replacingt′t^\{\\prime\}witht′\+Δ​t′t^\{\\prime\}\+\\Delta t^\{\\prime\}to permit an investigation of which lower bounds fort′t^\{\\prime\}other than0\.70\.7can be proved after the perturbation\. Since case \(b\) applies to node 2, we get the surrogate inequalityδ′\>−Δ​p−Δ​t′\\delta^\{\\prime\}\>\-\\Delta p\-\\Delta t^\{\\prime\}\. This implies the single\-literal clauseδ′\\delta^\{\\prime\}whenΔ​p=Δ​t′=0\\Delta p=\\Delta t^\{\\prime\}=0, which means thatδ′\\delta^\{\\prime\}is the surrogate clause\. The surrogate inequality continues to imply clauseδ′\\delta^\{\\prime\}as long as

Δ​p\+Δ​t′≤0\\Delta p\+\\Delta t^\{\\prime\}\\leq 0\(52\)Node 3, which corresponds to case \(c\), similarly yields the surrogate inequality−δ′\>−0\.7−Δ​t′\-\\delta^\{\\prime\}\>\-0\.7\-\\Delta t^\{\\prime\}\. This implies the clause¬δ′\\neg\\delta^\{\\prime\}whenΔ​t′=0\\Delta t^\{\\prime\}=0, which is therefore the surrogate clause\. The surrogate inequality continues to imply¬δ′\\neg\\delta^\{\\prime\}as long as

Δ​t′≤0\.3\\Delta t^\{\\prime\}\\leq 0\.3\(53\)The lower bound0\.70\.7remains proven fort′t^\{\\prime\}as long as the perturbationΔ​p\\Delta psatisfies \([52](https://arxiv.org/html/2607.15532#Ch0.E52)\) and \([53](https://arxiv.org/html/2607.15532#Ch0.E53)\) withΔ​t′=0\\Delta t^\{\\prime\}=0; that is, as long asΔ​p≤0\\Delta p\\leq 0, which is to say thatpp\(currently 0\.3\) can be reduced but not increased\.

If we wish to know under what conditions a lower bound of 0\.9 \(rather than 0\.7\) can be proved fort′t^\{\\prime\}, we can letΔ​t′=0\.2\\Delta t^\{\\prime\}=0\.2in \([52](https://arxiv.org/html/2607.15532#Ch0.E52)\) and \([53](https://arxiv.org/html/2607.15532#Ch0.E53)\)\. SinceΔ​t′=0\.2\\Delta t^\{\\prime\}=0\.2satisfies \([53](https://arxiv.org/html/2607.15532#Ch0.E53)\), condition \([52](https://arxiv.org/html/2607.15532#Ch0.E52)\) tells us thatΔ​p≤−0\.2\\Delta p\\leq\-0\.2suffices to provet′≥0\.7\+0\.2t^\{\\prime\}\\geq 0\.7\+0\.2\. Thus if the upper bound onv​\(P\)v\(P\)is reduced from 0\.3 to to 0\.1, a lower bound of 0\.9 can be proved for the truth value of\(P⊃Q\)⊃¬P\(P\\supset Q\)\\supset\\neg P, regardless of the bound \(if any\) given forv​\(Q\)v\(Q\)\. As it happens, this is exactly the optimal value oft′t^\{\\prime\}after the perturbation\.

The upshot of this analysis is that\(P⊃Q\)⊃¬P\(P\\supset Q\)\\supset\\neg Phas a truth value of at least 0\.7, given thatPP’s truth value is at most 0\.3, regardless of the upper bound we place onQQ’s truth value\. The guaranteed truth value 0\.7 remains valid so long as the upper bound 0\.3 onPP’s truth value is not relaxed\. In fact, if it is tightened \(reduced\), the guaranteed truth value of\(P⊃Q\)⊃¬P\(P\\supset Q\)\\supset\\neg Pincreases by an equal amount, but if it is relaxed, the guaranteed truth value is reduced by an equal amount\.

The practicality of this type of comprehensive analysis depends on the number of leaf nodes that generate relevant surrogate inequalities\. The total of number of leaf nodes can be very large, but it is likely that only a fraction of them generate surrogate inequalities that contain perturbation terms for the constraints of interest\. The remainder of the leaf nodes can be ignored\. If we are interested only in learning which constraints play a role in deducing the optimal solution, we need only observe which constraints have a positive dual multiplier in at least one leaf node\. There is no need to generate and store surrogate inequalities\. This limited form of analysis can be performed on any problem instance that can be solved by a branch\-and\-bound method\.

### 7\.3MILP Postoptimality Analysis with Decision Diagrams

A second method of postoptimality analysis for MILP, described in[SerHoo20](https://arxiv.org/html/2607.15532#bib.bib117), generates a BDD that represents near\-optimal solutions of the problem\. Such a BDD is convenient for conducting several types of postoptimality analysis\. One can efficiently build a BDD that compactly stores all such solutions during the normal branch\-and\-bound search for an optimal solution\. A simple procedure \(“sound reduction”\) allows it to be further compressed, often by several orders of magnitude, by introducing certain infeasible solutions that do not affect postoptimality analysis\. As a result, very large optimization problems can be analyzed in this fashion\.

We illustrate the idea by applying it to the problem of inference in propositional logic\. Consider again the setF=\{f1,f2,f3\}F=\\\{f\_\{1\},f\_\{2\},f\_\{3\}\\\}of formulas listed in \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\)\. Suppose we wish to determine the minimum number of atomic propositionsxix\_\{i\}that can be false ifFFis to be satisfied\. This can be ascertained by minimizing∑i\(1−xi\)\\sum\_\{i\}\(1\-x\_\{i\}\)subject toFF, a problem that can be solved by integer programming\. As it happens, at least two variables must be false\. We would like to know which of the formulas inFFplay a role in this deduction\.

This question can be addressed by introducing 0–1 variablesy1,y2,y3y\_\{1\},y\_\{2\},y\_\{3\}that respectively indicate whetherf1,f2,f3f\_\{1\},f\_\{2\},f\_\{3\}are enforced\. We augmentFFby adding formulasyi⊃fiy\_\{i\}\\supset f\_\{i\}fori=1,2,3i=1,2,3to obtainF′F^\{\\prime\}\. The minimum of∑i\(1−xi\)\\sum\_\{i\}\(1\-x\_\{i\}\)subject toF′F^\{\\prime\}is of course zero, since theyiy\_\{i\}s can all be 0, in which case nofif\_\{i\}is enforced\. However, we can investigate the role of thefif\_\{i\}s by building a BDD that represents certainnear\-optimal solutionsof this problem; namely, solutions with value 0, 1, or 2\. Such a BDD appears in Fig\.[7](https://arxiv.org/html/2607.15532#Ch0.F7)\(a\)\.

![Refer to caption](https://arxiv.org/html/2607.15532v1/x10.png)

![Refer to caption](https://arxiv.org/html/2607.15532v1/x11.png)

![Refer to caption](https://arxiv.org/html/2607.15532v1/x12.png)

Figure 7:\(a\) BDD for postoptimality analysis of inference from formulas \([43](https://arxiv.org/html/2607.15532#Ch0.E43)\)\. \(b\) BDD after fixing\(y1,y2,y3\)=\(1,1,1\)\(y\_\{1\},y\_\{2\},y\_\{3\}\)=\(1,1,1\)\. \(c\) BDD after fixing\(y1,y2,y3\)=\(1,0\)\(y\_\{1\},y\_\{2\},y\_\{3\}\)=\(1,0\)\. Thick arcs indicate optimal values of𝒙\\bm\{x\}\.An optimal solution subject toF′F^\{\\prime\}can be found by solving an easy shortest path problem in the BDD of Fig\.[7](https://arxiv.org/html/2607.15532#Ch0.F7)\(a\)\. Since we are minimizing the number of falsexix\_\{i\}s, we place a cost \(length\) of 1 on dashed arcs in Fig,[7](https://arxiv.org/html/2607.15532#Ch0.F7)that correspond to values of thexix\_\{i\}s, and view all other arcs as having cost 0\. The shortest top\-to\-bottom path has zero cost, indicating that an optimal solution has value 0, as expected\. Now we can determine the result of enforcing any subset offif\_\{i\}s by fixing the correspondingyiy\_\{i\}s to 1 and computing shortest paths in the simplified BDD that results\.

We can see right away thatf2f\_\{2\}has no bearing on the problem, since the value ofy2y\_\{2\}has no effect on any path length\. If we enforce all thefif\_\{i\}s by fixing allyiy\_\{i\}s to 1, we get the BDD in Fig\.[7](https://arxiv.org/html/2607.15532#Ch0.F7)\(b\), in which the shortest path length is 2, as expected\. If we enforce onlyf1f\_\{1\}, we obtain the BDD of Fig\.[7](https://arxiv.org/html/2607.15532#Ch0.F7)\(c\), in which the shortest path has length 1\. Thus without premisef3f\_\{3\}, the minimum number of false atoms drops to 1\. It is similarly shown that withoutf1f\_\{1\}, the number drops to 0\.

The BDDs also allow inferences regarding possible values of the variablesxix\_\{i\}\. If all three formulas are enforced, as in Fig\.[7](https://arxiv.org/html/2607.15532#Ch0.F7)\(b\), we see immediately that the number of false atoms can be reduced to 2 only by settingx3x\_\{3\}andx5x\_\{5\}to true\. If we enforce onlyf1f\_\{1\}, as in Fig\.[7](https://arxiv.org/html/2607.15532#Ch0.F7)\(c\), we see that the number of false atoms can be reduced to 1 only by settingx1x\_\{1\}orx2x\_\{2\}to false\.

## 8Answer Set Programming Modulo Theories

Optimization can play an important role when logical and arithmetical constraints appear in the same problem\. This occurs, for example, when a propositional satisfiability \(SAT\) problem is enhanced with constraints involving integers or real numbers, resulting in aSAT modulo theory\(SMT\)[BarTin18](https://arxiv.org/html/2607.15532#bib.bib10);[TanWanHe24](https://arxiv.org/html/2607.15532#bib.bib128)\. The term refers to the fact that the logical propositions are evaluated in the context of \(“modulo”\) a specific mathematical theory, such as linear equations or inequalities\.

SMTs are not primarily identified with AI, since they have many applications in other areas, such as hardware and software verification and general combinatorial problem solving\. However, a similar problem class based onanswer set programming\(ASP\) is more closely related to AI, due to its use of default logic rather than a traditional SAT problem[ErdGelLeo16](https://arxiv.org/html/2607.15532#bib.bib51);[JanNie16](https://arxiv.org/html/2607.15532#bib.bib74);[Lif99](https://arxiv.org/html/2607.15532#bib.bib92);[Lif08](https://arxiv.org/html/2607.15532#bib.bib93);[MarTru99](https://arxiv.org/html/2607.15532#bib.bib96);[Nie99](https://arxiv.org/html/2607.15532#bib.bib108)\. Like a SAT problem, a default logic problem can be combined with arithmetical or other types of constraints, resulting in anASP modulo theory[GebKamKauOstSchWan16](https://arxiv.org/html/2607.15532#bib.bib52);[JanKamOstSchWanSch17](https://arxiv.org/html/2607.15532#bib.bib73);[LeeMen13](https://arxiv.org/html/2607.15532#bib.bib90)\. Some applications of ASP modulo theories are described in[BarLee14](https://arxiv.org/html/2607.15532#bib.bib11);[LeeMen13](https://arxiv.org/html/2607.15532#bib.bib90);[Lie23](https://arxiv.org/html/2607.15532#bib.bib91);[VarMen24](https://arxiv.org/html/2607.15532#bib.bib124);[WalSchBha17](https://arxiv.org/html/2607.15532#bib.bib126)\. We show how an optimization method such as linear or integer programming can play a key role when arithmetical constraints are involved\.

ASP modulo theories \(as well as SMTs\) are closely related to logic\-based Benders decomposition \(LBBD\), an optimization method we applied to projection problems in Section[6](https://arxiv.org/html/2607.15532#Ch0.S6)\. The default logic problem can be regarded as a master problem with propositional variablesxix\_\{i\}\. The subproblem can be a numerical constraint set whose feasibility can be checked with a linear or integer programming solver\. For example, the subproblem may consist of linear inequalities that are activated by a model\{xi\|i∈I\}\\\{x\_\{i\}\\;\|\\;i\\in I\\\}obtained when solving the master problem\. That is, the subproblem may consist of constraints of the formxi→𝒂i​𝒚≤bix\_\{i\}\\rightarrow\\bm\{a\}^\{i\}\\bm\{y\}\\leq b\_\{i\}, where𝒚≥𝟎\\bm\{y\}\\geq\\bm\{0\}is a vector of real\-valued variables\. An infeasible subproblem generates a Benders cut in the form of a nogood constraint⋁i∈I′¬xi\\bigvee\_\{i\\in I^\{\\prime\}\}\\neg x\_\{i\}, whereI′I^\{\\prime\}indexes a subset of the model that is responsible for the infeasibility\. A stable model can be found by repeatedly using LBBD to find minimal models of the combined logical and inequality constraints, until a model is found that is also minimal in the corresponding Gelfond\-Lifschitz \(G\-L\) transform of the logical constraints\.

As an example, consider the default logic problem \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\) with the following additional constraints

x1→3​y1\+2​y2≤6x2→−3​y1\+y2≤−9x3→−2​y1−5​y2≤−10y1,y2≥0\\begin\{array\}\[\]\{l\}x\_\{1\}\\rightarrow 3y\_\{1\}\+2y\_\{2\}\\leq 6\\\\ x\_\{2\}\\rightarrow\-3y\_\{1\}\+y\_\{2\}\\leq\-9\\\\ x\_\{3\}\\rightarrow\-2y\_\{1\}\-5y\_\{2\}\\leq\-10\\\\ y\_\{1\},y\_\{2\}\\geq 0\\end\{array\}\(54\)The goal is to identify a stable model, which can be found by enumerating minimal models of the constraints in \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\) and \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\), until a model is found that is also minimal in the G\-L transform of \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\)\. If no such model is found, the problem has no stable model\.

To find a minimal model of the constraints in \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\) and \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\), we first use integer programming \(as in Section[4\.1](https://arxiv.org/html/2607.15532#Ch0.S4.SS1)\) to find a minimal model of the master problem \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\)\. We then use linear programming \(LP\) to check whether the inequalities in the subproblem \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\) that are enforced by this model can be satisfied\. If not, we consult the dual solution of the LP to generate a Benders cut in the form of a nogood constraint that excludes the infeasible model\. We then generate another minimal model by solving the master problem subject to the nogood constraint\. We continue in this fashion, generating nogood constraints as needed, until finding a minimal model that satisfies \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\), or until the master problem is infeasible\.

The entire process in detail goes as follows\. We begin as in Section[4\.1](https://arxiv.org/html/2607.15532#Ch0.S4.SS1)by solving the integer programming problem \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\) to find a minimal model\{x1,x2\}\\\{x\_\{1\},x\_\{2\}\\\}of \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\)\. This model violates \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\) because it enforces the first two inequalites in \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\), and an LP solver determines that they cannot be satisfied wheny1,y2≥0y\_\{1\},y\_\{2\}\\geq 0\. If we associate dual variablesu1,u2u\_\{1\},u\_\{2\}with these inequalities, the LP solver yields a dual solution\(u1,u2\)=\(1,1\)\(u\_\{1\},u\_\{2\}\)=\(1,1\)that proves infeasibility\. Since both dual variables are positive, we know thatx1x\_\{1\}andx2x\_\{2\}are jointly responsible for the infeasibility\.888In general, the subsetSSof constraints corresponding to positive dual variables is infeasible\. However, proper subsets ofSSmay also be infeasible, and they would give rise to stronger nogood constraints\. The problem of finding an irreducible infeasible subset is discussed in[Chi96](https://arxiv.org/html/2607.15532#bib.bib34);[Chi97](https://arxiv.org/html/2607.15532#bib.bib35);[Chi01](https://arxiv.org/html/2607.15532#bib.bib36);[ChiDra91](https://arxiv.org/html/2607.15532#bib.bib37)\.We therefore generate a nogood clause¬x1∨¬x2\\neg x\_\{1\}\\vee\\neg x\_\{2\}to ensure that they do not both occur in a model\. \(If onlyu1u\_\{1\}were positive, we would generate a nogood clause consisting of the single literal¬x1\\neg x\_\{1\}\.\) We add the nogood clause \(in the formx1\+x2≤1x\_\{1\}\+x\_\{2\}\\leq 1\) to the integer programming problem \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\), which yields an optimal solution\(x1,…,x5\)=\(0,0,0,1,1\)\(x\_\{1\},\\dots,x\_\{5\}\)=\(0,0,0,1,1\)\. This solution vacuously satisfies \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\) because none of the inequalities in \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\) are enforced\. However, the corresponding model\{x4,x5\}\\\{x\_\{4\},x\_\{5\}\\\}is not minimal for the G\-L transform, which consists of the single proposition\(x1∧x4\)→x5\(x\_\{1\}\\wedge x\_\{4\}\)\\rightarrow x\_\{5\}\.

At this point we attempt to find another minimal model for the constraints in \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\) and \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\) by solving the integer programming problem \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\) with an additional constraintx4\+x5≤1x\_\{4\}\+x\_\{5\}\\leq 1to exclude the model found previously\. We also retain the nogood constraintx1\+x2≤1x\_\{1\}\+x\_\{2\}\\leq 1in \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\) because it remains valid\. The resulting solution\(x1,…,x5\)=\(1,0,1,0,1\)\(x\_\{1\},\\ldots,x\_\{5\}\)=\(1,0,1,0,1\)satisfies \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\), but the corresponding model\{x1,x3,x5\}\\\{x\_\{1\},x\_\{3\},x\_\{5\}\\\}is not minimal in the G\-L transform, which consists ofx1→x3x\_\{1\}\\rightarrow x\_\{3\},\(x1∧x4\)→x5\(x\_\{1\}\\wedge x\_\{4\}\)\\rightarrow x\_\{5\}, and→x1\\rightarrow x\_\{1\}\. The integer programming problem \([27](https://arxiv.org/html/2607.15532#Ch0.E27)\) becomes infeasible after adding a constraintx1\+x3\+x5≤2x\_\{1\}\+x\_\{3\}\+x\_\{5\}\\leq 2to exclude this last solution\. We conclude that the ASP modulo theory problem consisting of \([25](https://arxiv.org/html/2607.15532#Ch0.E25)\) and \([54](https://arxiv.org/html/2607.15532#Ch0.E54)\) has no stable model\.

## 9Possible Reserch Directions

Many opportunities remain for application of optimization methods to logical inference problems related to AI\. One avenue is to exploit the mathematical properties of semantics for various logics\. Boolean, probabilistic, belief, and nonmonotonic logics have already been discussed in the preceding pages\. Other possibilities include Kripke semantics for modal logics involving necessity and possibility \(S4 and S5\), as well as various semantics for epistemic, doxastic and deontic logics[BladeRijVen02](https://arxiv.org/html/2607.15532#bib.bib18);[BlavanBen06](https://arxiv.org/html/2607.15532#bib.bib19);[GioSai26](https://arxiv.org/html/2607.15532#bib.bib55);[Gol03](https://arxiv.org/html/2607.15532#bib.bib56);[GorOtt06](https://arxiv.org/html/2607.15532#bib.bib57);[vanDitHalHoeKoo15](https://arxiv.org/html/2607.15532#bib.bib123)\.

There are, in fact, deep connections between logical semantics and optimization theory that can serve as the basis for applying one to the other[BorChaMit02](https://arxiv.org/html/2607.15532#bib.bib23);[ChaHoo91](https://arxiv.org/html/2607.15532#bib.bib30);[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31);[ConCor94](https://arxiv.org/html/2607.15532#bib.bib39);[Jer89](https://arxiv.org/html/2607.15532#bib.bib77);[Wil09](https://arxiv.org/html/2607.15532#bib.bib132)\. Even traditional Boolean logic has a rich polyhedral structure when truth assignments are interpreted as vertices of a hypercube, which opens the door to specialized integer programming methods[ChaHoo99](https://arxiv.org/html/2607.15532#bib.bib31)\. The resolution method of propositional logic underlies the fundamental theorem of cutting plane theory in integer programming[Chv73](https://arxiv.org/html/2607.15532#bib.bib38), and resolvents are special cases of the Chvátal\-Gomory cuts widely used in integer programming solvers[ConCorZam14](https://arxiv.org/html/2607.15532#bib.bib40);[Hoo89](https://arxiv.org/html/2607.15532#bib.bib65);[NemWol99](https://arxiv.org/html/2607.15532#bib.bib104)\. An optimization\-oriented analysis of semantics that have been developed for various modal logics could lead to new and efficient inference methods\.

Still other possible research directions arise in the area of Bayesian and causal networks\. Optimization methods have already been applied to learning the structure of traditional Bayesian networks[BarCus17](https://arxiv.org/html/2607.15532#bib.bib12);[KitConGuoLiuCho23](https://arxiv.org/html/2607.15532#bib.bib84)as well as to maximum a posteriori \(MAP\) inference[DubLeeFla25](https://arxiv.org/html/2607.15532#bib.bib47);[SonMelGloJaaWei08](https://arxiv.org/html/2607.15532#bib.bib122)\. One could investigate extending these methods to networks that allow Boolean formulas in the manner of Bayesian logic \(Section[2\.4](https://arxiv.org/html/2607.15532#Ch0.S2.SS4)\)\. In addition, the large literature on causal networks[Pea95](https://arxiv.org/html/2607.15532#bib.bib112);[Pea00](https://arxiv.org/html/2607.15532#bib.bib113);[WeiPreFar25](https://arxiv.org/html/2607.15532#bib.bib131);[ZanOzkSte22](https://arxiv.org/html/2607.15532#bib.bib134)may offer further opportunities\. It may be possible, for example, to specialize inference methods for Bayesian logic to networks with causal structure, as well as to develop an analog of do\-calculus for Bayesian logic\. One might also adapt methods for optimizing causal interventions[VonVerdeNobelBraMalBacLaaKon24](https://arxiv.org/html/2607.15532#bib.bib125)to Bayesian logic\. Another possibility is to exploit the structure of small\-treewidth Bayesian logic problems\. This has long been done for traditional Bayesian networks[KorPar13](https://arxiv.org/html/2607.15532#bib.bib87);[LauSpi88](https://arxiv.org/html/2607.15532#bib.bib88);[PeyCrodeGivFraRobSabSchVig18](https://arxiv.org/html/2607.15532#bib.bib114), and as remarked in Section[6\.1](https://arxiv.org/html/2607.15532#Ch0.S6.SS1), small treewidth can also be exploited in logical inference\. The two approaches might be combined in the context of Bayesian logic, perhaps through nonserial dynamic programming, a concept known in the optimization community since the 1970s[BerBri72](https://arxiv.org/html/2607.15532#bib.bib17)\.

An intriguing possibility is to harness the full potential of projection, which we have seen is a generalization of both optimization and logical inference\. By projecting a knowledge base onto a subset of Boolean variables, one could not only answer queries as described in Section[6](https://arxiv.org/html/2607.15532#Ch0.S6), but create smaller, specialized rule bases for efficient application in particular domains\. It was noted in Section[6\.2](https://arxiv.org/html/2607.15532#Ch0.S6.SS2)that a projection onto discrete variables can be computed by running Benders decomposition to completion\. The linear programming models of belief logics require polyhedral projection, but it is a well\-studied \(if not particularly well\-solved\) problem in optimization theory[Bal98](https://arxiv.org/html/2607.15532#bib.bib9);[HowKin12](https://arxiv.org/html/2607.15532#bib.bib71);[HuyLasLas92](https://arxiv.org/html/2607.15532#bib.bib72);[JinMorTal20](https://arxiv.org/html/2607.15532#bib.bib79);[JonKerMac08](https://arxiv.org/html/2607.15532#bib.bib80)\. An interesting question is how to combine polyhedral projection with column generation for application to Boole’s probabilistic logic\. Finally, there is the possibility of representing a domain\-specific projected knowledge base in the form of a decision diagram, in order to obtain enhanced transparency and enable rapid responses to complicated queries\.

## References

- \(1\)Akers, S\.B\.: Binary decision diagrams\.IEEE Transactions on ComputersC\-27, 509–516 \(1978\)
- \(2\)Amano, K\., Maruoka, A\.: On learning monotone boolean functions under the uniform distribution\.Theoretical Computer Science350, 3–12 \(2006\)
- \(3\)Andersen, K\.A\., Hooker, J\.N\.: Bayesian logic\.Decision Support Systems11, 191–210 \(1994\)
- \(4\)Andersen, K\.A\., Hooker, J\.N\.: Determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs\.Annals of Operations Research65, 1–20 \(1996\)
- \(5\)Andersen, K\.A\., Hooker, J\.N\.: A linear programming framework for logics of uncertainty\.Decision Support Systems16, 39–53 \(1996\)
- \(6\)Andersen, K\.A\., Pretolani, D\.: Easy cases of probabilistic satisfiability\.Annals of Mathematics and Artificial Intelligence33, 69–91 \(2001\)
- \(7\)Anderson, J\.R\., Bothell, D\., Byrne, M\.D\., Douglass, S\.A\., Lebiere, C\., Qin, Y\.: An integrated theory of the mind\.Psychological Review111, 1036–1060 \(2004\)
- \(8\)Anthony, M\.: Probabilistic learning and Boolean functions\.In: Y\. Crama, P\.L\. Hammer \(eds\.\) Boolean Models and Methods in Mathematics, Computer Science, and Engineering,*Encyclopedia of Mathematics and its Applications*, vol\. 134, pp\. 197–220\. Cambridge University Press, Cambridge \(2010\)
- \(9\)Balas, E\.: Projection with a minimal system of inequalities\.Computational Optimization and Applications10, 189–193 \(1998\)
- \(10\)Barrett, C\., Tinelli, C\.: Satisfiability modulo theories\.In: E\.M\. Clarke, T\.A\. Henzinger, H\. Veith, R\. Bloem \(eds\.\) Handbook of Model Checking, pp\. 305–343\. Springer \(2018\)
- \(11\)Bartholomew, M\., Lee, J\.: System ASPMT2SMT: Computing ASPMT theories by SMT solvers\.In: Logics in Artificial Intelligence \(JELIA 2014\),*Lecture Notes in Computer Science*, vol\. 8761, pp\. 529–542\. Springer \(2014\)
- \(12\)Bartlett, M\., Cussens, J\.: Integer linear programming for the Bayesian network structure learning problem\.Artificial Intelligence244, 258–271 \(2017\)
- \(13\)Bell, C\., Nerode, A\., Ng, R\.T\., Subrahmanian, V\.S\.: Mixed integer progamming methods for computing nonmonotonic deductive databases\.Journal of the ACM41, 1178–1215 \(1994\)
- \(14\)Ben\-Eliyahu–Zohary, R\.: An incremental algorithm for generating all minimal models\.Artificial Intelligence169, 1–22 \(2005\)
- \(15\)Benders, J\.F\.: Partitioning procedures for solving mixed\-variables programming problems\.Numerische Mathematik4, 238–252 \(1962\)
- \(16\)Bergman, D\., Cire, A\.A\., van Hoeve, W\.J\., Hooker, J\.N\.: Decision Diagrams for Optimization\.Springer \(2016\)
- \(17\)Bertelè, U\., Brioschi, F\.: Nonserial Dynamic Programming\.Academic Press, New York \(1972\)
- \(18\)Blackburn, P\., de Rijke, M\., Venema, Y\.: Modal Logic\.Cambridge University Press, Cambridge \(2002\)
- \(19\)Blackburn, P\., van Benthem, J\.: Modal logic: A semantic perspective\.In: P\. Blackburn, J\. van Benthem, F\. Wolter \(eds\.\) Handbook of Modal Logic, pp\. 2–79\. Elsevier, Amsterdam \(2006\)
- \(20\)Blum, A\., Burcht, C\., Langford, J\.: On learning monotone Boolean functions\.In: Proceedings 39th Annual Symposium on Foundations of Computer Science, pp\. 408–415 \(1998\)
- \(21\)Bollig, B\., Sauerhoff, M\., Sieling, D\., Wegener, I\.: Binary decision diagrams\.In: Y\. Crama, P\.L\. Hammer \(eds\.\) Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp\. 473–505\. Cambridge University Press, Cambridge, UK \(2010\)
- \(22\)Boole, G\.: An Investigation of the Laws of Thought, On Which are Founded the Mathematical Theories of Logic and Probabilities\.Walton and Maberly, London \(1854\)
- \(23\)Borkar, V\.S\., Chandru, V\., Mitter, S\.K\.: Mathematical programming embeddings of logic\.Journal of Automated Reasoning29, 91–106 \(2002\)
- \(24\)Boros, A\., Hammer, P\.L\., Hooker, J\.N\.: Predicting cause\-effect relationships from incomplete discrete observations\.SIAM Journal on Discrete Mathematics7, 531–543 \(1994\)
- \(25\)Boros, E\., Hammer, P\.L\.: Pseudo\-Boolean optimization\.Discrete Applied Mathematics123, 155–225 \(2002\)
- \(26\)Boros, E\., Hammer, P\.L\., Hooker, J\.N\.: Boolean regression\.Annals of Operations Research58, 201–226 \(1995\)
- \(27\)Brun, T\.: Structure probabiliste en logique des propositions\.Memoire d’ingénieur, École des hautes études commerciales, Montréal \(1988\)
- \(28\)Bryant, R\.E\.: Symbolic boolean manipulation with ordered binary decision diagrams\.ACM Computing Surveys24, 293– 318 \(1992\)
- \(29\)Burkart, N\., Huber, M\.F\.: A survey on the explainability of supervised machine learning\.Journal of Artificial Intelligence Research70, 245–317 \(2021\)
- \(30\)Chandru, V\., Hooker, J\.N\.: Extended Horn clauses in propositional logic\.Journal of the ACM38, 203–221 \(1991\)
- \(31\)Chandru, V\., Hooker, J\.N\.: Optimization Methods for Logical Inference\.Wiley \(1999\)
- \(32\)Charnes, A\., Cooper, W\.W\.: Programming with linear fractional functionals\.Naval Research Logistics Quarterly9, 181–186 \(1962\)
- \(33\)Chen, T\., Braga\-Neto, U\.M\.: Statistical detection of boolean regulatory relationships\.IEEE/ACM Transactions on Computational Biology and Bioinformatics10, 1310–1321 \(2017\)
- \(34\)Chinneck, J\.W\.: An effective polynomial\-time heuristic for the minimum\-cardinality IIS set\-covering problem\.Annals of Mathematics and Artificial Intelligence17, 127–144 \(1996\)
- \(35\)Chinneck, J\.W\.: Finding a useful subset of constraints for analysis in an infeasible linear program\.INFORMS Journal on Computing9, 111–129 \(1997\)
- \(36\)Chinneck, J\.W\.: Fast heuristics for the maximum feasible subsystem problem\.INFORMS Journal on Computing13, 171–256 \(2001\)
- \(37\)Chinneck, J\.W\., Dravnieks, E\.W\.: Locating minimal infeasible constraint sets in linear programs\.ORSA Journal on Computing3, 157–168 \(1991\)
- \(38\)Chvátal, V\.: Edmonds polytopes and a hierarchy of combinatorial problems\.Discrete Mathematics4, 305–337 \(1973\)
- \(39\)Conforti, M\., Cornuéjols, G\.: A class of logical inference problems soluble by linear programming\.Journal of the ACM33, 670–675 \(1994\)
- \(40\)Conforti, M\., Cornuéjols, G\., Zambelli, G\.: Integer Programming\.Springer, Dordrecht \(2014\)
- \(41\)Cozman, F\.G\., Marinescu, R\., Lee, J\., Gray, A\., Riegel, R\., Bhattacharjya, D\.: Markov conditions and factorization in logical credal networks\.International Journal of Approximate Reasoning172\(2024\)
- \(42\)Dawande, M\., Hooker, J\.N\.: Inference\-based sensitivity analysis for mixed integer/linear programming\.Operations Research48, 623–634 \(2000\)
- \(43\)Dempster, A\.P\.: Upper and lower probabilities induced by a multivaued mapping\.Annals of Mathematical Statistics38, 325–339 \(1967\)
- \(44\)Dempster, A\.P\.: A generalization of bayesian inference\.Journal of the Royal Statistical Society \(Series B\)30, 205–247 \(1968\)
- \(45\)Devriendt, J\., Gleixner, A\., Nordström, J\.: Learn to relax: Integrating 0–1 integer linear programming with pseudo\-Boolean conflict\-driven search\.Constraints26, 26–55 \(2021\)
- \(46\)Devriendt, J\., Gocht, S\., Demirović, E\., Nordström, J\., Stuckey, P\.: Cutting to the core of pseudo\-boolean optimization: Combining core\-guided search with cutting planes reasoning\.In: National Conference on Artificial Intelligence \(AAAI 2021\), pp\. 3750–3758 \(2021\)
- \(47\)Dubey, H\.V\., Lee, J\.A\., Flaherty, P\.: Maximum a posteriori inference for factor graphs via Benders decmposition\.SIAM Journal on Mathematics of Data Science7\(2025\)
- \(48\)Dugat, V\., Sandri, S\.: Complexity of hierarchical trees in evidence theory\.ORSA Journal on Computing6, 37–49 \(1994\)
- \(49\)Elffers, J\., Nordström, J\.: Divide and conquer: Towards faster pseudo\-Boolean solving\.In: International Joint Conference on Artificial Intelligence \(IJCAI 2018\), pp\. 1291–1299 \(2018\)
- \(50\)Elffers, J\., Nordström, J\.: A cardinal improvement to pseudo\-Boolean solving\.In: National Conference on Artificial Intelligence \(AAAI 2020\), pp\. 1495–1503 \(2020\)
- \(51\)Erdem, E\., Gelfond, M\., Leone, N\.: Applications of answer set programming\.AI Magazine37, 53–68 \(2016\)
- \(52\)Gebser, M\., Kaminski, R\., Kaufmann, B\., Ostrowski, M\., , Schaub, T\., Wanko, P\.: Theory solving made easy with clingo 5\.In: Technical Communications of the 30th International Confrence on Logic Programming \(ICLP 2016\),*Open Access Series in Informatics*, vol\. 52, pp\. 2:1–2:15 \(2016\)
- \(53\)Gelfond, M\., Lifschitz, V\.: The stable model semantics for logic programming\.In: R\.A\. Kowalski, K\.A\. Bowen \(eds\.\) Proceedings of the 5th International Conference and Symposium on Logic Programming, pp\. 1070–1080 \(1988\)
- \(54\)Georgakopolous, G\., Kavvadias, D\., Papadimitriou, C\.H\.: Probabilistic satisfiability\.Journal of Complexity4, 1–11 \(1988\)
- \(55\)Giordani, A\., Saitta, V\.: A norm\-based truthmaker semantics for modal logic\.Journal of Philosophical Logic55, 135–165 \(2026\)
- \(56\)Goldblatt, R\.: Mathematical modal logic: A view of its evolution\.Journal of Applied Logic1, 309–391 \(2003\)
- \(57\)Goranko, V\., Otto, M\.: Model theory of modal logic\.In: P\. Blackburn, J\. van Benthem, F\. Wolter \(eds\.\) Handbook of Modal Logic, pp\. 249–329\. Elsevier, Amsterdam \(2006\)
- \(58\)Haenni, R\., Romeijn, J\.W\., Wheeler, G\., Williamson, J\.: Possible semantics for a common framework of probabilistic logics\.In: V\.N\. Huynh, Y\. Nakamori, H\. Ono, J\. Lawry, V\. Kreinovich, H\.T\. Nguyen \(eds\.\) Proceedings of the International Workshop on Interval/Probabilistic Uncertainty and Non Classical Logics, pp\. 268–279\. Springer \(2008\)
- \(59\)Hähnle, R\.: Many\-valued logic and mixed integer programming\.Annals of Mathematics and Artificial Intelligence12, 231–263 \(1994\)
- \(60\)Haibe\-Kains, B\., Adam, G\.A\., Hosny, A\., Khodakarami, F\., Waldron, L\., Wang, B\., McIntosh, C\., Goldenberg, A\., Kundaje, A\., Greene, C\.S\., Broderick, T\., Hoffman, M\.M\., Leek, J\.T\., , Korthauer, K\., Huber, W\., Brazma, A\., Pineau, J\., Tibshirani, R\., Hastie, T\., Ioannidis, J\.P\.A\., Quackenbush, J\., Aerts, H\.J\.W\.L\.: Artificial intelligence and the value of transparency\.Nature586, E14–E15 \(2020\)
- \(61\)Hailperin, T\.: Boole’s Logic and Probability,*Studies in Logic and the Foundations of Mathematics*, vol\. 85\.North\-Holland, Amsterdam \(1976\)
- \(62\)Hansen, P\., Jaumard, B\.: Probabilistic logic\.In: J\. Kohlas, R\. Kruse \(eds\.\) Algorithms for Uncertainty and Defeasible Reasoning,*Handbook of Defeasible Reasoning and Uncertainty Management Systems*, vol\. 5, pp\. 321–368\. Springer, Berlin \(2000\)
- \(63\)Hansen, P\., Perron, S\.: Merging the local and global approaches to probabilistic satisfiability\.International Journal of Approximate Reasoning47, 125–140 \(2008\)
- \(64\)Hooker, J\.N\.: A mathematical programming model for probabilistic logic\.Tech report 05\-88\-89, Graduate School of Industrial Administration, Carnegie Mellon University \(1988\)
- \(65\)Hooker, J\.N\.: Input proofs and rank one cutting planes\.ORSA Journal on Computing1, 137–145 \(1989\)
- \(66\)Hooker, J\.N\.: Logic\-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction\.Wiley, New York \(2000\)
- \(67\)Hooker, J\.N\.: Decision diagrams and dynamic programming\.In: C\. Gomes, M\. Sellmann \(eds\.\) CPAIOR 2013 Proceedings, pp\. 94–110\. \(2013\)
- \(68\)Hooker, J\.N\.: Projection, consistency, and George Boole\.Constraints21, 59–76 \(2016\)
- \(69\)Hooker, J\.N\.: Logic\-Based Benders Decomposition: Theory and Applications\.Springer \(2024\)
- \(70\)Hooker, J\.N\., Ottosson, G\.: Logic\-based Benders decomposition\.Mathematical Programming96, 33–60 \(2003\)
- \(71\)Howe, J\.M\., King, A\.: Polyhedral analysis using parametric objectives\.In: Proceedings of the International Static Analysis Symposium \(SAS 2012\), pp\. 41–57\. Springer \(2012\)
- \(72\)Huynh, T\., Lassez, C\., Lassez, J\.L\.: Practical issues on the projection of polyhedral sets\.Annals of Mathematics and Artificial Intelligence6, 295–315 \(1992\)
- \(73\)Janhunen, T\., Kaminski, R\., Ostrowski, M\., Schellhorn, S\., Wanko, P\., Schaub, T\.: Clingo goes linear constraints over reals and integers\.Theory and Practice of Logic Programming17, 872–888 \(2017\)
- \(74\)Janhunen, T\., Niemelä, I\.: The answer set programming paradigm\.AI Magazine37, 13–24 \(2016\)
- \(75\)Jaumard, B\., Hansen, P\., Aragão, M\.P\.: Column generation methods for probabilistic logic\.INFORMS Journal on Computing3, 135–148 \(1991\)
- \(76\)Jeroslow, R\.G\.: Representability in mixed integer programming, I: Characterization results\.Discrete Applied Mathematics17, 223–243 \(1987\)
- \(77\)Jeroslow, R\.G\.: Mixed Integer Formulation,*Logic\-Based Decision Support*, vol\. 40\.North\-Holland, Amsterdam \(1989\)
- \(78\)Jeroslow, R\.G\., Wang, J\.: Solving propositional satisfiability problems\.Annals of Mathematics and Artificial Intelligence1, 167–188 \(1990\)
- \(79\)Jing, R\.J\., Moreno\-Maza, M\., Talaashrafi, D\.: Complexity estimates for Fourier\-Motzkin elimination\.In: Proceedings of the International Workshop on Computer Algebra in Scientific Computing \(CASC 2020\), pp\. 282–306\. Springer \(2020\)
- \(80\)Jones, C\.N\., Kerrigan, E\.C\., Maciejowski, J\.M\.: On polyhedral projection and parametric programming\.Journal of Optimization Theory and Applications138, 207–220 \(2008\)
- \(81\)Kane, T\.B\.: Maximum entropy in Nielsson’s probabilistic logic\.In: Proceedings of IJCAI 1989, pp\. 442–447\. Morgan Kaufmann \(1989\)
- \(82\)Kavvadias, D\., Papadimitriou, C\.H\.: A linear programming approach to reasoning about probabilities\.Annals of Mathematics and Artificial Intelligence1, 189–206 \(1990\)
- \(83\)Kim, T\.W\., Hooker, J\.N\., Donaldson, T\.: Taking principles seriously: A hybrid approach to value alignment in artificial intelligence\.Journal of Artificial Intelligence Research70, 871–890 \(2021\)
- \(84\)Kitson, N\.K\., Constantinou, A\.C\., Gao, Z\., Liu, Y\., Chobtham, K\.: A survey of Bayesian network structure learning\.Artificial Intelligence Review56, 8721–8814 \(2023\)
- \(85\)Klinov, P\., Parsia, B\.: On improving the scalability of checking satisfiability in probabilistic description logics\.In: L\. Godo, A\. Pugliese \(eds\.\) International Conference on Scalable Uncertainty Management, pp\. 138–149\. Springer, Berlin \(2009\)
- \(86\)Klinov, P\., Parsia, B\.: A hybrid method for probabilistic satisfiability\.In: N\. Bjørner, V\. Sofronie\-Stokkermans \(eds\.\) 23rd International Conference on Automated Deduction \(CADE\), pp\. 354–368\. Springer \(2011\)
- \(87\)Korhonen, J\.H\., Parviainen, P\.: Exact learning of bounded tree\-width Bayesian networks\.In: Proceedings of the 16th International Conference on Artificial Intelligence and Statistics \(AISTATS 2013\),*Journal of Machine Learning Research Workshop & Conference Proceedings*, vol\. 31, pp\. 370–378 \(2013\)
- \(88\)Lauritzen, S\.L\., Spiegelhalter, D\.J\.: Local computations with probabilities on graphical structures and their application to expert systems\.Journal of the Royal Statistical Society B50, 157–194 \(1988\)
- \(89\)Lebiere, C\., Anderson, J\.R\.: A connectionist implementation of the ACT\-R production system\.In: Proceedings of the Fifteenth Annual Conference of the Cognitive Science Society, pp\. 635–640 \(1993\)
- \(90\)Lee, J\., Meng, Y\.: Answer set programming modulo theories and reasoning about continuous changes\.In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence \(IJCAI 2013\), pp\. 990–996 \(2013\)
- \(91\)Lierler, Y\.: Constraint answer set programming: Integrational and translational \(or SMT\-based\) approaches\.Theory and Practice of Logic Programming23, 195–225 \(2023\)
- \(92\)Lifschitz, V\.: Action languages, answer sets, and planning\.In: K\.R\. Apt, V\.W\. Marek, M\. Truszczyński, D\.S\. Warren \(eds\.\) The Logic Programming Paradigm: A 25\-Year Perspective, pp\. 357–374\. Springer, Berlin \(1999\)
- \(93\)Lifschitz, V\.: What is answer set prgramming?In: Proceedings of the 23rd National Conference on Artificial Intelligence \(AAAI 2008\), pp\. 1594–1597\. AAAI Press \(2008\)
- \(94\)Liu, G\., Janhunen, T\., Niemelä, I\.: Answer set programming via mixed integer programming\.In: Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning, pp\. 32–42 \(2012\)
- \(95\)Liu, G\., Janhunen, T\., Niemelä, I\.: Introducing real variables and integer objective functions to answer set programming\.In: Proceedings of the International Conference on Applications of Declarative Programming and Knowledge Management, pp\. 118–135 \(2014\)
- \(96\)Marek, V\.W\., Truszczyński, M\.: Stable models and an alternative logic programming paradigm\.In: K\.R\. Apt, V\.W\. Marek, M\. Truszczyński, D\.S\. Warren \(eds\.\) The Logic Programming Paradigm: A 25\-Year Perspective, pp\. 375–398\. Springer, Berlin \(1999\)
- \(97\)Marek, W\., Nerode, A\., Remmel, J\.B\.: The stable models of a predicate logic program\.Journal of Logic Programming21, 129–154 \(1994\)
- \(98\)Marinescu, R\., Lee, J\., Bhattacharjya, D\., Cozman, F\., Gray, A\.: Abductive reasoning in logical credal networks\.In: 38th Conference on Neural Information Processing Systems \(NeurIPS\), pp\. 635–640 \(2024\)
- \(99\)Marinescu, R\., Qian, H\., Gray, A\., Bhattacharjya, D\., Barahona, F\., Gao, T\., Riegel, R\., Sahu, P\.: Logical credal networks\.In: 36th Conference on Neural Information Processing Systems \(NeurIPS\), pp\. 635–640 \(2022\)
- \(100\)Mauá, D\.D\., Cozman, F\.G\.: Thirty years of credal networks: Specification, algorithms and complexity\.International Journal of Approximate Reasoning126, 133–157 \(2020\)
- \(101\)Mauá, D\.D\., de Campos, C\.P\., Benavoli, A\., Zaffalon, M\.: Probabilistic inference in credal networks via integer programming\.Artificial Intelligence176, 2351–2370 \(2012\)
- \(102\)Mukherjee, S\., Pelech, S\., Neve, R\.M\., Kuo, W\.L\., Ziyad, S\., Spellman, P\.T\., Gray, J\.W\., Speed, T\.P\.: Sparse combinatorial inference with an application in cancer biology\.Bioinformatics25, 265–271 \(2009\)
- \(103\)Mukherjee, S\., Speed, T\.P\.: Sparse, noisy Boolean functions\.Technical report, University of California, Berkeley \(2007\)
- \(104\)Nemhauser, G\.L\., Wolsey, L\.A\.: Integer and Combinatorial Optimization\.Wiley, New York \(1999\)
- \(105\)Newell, A\.: Unified Theories of Cognition\.Harvard University Press, Cambridge, MA \(1994\)
- \(106\)Newell, A\., Shaw, J\.C\., Simon, H\.A\.: Report on a general problem\-solving program\.In: Proceedings of the International Conference on Information Processing \(IFIP\), vol\. 1, pp\. 256–264\. UNESCO, Paris \(1959\)
- \(107\)Newell, A\., Simon, H\.A\.: The logic theory machine: A complex information processing system\.Tech report P\-868, RAND Corporation \(1956\)
- \(108\)Niemelä, I\.: Logic programs with stable model semantics as a constraint programming paradigm\.Annals of Mathematics and Artificial Intelligence25, 241–273 \(1999\)
- \(109\)Nilsson, N\.J\.: Probabilistic logic\.Artificial Intelligence28, 71–87 \(1986\)
- \(110\)Nilsson, N\.J\.: Probabilistic logic revisited\.Artificial Intelligence59, 39–42 \(1993\)
- \(111\)Osorio, M\., Díaz, J\., Santoyo, A\.: 0\-1 integer programming for computing semi\-stable semantics of argumentation frameworks\.Computación y Sistemas21\(2017\)
- \(112\)Pearl, J\.: Causal diagrams for empirical research\.Biometrika82, 669–710 \(1995\)
- \(113\)Pearl, J\.: Causality: Models, Reasoning, and Inference\.Cambridge University Press, Cambridge \(2000\)
- \(114\)Peyrard, N\., Cros, M\.J\., de Givry, S\., Franc, A\., Robin, S\., Sabbadin, R\., Schiex, T\., Vignes, M\.: Exact and approximate inference in graphical models: Variable elimination and beyond\.arXiv:1506\.08544 \(2018\)
- \(115\)Popov, M\., Balyo, T\., Iser, M\., Ostertag, T\.: Construction of decision diagrams for product configuration\.In: Proceedings of the 25th International Workshop on Configuration, pp\. 108–117 \(2023\)
- \(116\)Sanchez, S\.N\., Triantaphyllou, E\., Chen, J\., Liao, T\.W\.: An incremental learning algorithm for constructing boolean functions from positive and negative examples\.Computers and Operations Research29, 1677–1700 \(2002\)
- \(117\)Serra, T\., Hooker, J\.N\.: Compact representation of near\-optimal integer programming solutions\.Mathematical Programming182, 199–232 \(2020\)
- \(118\)Shafer, G\.: A Mathematical Theory of Evidence\.Princeton University Press, Princeton, NJ \(1976\)
- \(119\)Sloan, R\.H\., Szörényi, B\., Turán, G\.: Learning boolean functions with queries\.In: Y\. Crama, P\.L\. Hammer \(eds\.\) Boolean Models and Methods in Mathematics, Computer Science, and Engineering,*Encyclopedia of Mathematics and its Applications*, vol\. 134, pp\. 221–256\. Cambridge University Press, Cambridge \(2010\)
- \(120\)Smirnov, P\., Berg, J\., Järvisalo, M\.M\.: Pseudo\-Boolean optimization by implicit hitting sets\.In: L\.D\. Michel \(ed\.\) Principles and Practice of Constraint Programming \(CP 2022\), pp\. 51:1–20\. Springer \(2022\)
- \(121\)SolverMax: Solver performance: 1989 vs 2024\.5 January \(2024\)\.URLwww\.solvermax\.com/blog/solver\-performance\-1989\-vs\-2024
- \(122\)Sontag, D\., Meltzer, T\., Globerson, A\., Jaakkola, T\., Weiss, Y\.: Tightening LP relaxations for MAP using message passing\.In: Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence \(UAI 2008\), pp\. 503–510 \(2008\)
- \(123\)van Ditmarsch, H\., Halpern, J\.Y\., van der Hoek, W\., Kooi, B\.: An introduction to logics of knowledge and belief\.In: H\. van Ditmarsch, J\.Y\. Halpern, W\. van der Hoek, B\. Kooi \(eds\.\) Handbook of Epistemic Logic, pp\. 1–52\. College Publications \(2015\)
- \(124\)Varanasi, S\.C\., Meng, B\.: Integrating SMT solvers into goal\-directed answer set programming, challenges and directions\.In: Fourth Workshop on Goal\-directed Execution of Answer Set Programs \(GDE 2024\),*CEUR Workshop Proceedings*, vol\. 3799 \(2024\)
- \(125\)Vonk, M\.C\., Vermetten, D\., de Nobel, J\., Brand, S\., Malekovic, N\., Bäck, T\., Laarman, A\., Kononov, A\.V\.: Optimizing causal interventions in hybrid Bayesian networks\.In: Proceedings of the International Conference on Information Processing and Management of Uncertainty in Knowledge\-Based Systems \(IPMU 2024\), pp\. 245–256 \(2024\)
- \(126\)Wałega, P\.A\., Schultz, C\., Bhatt, M\.: Non\-monotonic spatial reasoning with answer set programming modulo theories\.Theory and Practice of Logic Programming17, 205–225 \(2017\)
- \(127\)Walmsley, J\.: Artificial intelligence and the value of transparency\.AI and Society36, 585–595 \(2021\)
- \(128\)Wang, A\., Wang, X\.F\., He, F\.: A survey of satisfiability modulo theories\.Computer Engineering and Science46, 400–415 \(2024\)
- \(129\)Wegener, I\.: Branching Programs and Binary Decision Diagrams: Theory and Applications\.Society for Industrial and Applied Mathematics, Philadelphia \(2000\)
- \(130\)Wegener, I\.: BDDs—design, analysis, complexity, and applications\.Discrete Applied Mathematics138, 229–251 \(2004\)
- \(131\)Weinberg, A\.I\., Premebida, C\., Faria, D\.R\.: Causality from bottom to top: A survey\.Machine Learning114\(2025\)
- \(132\)Williams, H\.P\.: Logic and Integer Programming\.Springer, Berlin \(2009\)
- \(133\)Wilson, N\.: Algorithms for Dempster\-Shafer theory\.In: J\. Kohlas, R\. Kruse \(eds\.\) Algorithms for Uncertainty and Defeasible Reasoning,*Handbook of Defeasible Reasoning and Uncertainty Management Systems*, vol\. 5, pp\. 421–476\. Springer, Berlin \(2000\)
- \(134\)Zanga, A\., Özkırımlı, E\., Stella, F\.: A survey on causal discovery: Theory and practice\.International Journal of Approximate Reasoning151, 101–129 \(2022\)
- \(135\)Zhou, J\., Chen, F\. \(eds\.\): Human and Machine Learning: Visible, Explainable, Trustworthy, and Transparent\.Springer, Dordrecht \(2018\)