Bipolar Fuzzy Minimum-Weight Satisfiability under Continuous t-Norms: A Clause-Witness Branch-and-Bound Framework
Abstract
Minimum-weight satisfiability asks for a satisfying Boolean assignment of minimum cost, while many fuzzy decision and knowledge systems operate with graded positive and negative relations rather than crisp literals. This paper introduces a bipolar fuzzy minimum-weight satisfiability problem in which positive and negative clause--variable relations, target clause levels, and variable states are represented in the unit interval. The clause requirements are expressed by bipolar fuzzy relational equalities defined with an arbitrary continuous t-norm. Classical minimum-weight CNF satisfiability is recovered as a crisp special case, independently of the selected t-norm, and an optimal Boolean solution is shown to exist in that specialization even though the proposed formulation uses continuous variables. For the graded problem, clause satisfaction is characterized through admissible variable domains and effective clause-witness sets. This structure leads to an exact clause-witness branch-and-bound method with preprocessing, propagation, lower-point closure, and a disjoint-witness packing bound. Computational experiments verify the solver against explicit witness enumeration, mixed-integer baselines, and external SATLIB formulas; on a focused graded ablation set, the packing bound reduces the median number of explored nodes by about 45 percent relative to the single-row witness bound.
Related
- A minimum witness for the 3/2 configuration-linear-program gap in two-weight graph balancing, unique at its size
- A bipolar fuzzy relation equation framework for clinical decision support systems
- Designing an Adaptive Robust and Evolutionary-Game Framework for Minimum Shipment Quotas in Capacity-Constrained Freight Markets
- Exact Complexity of the Satisfiability Problem for Strategy Logic
- More on expressibility of satisfiability in submodels and extensions
BibTeX
@misc{ghodousian2026bipolar,
title = {{Bipolar Fuzzy Minimum-Weight Satisfiability under Continuous t-Norms: A Clause-Witness Branch-and-Bound Framework}},
author = {Amin Ghodousian and Mohammad Sedigh Chopannavaz},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04927},
eprint = {2609.04927},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04927},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Bipolar Fuzzy Minimum-Weight Satisfiability under Continuous t-Norms: A Clause-Witness Branch-and-Bound Framework
AU - Amin Ghodousian
AU - Mohammad Sedigh Chopannavaz
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.04927
UR - https://arxiv.org/abs/2609.04927
AB - Minimum-weight satisfiability asks for a satisfying Boolean assignment of minimum cost, while many fuzzy decision and knowledge systems operate with graded positive and negative relations rather than crisp literals. This paper introduces a bipolar fuzzy minimum-weight satisfiability problem in which positive and negative clause--variable relations, target clause levels, and variable states are represented in the unit interval. The clause requirements are expressed by bipolar fuzzy relational equalities defined with an arbitrary continuous t-norm. Classical minimum-weight CNF satisfiability is recovered as a crisp special case, independently of the selected t-norm, and an optimal Boolean solution is shown to exist in that specialization even though the proposed formulation uses continuous variables. For the graded problem, clause satisfaction is characterized through admissible variable domains and effective clause-witness sets. This structure leads to an exact clause-witness branch-and-bound method with preprocessing, propagation, lower-point closure, and a disjoint-witness packing bound. Computational experiments verify the solver against explicit witness enumeration, mixed-integer baselines, and external SATLIB formulas; on a focused graded ablation set, the packing bound reduces the median number of explored nodes by about 45 percent relative to the single-row witness bound.
ER -